線段樹（）是一種二元樹形資料結構，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。
參考資料
*
- [https://www.cs.nthu.edu.tw/~wkhon/ds/ds10/tutorial/tutorial6.pdf Stabbing Problem]
评论 (0)