線段樹 (儲存區間)

線段樹（英語：Segment tree）是一種二元樹形資料結構，1977年由喬恩·本特利發明^[1]，用以儲存區間或線段，並且允許快速查詢結構內包含某一點的所有區間。

关于用于查询数列信息的数据结构，請見「线段树 (区间查询)」。

一個包含${\displaystyle n}$個區間的線段樹，空間複雜度為${\displaystyle O(n)}$，查詢的時間複雜度則為${\displaystyle O(\log n+k)}$，其中${\displaystyle k}$是符合條件的區間數量。

此資料結構亦可推廣到高維度。

結構

線段樹是一個平衡的二叉树，它将每个长度不为1的区间划分成左右两个区间递归求解。令整個區間的長度為N，則其有N個葉節點，每個葉節點代表一個單位區間，每個內部結點代表的區間為其兩個兒子代表區間的聯集。这种数据结构可以方便的进行大部分的区间操作。

本處以一維的線段樹為例。

線段樹結構示意，其儲存的線段顯示在圖片的下方。

令S是一維線段的集合。將這些線段的端點坐標由小到大排序，令其為${\displaystyle x_{1},x_{2},\cdots ,x_{m}}$。我們將被這些端點切分的每一個區間稱為「單位區間」（每個端點所在的位置會單獨成為一個單位區間），從左到右包含：

${\displaystyle (-\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。