segment tree

WHAT& WHY

線段樹是一種二叉樹，但並一定是完全二叉樹（如最後的8~10部分）， 直觀來說就是把一段區間分成儘可能多的部分，最終劃分成每個點佔一段。其優點是應用範圍廣，易擴展：任何具有區間加性的性質都能用線段樹維護。

在線段樹種，對於任意一個節點[a,b)，它的左子節點的區間為[a,(a+b)/2)， 右子節點的區間為[(a+b)/2, b)。當然還有另一種表示方法：對於任意一個節點[a,b]，其左子節點為[a,(a+b)/2]， 右子節點為[(a+b)/2+1, b]。兩者明顯是一回事，在這裡我們用第一種表示方法（如圖）。

HOW

又到了喜聞樂見的HOW部分。在這裡我們來分析一個求和的二叉樹。

1.如何建樹？

答：使用遞歸遍歷。

對於每一次遞歸，我們需要三個參數：當前節點編號node，當前結點的左範圍l和右範圍r。如果當前節點已經是葉子結點，將原數組中的值放置到這裡。否則遞歸遍歷左子樹和右子樹，當前結點的值為兩個子數之和。

void build(int node, int l, int r) { if (l + 1 == r) { tree[node] = a[l]; } else { int mid = (l + r) / 2; build(node * 2, l, mid); build(node * 2 + 1, mid, r); tree[node] = tree[node * 2] + tree[node * 2 + 1]; }}

2.如何詢問某個特定區間的屬性（在這裡是求和）

答：遞歸遍歷。

其中node 為當前節點編號，l為當前左範圍，r為當前右範圍，ql為目標左範圍，qr為當前右範圍，函數的返回值為sum，也就是當前累積的和。如果目標範圍已經包括了當前遞歸範圍那麼直接返回和，否則繼續分左右兩半遞歸。

int query(int node, int l, int r, int ql, int qr) { int mid = (l + r) / 2; int sum = 0; if (l >= ql && r <= qr) { sum += tree[node]; } else { if (ql < mid) { sum += query(node * 2, l, mid, ql, qr); } if (qr > mid) { sum += query(node * 2 + 1, mid, r, ql, qr); } } return sum;}

3.如何更新某個節點的值

答：當然還是遞歸遍歷啊，都是套路....

首先往下搜到底，改變葉子結點的值，再向上改變所有包含此區間的區間的值。。

int update(int node, int l, int r, int x, int value) { if (l + 1 == r) { tree[node] = value; } else { int mid = (l + r) / 2; if (x < mid) { update(node * 2, l, mid, x, value); } else { update(node * 2 + 1, mid, r, x, value); } } tree[node] = tree[node * 2] + tree[node * 2 + 1];}

來同一發例題~

POJ 2352: 2352 -- Stars

題解： https://github.com/Prionantha/OJ/blob/master/POJ%202352%20-%20Segment%20Tree.cpp

還有另一種使用樹狀數組的解法： https://github.com/Prionantha/OJ/blob/master/POJ%202352%20-%20BIT.cpp

樹狀數組筆記：知乎專欄

第二次非自願裝逼..