線段樹 (儲存區間)

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

一個包含個區間的線段樹，空間複雜度為，查詢的時間複雜度則為，其中是符合條件的區間數量。

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

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

本處以一維的線段樹為例。
令S是一維線段的集合。將這些線段的端點坐標由小到大排序，令其為。我們將被這些端點切分的每一個區間稱為「單位區間」（每個端點所在的位置會單獨成為一個單位區間），從左到右包含：

線段樹的結構為一個二元樹，每個節點都代表一個坐標區間，節點N所代表的區間記為Int(N)，則其需符合以下條件：
其每一個葉節點，從左到右代表每個單位區間。
其內部節點代表的區間是其兩個子節點代表的區間之聯集。
每個節點（包含葉節點）中有一個儲存線段的資料結構。若一個線段S的坐標區間包含Int(N)但不包含Int(parent(N))，則節點N中會儲存線段S。

參考資料


 Stabbing Problem 

X
Category:树结构
Category:二叉树
Category:搜索树