線段樹
本文介紹的是一種儲存區間的資料結構。關於一種提供區間查詢的資料結構，請見「线段树 (区间查询)」。線段樹（英语：Segment tree）是一種二元樹形資料結構，1977年由Jon Louis Bentley發明[1]，用以儲存區間或線段，並且允許快速查詢結構內包含某一點的所有區間。
一個包含n{displaystyle n}個區間的線段樹，空間複雜度為O(n){displaystyle O(n)}，查詢的時間複雜度則為O(logn+k){displaystyle O(log n+k)}，其中k{displaystyle k}是符合條件的區間數量。
此資料結構亦可推廣到高維度。
結構
本處以一維的線段樹為例。
線段樹結構示意，其儲存的線段顯示在圖片的下方。
令S是一維線段的集合。將這些線段的端點坐標由小到大排序，令其為x1,x2,⋯,xm{displaystyle x_{1},x_{2},cdots ,x_{m}}。我們將被這些端點切分的每一個區間稱為「單位區間」（每個端點所在的位置會單獨成為一個單位區間），從左到右包含：
- (−∞,x1),[x1,x1],(x1,x2),[x2,x2],...,(xm−1,xm),[xm,xm],(xm,+∞){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 )}
![{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 )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/70fb76f06a0c51b35b88899c5a06ae41dfc70f76)
線段樹的結構為一個二元樹，每個節點都代表一個坐標區間，節點N所代表的區間記為Int(N)，則其需符合以下條件：
- 其每一個葉節點，從左到右代表每個單位區間。
- 其內部節點代表的區間是其兩個兒子代表的區間之聯集。
- 每個節點（包含葉子）中有一個儲存線段的資料結構。若一個線段S的坐標區間包含Int(N)但不包含Int(parent(N))，則節點N中會儲存線段S。
參考資料
^ （de Berg 等人 2000，p.229）
| |||||||||||||||||||||||||||||||||||||||||||||||
 | 这是一篇小作品。你可以通过编辑或修订扩充其内容。 |
