参考：

https://www.hackerearth.com/zh/practice/data-structures/advanced-data-structures/segment-trees/tutorial/

https://en.wikipedia.org/wiki/Segment_tree

Segment tree

一种静态树的数据结构。用于储存intervals, segments。它可以查询储存的segments。

在原理上，这个结构建立后就不能修改。

翻译称为“线段树”。

线段树储存 a set I of n intervals， 创建的时间复杂度O(n log n).

它搜索k个intervals的时间复杂度是O(log n + k)

它的使用领域：

在计算几何学和地理数据系统 computational geometry, and geographic information systems.

线段树能够被概括到高纬领域“The segment tree can be generalized to higher dimension spaces.”

结构

 in a one-dimensional space. 本文是关于一纬的领域。

线段树

原文：https://www.cnblogs.com/chentianwei/p/11611626.html