轉(zhuǎn)自：http://www.cnblogs.com/TenosDoIt/p/3453089.html#b
一 概述
線段樹误续，類似區(qū)間樹，是一個(gè)完全二叉樹栽烂，它在各個(gè)節(jié)點(diǎn)保存一條線段（數(shù)組中的一段子數(shù)組），主要用于高效解決連續(xù)區(qū)間的動(dòng)態(tài)查詢問題怀喉，由于二叉結(jié)構(gòu)的特性躬拢，它基本能保持每個(gè)操作的復(fù)雜度為O(logn)。
線段樹的每個(gè)節(jié)點(diǎn)表示一個(gè)區(qū)間馅袁，子節(jié)點(diǎn)則分別表示父節(jié)點(diǎn)的左右半?yún)^(qū)間犹褒，例如父親的區(qū)間是[a,b]，那么(c=(a+b)/2)左兒子的區(qū)間是[a,c]宙枷，右兒子的區(qū)間是[c+1,b]慰丛。
二 從一個(gè)例子理解線段樹
下面我們從一個(gè)經(jīng)典的例子來了解線段樹，問題描述如下:從數(shù)組arr[0...n-1]中查找某個(gè)數(shù)組某個(gè)區(qū)間內(nèi)的最小值贤笆，其中數(shù)組大小固定，但是數(shù)組中的元素的值可以隨時(shí)更新恤左。
對這個(gè)問題一個(gè)簡單的解法是：遍歷數(shù)組區(qū)間找到最小值，時(shí)間復(fù)雜度是O(n),額外的空間復(fù)雜度O(1)链患。當(dāng)數(shù)據(jù)量特別大，而查詢操作很頻繁的時(shí)候贸毕，耗時(shí)可能會(huì)不滿足需求。
另一種解法：使用一個(gè)二維數(shù)組來保存提前計(jì)算好的區(qū)間[i,j]內(nèi)的最小值摊腋，那么預(yù)處理時(shí)間為O(n^2)兴蒸，查詢耗時(shí)O(1), 但是需要額外的O(n^2)空間蕾殴，當(dāng)數(shù)據(jù)量很大時(shí)，這個(gè)空間消耗是龐大的议谷，而且當(dāng)改變了數(shù)組中的某一個(gè)值時(shí)卧晓，更新二維數(shù)組中的最小值也很麻煩。
我們可以用線段樹來解決這個(gè)問題：預(yù)處理耗時(shí)O(n)胜宇，查詢、更新操作O(logn)从诲，需要額外的空間O(n)。根據(jù)這個(gè)問題我們構(gòu)造如下的二叉樹
葉子節(jié)點(diǎn)是原始組數(shù)arr中的元素
非葉子節(jié)點(diǎn)代表它的所有子孫葉子節(jié)點(diǎn)所在區(qū)間的最小值
由于線段樹的父節(jié)點(diǎn)區(qū)間是平均分割到左右子樹宫峦，因此線段樹是完全二叉樹导绷，對于包含n個(gè)葉子節(jié)點(diǎn)的完全二叉樹，它一定有n-1個(gè)非葉節(jié)點(diǎn)檐盟，總共2n-1個(gè)節(jié)點(diǎn)，因此存儲(chǔ)線段是需要的空間復(fù)雜度是O(n)羡忘。那么線段樹的操作：創(chuàng)建線段樹、查詢漫雕、節(jié)點(diǎn)更新 是如何運(yùn)作的呢（以下所有代碼都是針對求區(qū)間最小值問題）浸间？
2.1 創(chuàng)建線段樹
對于線段樹我們可以選擇和普通二叉樹一樣的鏈?zhǔn)浇Y(jié)構(gòu)躺彬。由于線段樹是完全二叉樹仿野，我們也可以用數(shù)組來存儲(chǔ)脚作，下面的討論及代碼都是數(shù)組來存儲(chǔ)線段樹劣针，節(jié)點(diǎn)結(jié)構(gòu)如下（注意到用數(shù)組存儲(chǔ)時(shí)，有效空間為2n-1,實(shí)際空間確不止這么多襟己，比如上面的線段樹中葉子節(jié)點(diǎn)1擎浴、3雖然沒有左右子樹，但是的確占用了數(shù)組空間萌狂，實(shí)際空間是滿二叉樹的節(jié)點(diǎn)數(shù)目： 2 * 2 ^{\lceil \log_2{n} \rceil} - 1， \lceil \log_2{n} \rceil 是樹的高度务傲，但是這個(gè)空間復(fù)雜度也是O(n)的 ）售葡。
struct SegTreeNode
{
int val;
}；
定義包含n個(gè)節(jié)點(diǎn)的線段樹 SegTreeNode segTree[n]尖阔，segTree[0]表示根節(jié)點(diǎn)。那么對于節(jié)點(diǎn)segTree[i]齿坷，它的左孩子是segTree[2i+1],右孩子是segTree[2i+2]永淌。
我們可以從根節(jié)點(diǎn)開始照雁，平分區(qū)間饺蚊，遞歸的創(chuàng)建線段樹，線段樹的創(chuàng)建函數(shù)如下：
1 const int MAXNUM = 1000;
2 struct SegTreeNode
3 {
4 int val;
5 }segTree[MAXNUM];//定義線段樹
6
7
14 void build(int root, int arr[], int istart, int iend)
15 {
16 if(istart == iend)//葉子節(jié)點(diǎn)
17 segTree[root].val = arr[istart];
18 else
19 {
20 int mid = (istart + iend) / 2;
21 build(root*2+1, arr, istart, mid);//遞歸構(gòu)造左子樹
22 build(root*2+2, arr, mid+1, iend);//遞歸構(gòu)造右子樹
23 //根據(jù)左右子樹根節(jié)點(diǎn)的值，更新當(dāng)前根節(jié)點(diǎn)的值
24 segTree[root].val = min(segTree[root*2+1].val, segTree[root*2+2].val);
25 }
26 }
2.2 查詢線段樹
已經(jīng)構(gòu)建好了線段樹苗缩，那么怎樣在它上面超找某個(gè)區(qū)間的最小值呢？查詢的思想是選出一些區(qū)間泻肯，使他們相連后恰好涵蓋整個(gè)查詢區(qū)間灶挟，因此線段樹適合解決“相鄰的區(qū)間的信息可以被合并成兩個(gè)區(qū)間的并區(qū)間的信息”的問題稚铣。代碼如下，具體見代碼解釋
7 int query(int root, int nstart, int nend, int qstart, int qend)
8 {
9 //查詢區(qū)間和當(dāng)前節(jié)點(diǎn)區(qū)間沒有交集
10 if(qstart > nend || qend <<span style="font-family: 'Courier New' !important;"> nstart)
11 return INFINITE;
12 //當(dāng)前節(jié)點(diǎn)區(qū)間包含在查詢區(qū)間內(nèi)
13 if(qstart <= nstart && qend >= nend)
14 return segTree[root].val;
15 //分別從左右子樹查詢，返回兩者查詢結(jié)果的較小值
16 int mid = (nstart + nend) / 2;
17 return min(query(root*2+1, nstart, mid, qstart, qend),
18 query(root*2+2, mid + 1, nend, qstart, qend));
19
20 }
舉例說明（對照上面的二叉樹）：
1、當(dāng)我們要查詢區(qū)間[0,2]的最小值時(shí)椒楣，從根節(jié)點(diǎn)開始捧灰，要分別查詢左右子樹，查詢左子樹時(shí)節(jié)點(diǎn)區(qū)間[0,2]包含在查詢區(qū)間[0,2]內(nèi)煌寇，返回當(dāng)前節(jié)點(diǎn)的值1，查詢右子樹時(shí)银锻，節(jié)點(diǎn)區(qū)間[3,5]和查詢區(qū)間[0,2]沒有交集，返回正無窮INFINITE掉弛，查詢結(jié)果取兩子樹查詢結(jié)果的較小值1殃饿，因此結(jié)果是1.
2芋肠、查詢區(qū)間[0,3]時(shí)帖池，從根節(jié)點(diǎn)開始肴甸，查詢左子樹的節(jié)點(diǎn)區(qū)間[0,2]包含在區(qū)間[0,3]內(nèi)友扰，返回當(dāng)前節(jié)點(diǎn)的值1村怪；查詢右子樹時(shí)甚负，繼續(xù)遞歸查詢右子樹的左右子樹搅轿，查詢到非葉節(jié)點(diǎn)4時(shí)没宾，又要繼續(xù)遞歸查詢：葉子節(jié)點(diǎn)4的節(jié)點(diǎn)區(qū)間[3,3]包含在查詢區(qū)間[0,3]內(nèi)，返回4会钝，葉子節(jié)點(diǎn)9的節(jié)點(diǎn)區(qū)間[4,4]和[0,3]沒有交集俭正，返回INFINITE,因此非葉節(jié)點(diǎn)4返回的是min(4, INFINITE) = 4，葉子節(jié)點(diǎn)3的節(jié)點(diǎn)區(qū)間[5,5]和[0,3]沒有交集澡罚，返回INFINITE,因此非葉節(jié)點(diǎn)3返回min(4, INFINITE) = 4, 因此根節(jié)點(diǎn)返回 min(1,4) = 1。
2.3單節(jié)點(diǎn)更新
單節(jié)點(diǎn)更新是指只更新線段樹的某個(gè)葉子節(jié)點(diǎn)的值肾请，但是更新葉子節(jié)點(diǎn)會(huì)對其父節(jié)點(diǎn)的值產(chǎn)生影響留搔，因此更新子節(jié)點(diǎn)后，要回溯更新其父節(jié)點(diǎn)的值铛铁。
1
8 void updateOne(int root, int nstart, int nend, int index, int addVal)
9 {
10 if(nstart == nend)
11 {
12 if(index == nstart)//找到了相應(yīng)的節(jié)點(diǎn)隔显，更新之
13 segTree[root].val += addVal;
14 return;
15 }
16 int mid = (nstart + nend) / 2;
17 if(index <= mid)//在左子樹中更新
18 updateOne(root*2+1, nstart, mid, index, addVal);
19 else updateOne(root*2+2, mid+1, nend, index, addVal);//在右子樹中更新
20 //根據(jù)左右子樹的值回溯更新當(dāng)前節(jié)點(diǎn)的值
21 segTree[root].val = min(segTree[root*2+1].val, segTree[root*2+2].val);
22 }
比如我們要更新葉子節(jié)點(diǎn)4（addVal = 6）,更新后值變?yōu)?0，那么其父節(jié)點(diǎn)的值從4變?yōu)?哺窄，非葉結(jié)點(diǎn)3的值更新后不變生年，根節(jié)點(diǎn)更新后也不變。
2.4 區(qū)間更新
區(qū)間更新是指更新某個(gè)區(qū)間內(nèi)的葉子節(jié)點(diǎn)的值，因?yàn)樯婕暗降娜~子節(jié)點(diǎn)不止一個(gè)挑格，而葉子節(jié)點(diǎn)會(huì)影響其相應(yīng)的非葉父節(jié)點(diǎn)仪或，那么回溯需要更新的非葉子節(jié)點(diǎn)也會(huì)有很多旨巷，如果一次性更新完，操作的時(shí)間復(fù)雜度肯定不是O(lgn)，例如當(dāng)我們要更新區(qū)間[0,3]內(nèi)的葉子節(jié)點(diǎn)時(shí)辆沦，需要更新出了葉子節(jié)點(diǎn)3,9外的所有其他節(jié)點(diǎn)郊闯。為此引入了線段樹中的延遲標(biāo)記概念，這也是線段樹的精華所在害捕。
延遲標(biāo)記：每個(gè)節(jié)點(diǎn)新增加一個(gè)標(biāo)記殿漠，記錄這個(gè)節(jié)點(diǎn)是否進(jìn)行了某種修改(這種修改操作會(huì)影響其子節(jié)點(diǎn))，對于任意區(qū)間的修改仪吧，我們先按照區(qū)間查詢的方式將其劃分成線段樹中的節(jié)點(diǎn)，然后修改這些節(jié)點(diǎn)的信息，并給這些節(jié)點(diǎn)標(biāo)記上代表這種修改操作的標(biāo)記狞贱。在修改和查詢的時(shí)候别垮，如果我們到了一個(gè)節(jié)點(diǎn)p老充，并且決定考慮其子節(jié)點(diǎn)廷粒，那么我們就要看節(jié)點(diǎn)p是否被標(biāo)記，如果有派阱，就要按照標(biāo)記修改其子節(jié)點(diǎn)的信息，并且給子節(jié)點(diǎn)都標(biāo)上相同的標(biāo)記芋酌，同時(shí)消掉節(jié)點(diǎn)p的標(biāo)記旱易。
因此需要在線段樹結(jié)構(gòu)中加入延遲標(biāo)記域妄迁，本文例子中我們加入標(biāo)記與addMark，表示節(jié)點(diǎn)的子孫節(jié)點(diǎn)在原來的值的基礎(chǔ)上加上addMark的值度苔，同時(shí)還需要修改創(chuàng)建函數(shù)build 和 查詢函數(shù) query，修改的代碼用紅色字體表示，其中區(qū)間更新的函數(shù)為update鸥诽，代碼如下：
1 const int INFINITE = INT_MAX;
2 const int MAXNUM = 1000;
3 struct SegTreeNode
4 {
5 int val;
6 int addMark;//延遲標(biāo)記
7 }segTree[MAXNUM];//定義線段樹
8
9
16 void build(int root, int arr[], int istart, int iend)
17 {
18 segTree[root].addMark = 0;//----設(shè)置標(biāo)延遲記域
19 if(istart == iend)//葉子節(jié)點(diǎn)
20 segTree[root].val = arr[istart];
21 else
22 {
23 int mid = (istart + iend) / 2;
24 build(root*2+1, arr, istart, mid);//遞歸構(gòu)造左子樹
25 build(root*2+2, arr, mid+1, iend);//遞歸構(gòu)造右子樹
26 //根據(jù)左右子樹根節(jié)點(diǎn)的值，更新當(dāng)前根節(jié)點(diǎn)的值
27 segTree[root].val = min(segTree[root*2+1].val, segTree[root*2+2].val);
28 }
29 }
30
31
35 void pushDown(int root)
36 {
37 if(segTree[root].addMark != 0)
38 {
39 //設(shè)置左右孩子節(jié)點(diǎn)的標(biāo)志域，因?yàn)楹⒆庸?jié)點(diǎn)可能被多次延遲標(biāo)記又沒有向下傳遞
40 //所以是 “+=”
41 segTree[root*2+1].addMark += segTree[root].addMark;
42 segTree[root*2+2].addMark += segTree[root].addMark;
43 //根據(jù)標(biāo)志域設(shè)置孩子節(jié)點(diǎn)的值撒汉。因?yàn)槲覀兪乔髤^(qū)間最小值，因此當(dāng)區(qū)間內(nèi)每個(gè)元
44 //素加上一個(gè)值時(shí)逗概，區(qū)間的最小值也加上這個(gè)值
45 segTree[root*2+1].val += segTree[root].addMark;
46 segTree[root*2+2].val += segTree[root].addMark;
47 //傳遞后怀偷，當(dāng)前節(jié)點(diǎn)標(biāo)記域清空
48 segTree[root].addMark = 0;
49 }
50 }
51
52
58 int query(int root, int nstart, int nend, int qstart, int qend)
59 {
60 //查詢區(qū)間和當(dāng)前節(jié)點(diǎn)區(qū)間沒有交集
61 if(qstart > nend || qend <<span style="font-family: 'Courier New' !important;"> nstart)
62 return INFINITE;
63 //當(dāng)前節(jié)點(diǎn)區(qū)間包含在查詢區(qū)間內(nèi)
64 if(qstart <= nstart && qend >= nend)
65 return segTree[root].val;
66 //分別從左右子樹查詢恋捆，返回兩者查詢結(jié)果的較小值
67 pushDown(root); //----延遲標(biāo)志域向下傳遞
68 int mid = (nstart + nend) / 2;
69 return min(query(root*2+1, nstart, mid, qstart, qend),
70 query(root*2+2, mid + 1, nend, qstart, qend));
71
72 }
73
74
81 void update(int root, int nstart, int nend, int ustart, int uend, int addVal)
82 {
83 //更新區(qū)間和當(dāng)前節(jié)點(diǎn)區(qū)間沒有交集
84 if(ustart > nend || uend <<span style="font-family: 'Courier New' !important;"> nstart)
85 return ;
86 //當(dāng)前節(jié)點(diǎn)區(qū)間包含在更新區(qū)間內(nèi)
87 if(ustart <= nstart && uend >= nend)
88 {
89 segTree[root].addMark += addVal;
90 segTree[root].val += addVal;
91 return ;
92 }
93 pushDown(root); //延遲標(biāo)記向下傳遞
94 //更新左右孩子節(jié)點(diǎn)
95 int mid = (nstart + nend) / 2;
96 update(root*2+1, nstart, mid, ustart, uend, addVal);
97 update(root*2+2, mid+1, nend, ustart, uend, addVal);
98 //根據(jù)左右子樹的值回溯更新當(dāng)前節(jié)點(diǎn)的值
99 segTree[root].val = min(segTree[root*2+1].val, segTree[root*2+2].val);
100 }
區(qū)間更新舉例說明：當(dāng)我們要對區(qū)間[0,2]的葉子節(jié)點(diǎn)增加2矩欠，利用區(qū)間查詢的方法從根節(jié)點(diǎn)開始找到了非葉子節(jié)點(diǎn)[0-2]庞瘸，把它的值設(shè)置為1+2 = 3彤灶，并且把它的延遲標(biāo)記設(shè)置為2，更新完畢；當(dāng)我們要查詢區(qū)間[0,1]內(nèi)的最小值時(shí)刽酱，查找到區(qū)間[0,2]時(shí)，發(fā)現(xiàn)它的標(biāo)記不為0娜氏，并且還要向下搜索，因此要把標(biāo)記向下傳遞记餐，把節(jié)點(diǎn)[0-1]的值設(shè)置為2+2 = 4猴仑，標(biāo)記設(shè)置為2朱浴，節(jié)點(diǎn)[2-2]的值設(shè)置為1+2 = 3芝囤，標(biāo)記設(shè)置為2（其實(shí)葉子節(jié)點(diǎn)的標(biāo)志是不起作用的先壕，這里是為了操作的一致性）瘩扼，然后返回查詢結(jié)果：[0-1]節(jié)點(diǎn)的值4；當(dāng)我們再次更新區(qū)間[0,1]（增加3）時(shí)垃僚，查詢到節(jié)點(diǎn)[0-1],發(fā)現(xiàn)它的標(biāo)記值為2集绰，因此把它的標(biāo)記值設(shè)置為2+3 = 5，節(jié)點(diǎn)的值設(shè)置為4+3 = 7谆棺；
其實(shí)當(dāng)區(qū)間更新的區(qū)間左右值相等時(shí)（[i,i]）栽燕，就相當(dāng)于單節(jié)點(diǎn)更新，單節(jié)點(diǎn)更新只是區(qū)間更新的特例改淑。
