线段树 (存储区间)

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

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

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

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

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

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

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