線段樹概述
線段樹是一種二叉搜索樹，它將一個區間劃分成一些單元區間，每個單元區間對應線段樹中的一個葉節點。
線段樹是建立在線段的基礎上，每個結點都代表了一條線段[a , b]。長度為1的線段稱為元線段。非元線段都有兩個子結點，左結點代表的線段為[a , (a + b ) / 2]，右結點代表的線段為[( a + b ) / 2 + 1 , b]。
它的優勢在於可以基本保證每個操作的復雜度為O(lgn).
上圖是一個非常簡單的線段樹。
基本操作
一棵線段樹一般要支持三種操作：建樹(build)、查詢(search)和更新(update)。
建樹
讓根節點表示區間[0,N-1]，即所有N個數所組成的一個區間。然後，把區間分成兩半，分別由左右子樹表示。不難證明，這樣的線段樹的節點數只有2N-1個，是O(N)級別的。
線段樹的結構如下：
[cpp]
struct node
{
/* data */
int left, right, mid;
//其它數據
};
struct node
{
/* data */
int left, right, mid;
//其它數據
};
其它的節點信息根據應用情況而定。
顯然，線段樹的構造是一個遞歸過程：
[cpp]
void makeTree(int start, int end, int c)
{
tree[c].left = start;
tree[c].right = end;
tree[c].mid = ((start+end)>>1);
tree[c].max = 0;
if (start == end)
{
//其它操作
return;
}
makeTree(start, tree[c].mid, (c << 1));
makeTree(tree[c].mid+1, end, (c << 1) | 1);
//其他操作
}
void makeTree(int start, int end, int c)
{
tree[c].left = start;
tree[c].right = end;
tree[c].mid = ((start+end)>>1);
tree[c].max = 0;
if (start == end)
{
//其它操作
return;
}
makeTree(start, tree[c].mid, (c << 1));
makeTree(tree[c].mid+1, end, (c << 1) | 1);
//其他操作
}
查詢
查詢操作也是一個遞歸過程。對一個節點的查詢要通過綜合其左右子節點的查詢結果。
[cpp]
void search(int start, int end, int c)
{
if (tree[c].left==start && tree[c].right==end)
{
//其它操作
return ;
}
if (start > tree[c].mid)
search(start, end, (c<<1)|1);
else if (end <= tree[c].mid)
search(start, end, c<<1);
else
{
search(start, tree[c].mid, c<<1);
search(tree[c].mid+1, end, (c<<1)|1);
}
}
void search(int start, int end, int c)
{
if (tree[c].left==start && tree[c].right==end)
{
//其它操作
return ;
}
if (start > tree[c].mid)
search(start, end, (c<<1)|1);
else if (end <= tree[c].mid)
search(start, end, c<<1);
else
{
search(start, tree[c].mid, c<<1);
search(tree[c].mid+1, end, (c<<1)|1);
}
}
更新
當用戶修改一個區間的值時，如果連同其子孫全部修改，則改動的節點數必定會遠遠超過O(log n)個。因而，如果要想把區間修改操作也控制在O(log n)的時間內，只修改O(log n)個節點的信息就成為必要。
借鑒前一節區間查詢用到的思路：區間修改時如果修改了一個節點所表示的區間，也不用去修改它的兒子節點。然而，對於被修改節點的祖先節點，也必須更新它所記錄的值，否則查詢操作就肯定會出問題。
解決方案是Lazy思想：對整個結點進行的操作，先在結點上做標記，而並非真正執行，直到根據查詢操作的需要分成兩部分。
應用場景
（1）：連續區間和；
（2）：區間覆蓋問題；
……
杭電1166
