线段树

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

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

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

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

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

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