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