线段树 (存储区间)

关于用于查询数列信息的数据结构，请见“线段树 (区间查询)”。

线段树（英语：Segment tree）是一种二叉树形数据结构，1977年由乔恩·本特利发明，用以存储区间或线段，并且允许快速查询结构内包含某一点的所有区间。

一个包含$n$个区间的线段树，空间复杂度为$O(n)$，查询的时间复杂度则为$O(\log n+k)$，其中$k$是符合条件的区间数量。

此数据结构亦可推广到高维度。

结构

线段树是一个平衡的二叉树，它将每个长度不为1的区间划分成左右两个区间递归求解。令整个区间的长度为N，则其有N个叶节点，每个叶节点代表一个单位区间，每个内部结点代表的区间为其两个儿子代表区间的联集。这种数据结构可以方便的进行大部分的区间操作。

本处以一维的线段树为例。

线段树结构示意，其存储的线段显示在图片的下方。

令S是一维线段的集合。将这些线段的端点坐标由小到大排序，令其为$x_{1},x_{2},\cdots ,x_{m}$。我们将被这些端点切分的每一个区间称为“单位区间”（每个端点所在的位置会单独成为一个单位区间），从左到右包含：

$(-\infty ,x_{1}),[x_{1},x_{1}],(x_{1},x_{2}),[x_{2},x_{2}],...,(x_{m-1},x_{m}),[x_{m},x_{m}],(x_{m},+\infty )$

线段树的结构为一个二叉树，每个节点都代表一个坐标区间，节点N所代表的区间记为Int(N)，则其需符合以下条件：

• 其每一个叶节点，从左到右代表每个单位区间。
• 其内部节点代表的区间是其两个儿子代表的区间之联集。
• 每个节点（包含叶子）中有一个存储线段的数据结构。若一个线段S的坐标区间包含Int(N)但不包含Int(parent(N))，则节点N中会存储线段S。

参考资料

• de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried. More Geometric Data Structures. Computational Geometry: algorithms and applications 2nd. Springer-Verlag Berlin Heidelberg New York. 20002000. ISBN 978-3-540-77973-5. doi:10.1007/978-3-540-77974-2. 
• Stabbing Problem （页面存档备份，存于互联网档案馆）