<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> # Segment Tree - 線段樹 -------- #### 線段樹 給定一段區間上的數字$$ s = [x_{0}, x_{2}, \dots, x_{n-1}] $$，求出$$ [p, q) $$這個區間上的所有數字之和（$$ 0 \leq p \leq q \lt n $$）。該區間可以修改每個元素的值，新增/刪除新的元素。 循環累加數組的算法可以在$$ O(1) $$時間復雜度內修改某個位置上的值，$$ O(n) $$時間復雜度內算出$$ [p, q) $$區間上所有元素之和。而線段樹可以做到修改值、累加區間的時間復雜度都為$$ O(log_{2} n) $$。 線段樹是一種二叉樹，它將數組$$ s = [x_{0}, x_{1}, \dots, x_{n-1}] $$劃分區間，線段樹中節點$$ [p,q) $$表示范圍$$ s[p,q) $$上被關注的內容，例如該區間上所有元素的和、最大/最小元素的值、第$$ k $$大的值等。本問題關注區間$$ s[p,q) $$上的元素之和。 節點$$ [p,q) $$代表數組$$ s[p,q) $$上所有元素之和。左子樹為$$ s[p, \frac{p + q}{2}) $$上元素之和，右子樹為$$ s[\frac{p + q}{2}, q) $$上元素之和。線段樹的葉子節點是長度為$$ 1 $$的區域$$ [p,p+1) $$。數組$$ s = [0, 1, 2, 3, 4, 5] $$如圖所示：  構造操作：從根節點開始，遞歸的將節點$$ [p,q) $$拆分為$$ [p, \frac{p+q}{2}) $$和$$ [ \frac{p+q}{2},q) $$，則顯然$$ \sum_{i=p}^{q-1} s_{i} = \sum_{i=p}^{\frac{p+q}{2}} s_{i} + \sum_{i = \frac{p+q}{2}}^{q-1} s_{i} $$，即父節點的值等于左右孩子節點值的和，我們將區域$$ s[p,q) $$上所有元素之和記錄在線段樹的節點$$ [p,q) $$上。像這樣遞歸的分解左右孩子，直到葉子節點為止。構造操作的時間復雜度為$$ O(n) $$。 更新操作：修改區間$$ s $$中任意一個值$$ s[i] $$需要修改從葉子節點$$ [i, i+1) $$到根節點$$ [p,q) $$這一分支上的所有節點，因為它們上所存儲的信息都會受到影響。更新操作的時間復雜度為$$ O(log_2?n) $$。 查詢操作：查詢區間$$ s[i,j) $$上所有元素之和，需要遞歸的從根節點向下匹配。對于節點$$ [p, q) $$有以下四種情況： $$ (1) $$ 若$$ [p,q) = [i,j) $$則該節點上的值即為所求，算法結束； $$ (2) $$ 若$$ j \leq \frac{p+q}{2} $$說明$$ [i,j) $$只屬于其左孩子； $$ (3) $$ 若$$ i \geq \frac{p+q}{2} $$說明$$ [i,j) $$只屬于其右孩子； $$ (4) $$ 若$$ i \lt \frac{p+q}{2}, j \gt \frac{p+q}{2} $$說明$$ [i, j) $$中一部分屬于左孩子，另一部分屬于右孩子，這時將$$ [i,j) $$拆分為兩部分$$ [i, \frac{p+q}{2}) $$和$$ [\frac{p+q}{2}, j) $$，分別匹配自己所屬的區域； 實際編碼時用數組$$ t $$來表示二叉樹（也可以真的寫一個二叉樹），節點$$ i $$的左孩子為$$ 2i+1 $$，右孩子為$$ 2i+2 $$。$$ t[0] $$為二叉樹根節點，代表$$ s[0,n) $$區域上所有元素之和，左孩子$$ t[1] $$表示$$ s[0, \frac{n}{2}) $$區域之和，右孩子$$ t[2] $$表示$$ s[\frac{n}{2}, n) $$區域之和，以此類推。 -------- #### 源碼 [SegmentTree.h](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/DataStructure/SegmentTree.h) [SegmentTree.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/DataStructure/SegmentTree.cpp) #### 測試 [SegmentTreeTest.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/DataStructure/SegmentTreeTest.cpp)