|
-------------------------- 線段樹，類似區(qū)間樹，它在各個節(jié)點保存一條線段（數(shù)組中的一段子數(shù)組），主要用于高效解決連續(xù)區(qū)間的動態(tài)查詢問題，由于二叉結(jié)構(gòu)的特性，它基本能保持每個操作的復雜度為O(logn)。 線段樹的每個節(jié)點表示一個區(qū)間，子節(jié)點則分別表示父節(jié)點的左右半?yún)^(qū)間，例如父親的區(qū)間是[a,b]，那么(c=(a+b)/2)左兒子的區(qū)間是[a,c]，右兒子的區(qū)間是[c+1,b]。 下面我們從一個經(jīng)典的例子來了解線段樹，問題描述如下:從數(shù)組arr[0...n-1]中查找某個數(shù)組某個區(qū)間內(nèi)的最小值，其中數(shù)組大小固定，但是數(shù)組中的元素的值可以隨時更新。 對這個問題一個簡單的解法是：遍歷數(shù)組區(qū)間找到最小值，時間復雜度是O(n),額外的空間復雜度O(1)。當數(shù)據(jù)量特別大，而查詢操作很頻繁的時候，耗時可能會不滿足需求。 另一種解法：使用一個二維數(shù)組來保存提前計算好的區(qū)間[i,j]內(nèi)的最小值，那么預處理時間為O(n^2)，查詢耗時O(1), 但是需要額外的O(n^2)空間，當數(shù)據(jù)量很大時，這個空間消耗是龐大的，而且當改變了數(shù)組中的某一個值時，更新二維數(shù)組中的最小值也很麻煩。 我們可以用線段樹來解決這個問題：預處理耗時O(n)，查詢、更新操作O(logn)，需要額外的空間O(n)。根據(jù)這個問題我們構(gòu)造如下的二叉樹
例如對于數(shù)組[2, 5, 1, 4, 9, 3]可以構(gòu)造如下的二叉樹（背景為白色表示葉子節(jié)點，非葉子節(jié)點的值是其對應數(shù)組區(qū)間內(nèi)的最小值，例如根節(jié)點表示數(shù)組區(qū)間arr[0...5]內(nèi)的最小值是1）： 本文地址
由于線段樹的父節(jié)點區(qū)間是平均分割到左右子樹，因此線段樹是完全二叉樹，對于包含n個葉子節(jié)點的完全二叉樹，它一定有n-1個非葉節(jié)點，總共2n-1個節(jié)點，因此存儲線段是需要的空間復雜度是O(n)。那么線段樹的操作：創(chuàng)建線段樹、查詢、節(jié)點更新 是如何運作的呢（以下所有代碼都是針對求區(qū)間最小值問題）？ 對于線段樹我們可以選擇和普通二叉樹一樣的鏈式結(jié)構(gòu)。由于線段樹是完全二叉樹，我們也可以用數(shù)組來存儲，下面的討論及代碼都是數(shù)組來存儲線段樹，節(jié)點結(jié)構(gòu)如下（注意到用數(shù)組存儲時，有效空間為2n-1,實際空間確不止這么多，比如上面的線段樹中葉子節(jié)點1、3雖然沒有左右子樹，但是的確占用了數(shù)組空間，實際空間是滿二叉樹的節(jié)點數(shù)目： struct SegTreeNode { int val; }； 定義包含n個節(jié)點的線段樹 SegTreeNode segTree[n]，segTree[0]表示根節(jié)點。那么對于節(jié)點segTree[i]，它的左孩子是segTree[2*i+1],右孩子是segTree[2*i+2]。 我們可以從根節(jié)點開始，平分區(qū)間，遞歸的創(chuàng)建線段樹，線段樹的創(chuàng)建函數(shù)如下： 1 const int MAXNUM = 1000; 2 struct SegTreeNode 3 { 4 int val; 5 }segTree[MAXNUM];//定義線段樹 6 7 /* 8 功能：構(gòu)建線段樹 9 root：當前線段樹的根節(jié)點下標 10 arr: 用來構(gòu)造線段樹的數(shù)組 11 istart：數(shù)組的起始位置 12 iend：數(shù)組的結(jié)束位置 13 */ 14 void build(int root, int arr[], int istart, int iend) 15 { 16 if(istart == iend)//葉子節(jié)點 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é)點的值，更新當前根節(jié)點的值 24 segTree[root].val = min(segTree[root*2+1].val, segTree[root*2+2].val); 25 } 26 } 已經(jīng)構(gòu)建好了線段樹，那么怎樣在它上面超找某個區(qū)間的最小值呢？查詢的思想是選出一些區(qū)間，使他們相連后恰好涵蓋整個查詢區(qū)間，因此線段樹適合解決“相鄰的區(qū)間的信息可以被合并成兩個區(qū)間的并區(qū)間的信息”的問題。代碼如下，具體見代碼解釋 1 /* 2 功能：線段樹的區(qū)間查詢 3 root：當前線段樹的根節(jié)點下標 4 [nstart, nend]: 當前節(jié)點所表示的區(qū)間 5 [qstart, qend]: 此次查詢的區(qū)間 6 */ 7 int query(int root, int nstart, int nend, int qstart, int qend) 8 { 9 //查詢區(qū)間和當前節(jié)點區(qū)間沒有交集 10 if(qstart > nend || qend < nstart) 11 return INFINITE; 12 //當前節(jié)點區(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、當我們要查詢區(qū)間[0,2]的最小值時，從根節(jié)點開始，要分別查詢左右子樹，查詢左子樹時節(jié)點區(qū)間[0,2]包含在查詢區(qū)間[0,2]內(nèi)，返回當前節(jié)點的值1，查詢右子樹時，節(jié)點區(qū)間[3,5]和查詢區(qū)間[0,2]沒有交集，返回正無窮INFINITE，查詢結(jié)果取兩子樹查詢結(jié)果的較小值1，因此結(jié)果是1. 2、查詢區(qū)間[0,3]時，從根節(jié)點開始，查詢左子樹的節(jié)點區(qū)間[0,2]包含在區(qū)間[0,3]內(nèi)，返回當前節(jié)點的值1；查詢右子樹時，繼續(xù)遞歸查詢右子樹的左右子樹，查詢到非葉節(jié)點4時，又要繼續(xù)遞歸查詢：葉子節(jié)點4的節(jié)點區(qū)間[3,3]包含在查詢區(qū)間[0,3]內(nèi)，返回4，葉子節(jié)點9的節(jié)點區(qū)間[4,4]和[0,3]沒有交集，返回INFINITE,因此非葉節(jié)點4返回的是min(4, INFINITE) = 4，葉子節(jié)點3的節(jié)點區(qū)間[5,5]和[0,3]沒有交集，返回INFINITE,因此非葉節(jié)點3返回min(4, INFINITE) = 4, 因此根節(jié)點返回 min(1,4) = 1。 單節(jié)點更新是指只更新線段樹的某個葉子節(jié)點的值，但是更新葉子節(jié)點會對其父節(jié)點的值產(chǎn)生影響，因此更新子節(jié)點后，要回溯更新其父節(jié)點的值。 1 /* 2 功能：更新線段樹中某個葉子節(jié)點的值 3 root：當前線段樹的根節(jié)點下標 4 [nstart, nend]: 當前節(jié)點所表示的區(qū)間 5 index: 待更新節(jié)點在原始數(shù)組arr中的下標 6 addVal: 更新的值（原來的值加上addVal） 7 */ 8 void updateOne(int root, int nstart, int nend, int index, int addVal) 9 { 10 if(nstart == nend) 11 { 12 if(index == nstart)//找到了相應的節(jié)點，更新之 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ù)左右子樹的值回溯更新當前節(jié)點的值 21 segTree[root].val = min(segTree[root*2+1].val, segTree[root*2+2].val); 22 } 比如我們要更新葉子節(jié)點4（addVal = 6）,更新后值變?yōu)?0，那么其父節(jié)點的值從4變?yōu)?，非葉結(jié)點3的值更新后不變，根節(jié)點更新后也不變。 區(qū)間更新是指更新某個區(qū)間內(nèi)的葉子節(jié)點的值，因為涉及到的葉子節(jié)點不止一個，而葉子節(jié)點會影響其相應的非葉父節(jié)點，那么回溯需要更新的非葉子節(jié)點也會有很多，如果一次性更新完，操作的時間復雜度肯定不是O(lgn)，例如當我們要更新區(qū)間[0,3]內(nèi)的葉子節(jié)點時，需要更新出了葉子節(jié)點3,9外的所有其他節(jié)點。為此引入了線段樹中的延遲標記概念，這也是線段樹的精華所在。 延遲標記：每個節(jié)點新增加一個標記，記錄這個節(jié)點是否進行了某種修改(這種修改操作會影響其子節(jié)點)，對于任意區(qū)間的修改，我們先按照區(qū)間查詢的方式將其劃分成線段樹中的節(jié)點，然后修改這些節(jié)點的信息，并給這些節(jié)點標記上代表這種修改操作的標記。在修改和查詢的時候，如果我們到了一個節(jié)點p，并且決定考慮其子節(jié)點，那么我們就要看節(jié)點p是否被標記，如果有，就要按照標記修改其子節(jié)點的信息，并且給子節(jié)點都標上相同的標記，同時消掉節(jié)點p的標記。 因此需要在線段樹結(jié)構(gòu)中加入延遲標記域，本文例子中我們加入標記與addMark，表示節(jié)點的子孫節(jié)點在原來的值的基礎(chǔ)上加上addMark的值，同時還需要修改創(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;//延遲標記 7 }segTree[MAXNUM];//定義線段樹 8 9 /* 10 功能：構(gòu)建線段樹 11 root：當前線段樹的根節(jié)點下標 12 arr: 用來構(gòu)造線段樹的數(shù)組 13 istart：數(shù)組的起始位置 14 iend：數(shù)組的結(jié)束位置 15 */ 16 void build(int root, int arr[], int istart, int iend) 17 { 18 segTree[root].addMark = 0;//----設(shè)置標延遲記域 19 if(istart == iend)//葉子節(jié)點 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é)點的值，更新當前根節(jié)點的值 27 segTree[root].val = min(segTree[root*2+1].val, segTree[root*2+2].val); 28 } 29 } 30 31 /* 32 功能：當前節(jié)點的標志域向孩子節(jié)點傳遞 33 root: 當前線段樹的根節(jié)點下標 34 */ 35 void pushDown(int root) 36 { 37 if(segTree[root].addMark != 0) 38 { 39 //設(shè)置左右孩子節(jié)點的標志域，因為孩子節(jié)點可能被多次延遲標記又沒有向下傳遞 40 //所以是 “+=” 41 segTree[root*2+1].addMark += segTree[root].addMark; 42 segTree[root*2+2].addMark += segTree[root].addMark; 43 //根據(jù)標志域設(shè)置孩子節(jié)點的值。因為我們是求區(qū)間最小值，因此當區(qū)間內(nèi)每個元 44 //素加上一個值時，區(qū)間的最小值也加上這個值 45 segTree[root*2+1].val += segTree[root].addMark; 46 segTree[root*2+2].val += segTree[root].addMark; 47 //傳遞后，當前節(jié)點標記域清空 48 segTree[root].addMark = 0; 49 } 50 } 51 52 /* 53 功能：線段樹的區(qū)間查詢 54 root：當前線段樹的根節(jié)點下標 55 [nstart, nend]: 當前節(jié)點所表示的區(qū)間 56 [qstart, qend]: 此次查詢的區(qū)間 57 */ 58 int query(int root, int nstart, int nend, int qstart, int qend) 59 { 60 //查詢區(qū)間和當前節(jié)點區(qū)間沒有交集 61 if(qstart > nend || qend < nstart) 62 return INFINITE; 63 //當前節(jié)點區(qū)間包含在查詢區(qū)間內(nèi) 64 if(qstart <= nstart && qend >= nend) 65 return segTree[root].val; 66 //分別從左右子樹查詢，返回兩者查詢結(jié)果的較小值 67 pushDown(root); //----延遲標志域向下傳遞 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 /* 75 功能：更新線段樹中某個區(qū)間內(nèi)葉子節(jié)點的值 76 root：當前線段樹的根節(jié)點下標 77 [nstart, nend]: 當前節(jié)點所表示的區(qū)間 78 [ustart, uend]: 待更新的區(qū)間 79 addVal: 更新的值（原來的值加上addVal） 80 */ 81 void update(int root, int nstart, int nend, int ustart, int uend, int addVal) 82 { 83 //更新區(qū)間和當前節(jié)點區(qū)間沒有交集 84 if(ustart > nend || uend < nstart) 85 return ; 86 //當前節(jié)點區(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); //延遲標記向下傳遞 94 //更新左右孩子節(jié)點 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ù)左右子樹的值回溯更新當前節(jié)點的值 99 segTree[root].val = min(segTree[root*2+1].val, segTree[root*2+2].val); 100 } 區(qū)間更新舉例說明：當我們要對區(qū)間[0,2]的葉子節(jié)點增加2，利用區(qū)間查詢的方法從根節(jié)點開始找到了非葉子節(jié)點[0-2]，把它的值設(shè)置為1+2 = 3，并且把它的延遲標記設(shè)置為2，更新完畢；當我們要查詢區(qū)間[0,1]內(nèi)的最小值時，查找到區(qū)間[0,2]時，發(fā)現(xiàn)它的標記不為0，并且還要向下搜索，因此要把標記向下傳遞，把節(jié)點[0-1]的值設(shè)置為2+2 = 4，標記設(shè)置為2，節(jié)點[2-2]的值設(shè)置為1+2 = 3，標記設(shè)置為2（其實葉子節(jié)點的標志是不起作用的，這里是為了操作的一致性），然后返回查詢結(jié)果：[0-1]節(jié)點的值4；當我們再次更新區(qū)間[0,1]（增加3）時，查詢到節(jié)點[0-1],發(fā)現(xiàn)它的標記值為2，因此把它的標記值設(shè)置為2+3 = 5，節(jié)點的值設(shè)置為4+3 = 7； 其實當區(qū)間更新的區(qū)間左右值相等時（[i,i]），就相當于單節(jié)點更新，單節(jié)點更新只是區(qū)間更新的特例。 求區(qū)間的最大值、區(qū)間求和等問題都是采用類似上面的延遲標記域。下面會通過acm的一些題目來運用一下線段樹。
等待更新...... 參考資料 GeeksforGeeks: http://www./segment-tree-set-1-range-minimum-query/ GeeksforGeeks: http://www./segment-tree-set-1-sum-of-given-range/ 懂得博客[數(shù)據(jù)結(jié)構(gòu)之線段樹]：http:///structure/segment-tree/ MetaSeed[數(shù)據(jù)結(jié)構(gòu)專題—線段樹]: http://blog.csdn.net/metalseed/article/details/8039326 NotOnlySuccess[完全版 線段樹]: http://www./index.php/segment-tree-complete/ 【版權(quán)聲明】轉(zhuǎn)載請注明出處：http://www.cnblogs.com/TenosDoIt/p/3453089.html |
|
|
， 
是樹的高度，但是這個空間復雜度也是O(n)的 ）。
