線段樹在算法中的應用朱凱迪

1、線段樹在算法中的應用作者：朱凱迪作者單位：寧波工程學院Email:摘 要： 計算機信息學競賽中出現(xiàn)了越來越多的統(tǒng)計，查找，規(guī)劃，排序，染色等等的題目。平衡二叉樹和線段樹是兩種最常見的解決此類問題的數(shù)據(jù)結(jié)構(gòu)?？墒瞧胶舛鏄溆幸粋€缺點，就是變成復雜度很高。我們可以看到在某些題目中，線段樹是它的有力替代品。這篇論文主要介紹了線段樹的操作，優(yōu)化以及應用。該論文也會系統(tǒng)地介紹染色問題使用線段樹的一般解法。關(guān)鍵詞：線段樹 數(shù)據(jù)結(jié)構(gòu) 信息學 算法1. 線段樹的定義及特征一棵二叉樹，記為T(a, b)，參數(shù)a, b表示該結(jié)點表示的區(qū)間a, b。區(qū)間長度b-a記為L。遞歸定義Ta,

2、b：若L1：a, (a + b) div 2為T的左兒子 (a + b) div 2, b為T的右兒子。若L=1：T為一個葉子結(jié)點。表示區(qū)間1, 10的線段樹表示如圖1-1所示：(圖1-1)定理1：線段樹把區(qū)間任意一條線段都分成不超過條線段。證明： 在區(qū)間(a, b)中，對于線段(c, d)，如果(c = b)，那么線段在(a, b)中被分為不超過。用歸納法證明，如果是單位區(qū)間，最多被分為一段，成立。如果區(qū)間(a, b)的左兒子與右兒子成立，那么如果當c = a時，1 若d (a + b) div 2那么相當于該線段被分為它左兒子表示的線段，加上右兒子分該線段，線段數(shù)不超過，也不超過，成立。對

3、于d = b的情況證明類似，不在贅述。 在區(qū)間(a, b)中，對于任意線段也用歸納法證明。對于單位區(qū)間，最多分為一段，成立。若(a, b)的左兒子與右兒子均成立，則對于線段(c, d)1 若d (a + b) div 2則該區(qū)間所分該線段等于其右兒子區(qū)間所分該線段，線段數(shù)小于，成立。3 若1、2均不成立，則此線段在左兒子區(qū)間分該線段滿足d V.Lson.b Lson為Left Son的縮寫，表示左兒子。，分該線段數(shù)不超過，而在右兒子區(qū)間分該線段滿足c = V.Rson.a Rson為Reft Son的縮寫，表示右兒子。，分該線段不超過，所以在該區(qū)間分該線段不超過，成立。這個結(jié)論為線段數(shù)能在的時

4、間內(nèi)完成一條線段的插入、刪除、查找等工作提供了理論依據(jù)。除了以上性質(zhì)，線段數(shù)還具有以下一些性質(zhì)：l 線段數(shù)是一個平衡樹，樹的高度為。l 任兩個結(jié)點要么是包含關(guān)系要么沒有公共部分，不可能重疊。l 給定一個葉子p，從根到p路徑上所有結(jié)點代表的區(qū)間都包含點p，且其它結(jié)點代表的區(qū)間都不包含p。2. 線段樹的基本存儲結(jié)構(gòu)和操作2.1 線段數(shù)的基本存儲結(jié)構(gòu)線段數(shù)的一個結(jié)點的最基本存儲數(shù)據(jù)結(jié)構(gòu)如圖2-1-1所示：struct Seg int left, right, mid; Seg *lson, *rson;(圖2-1-1)也可以用數(shù)組模擬二叉樹，則結(jié)構(gòu)體中不需要兩個指針變量。其中l(wèi)eft和right分別

5、表示該結(jié)點的左右端點，而mid則是中點。這樣就不需要在每次再計算了。而lson和rson分別指向該結(jié)點的左兒子和右兒子，如果沒有，則為NULL。這只是線段樹結(jié)點的最基本結(jié)構(gòu)，在解決實際問題時，還需要根據(jù)實際情況添加各種需要儲存的數(shù)據(jù)。如ZOJ1610 Count the Colors /onlinejudge/showProblem.do?problemCode=1610，染色問題。下文會具體講解。中，我建立的線段樹結(jié)點結(jié)構(gòu)體如圖2-1-2所示：struct tree int l, r, col, mid; tree *lc, *rc;(圖2-1-2)其

6、中l(wèi), r各代表左右端點，mid代表中點，col代表顏色。lc和rc各代表左兒子和右兒子。2.2 線段數(shù)的基本操作2.2.1 線段樹的建立操作在對線段樹進行操作前，我們需要建立起線段樹的結(jié)構(gòu)。我們使用結(jié)構(gòu)體數(shù)組來保存線段樹，這樣對于非葉節(jié)點，若它在數(shù)組中編號為 num，則其左右子節(jié)點的編號為 2 * num，2 * num + 1。由于線段樹是二分的樹型結(jié)構(gòu)，我們可以用遞歸的方法，從根節(jié)點開始來建立一棵線段樹。代碼如圖2-2-1所示：node seg_tree3 * MAXN; /由線段樹的性質(zhì)可知，建樹所需要的空間大概是所需處理最長線段長度的 2 倍多，所以需要開 3 倍大小的數(shù)組 void

7、 make(int l, int r, int num)/l,r 分別為當前節(jié)點的左右端點，num為節(jié)點在數(shù)組中的編號 seg_treenum.left = l; seg_treenum.right = r; seg_treenum.mid = (l + r) / 2; if (l + 1 != r) /若不為葉子節(jié)點，則遞歸的建立左右子樹 make(l, seg_treenum.mid, 2 * num); make(seg_treenum.mid, r, 2 * num + 1); (圖2-2-1)對應不同的題目，我們會在線段樹節(jié)點中添加另外的數(shù)據(jù)域，并隨著線段的插入或刪除進行維護，要注意

8、在建樹過程中將這些數(shù)據(jù)域初始化。2.2.2 線段樹的插入操作為了在插入線段后，我們能知道哪些節(jié)點上的線段被插入（覆蓋）過。我們需要在節(jié)點中添加一個cover域，來記錄當前節(jié)點所表示的線段是否被覆蓋。這樣，在建樹過程中，我們需要把每個節(jié)點的cover 域置 0；在線段的插入過程中，我們從根節(jié)點開始插入，同樣采取遞歸的方法。如果插入的線段完全覆蓋了當前節(jié)點所代表的線段，則將當前節(jié)點的 cover 域置 1 并返回。否則，將線段遞歸進入當前節(jié)點的左右子節(jié)點進行插入。代碼圖2-2-2所示。void insert(int l, int r, int num) /l,r 分別為插入當前節(jié)點線段的左右端點，

9、num為節(jié)點在數(shù)組中的編號 if (seg_treenum.left = l & seg_treenum.right = r)/若插入的線段完全覆蓋當前節(jié)點所表示的線段 seg_treenum.cover = 1; return; if (r = seg_treenum.mid) /當前節(jié)點的右子節(jié)點所代表的線段包含插入的線段 insert(l, r, 2 * num +1); else /插入的線段跨越了當前節(jié)點所代表線段的中點 insert(l, seg_treenum.mid, 2 * num); insert(seg_treenum.mid, r, 2 * num + 1); (圖2-

10、2-2)要注意，這樣插入線段時，有可能出現(xiàn)以下這種情況，即先插入線段1,3)，再插入線段1,5)。這樣，代表線段1,3)的節(jié)點以及代表線段1,5)的節(jié)點的 cover 值均為 1，但是在統(tǒng)計時，遇到這種情況，我們可以只統(tǒng)計更靠近根節(jié)點的節(jié)點，因為這個節(jié)點所代表的線段包含了其子樹上所有節(jié)點所代表的線段。 2.2.3 線段樹的刪除操作線段樹的刪除操作跟插入操作不大相同，因為一條線段只有被插入過才能被刪除。比如插入一條線段3,10)，則只能刪除線段4,6)，不能刪除線段7,12)。當刪除未插入的線段時，操作返回 false 值。 我們一樣采用遞歸的方法對線段進行刪除，如果當前節(jié)點所代表的線段未被覆蓋

11、，即 cover 值為 0，則遞歸進入此節(jié)點的左右子節(jié)點進行刪除。而如果當前節(jié)點所代表的線段已被覆蓋，即 cover 值為 1，則要考慮兩種情況。一是刪除的線段完全覆蓋當前節(jié)點所代表的線段，則將當前節(jié)點的cover值置0。我們應該遞歸的在當前節(jié)點的子樹上所有節(jié)點刪除線段。另一種情況是刪除的線段未完全覆蓋當前節(jié)點所代表的線段，比如當前節(jié)點代表的線段為1,10)，而要刪除的線段為4,7)，則刪除后剩下線段1,4)和7,10)，我們采用的方法是，將當前節(jié)點的cover置0，并將其左右子節(jié)點的 cover置 1，然后遞歸的進入左右子節(jié)點進行刪除。 刪除操作的代碼如圖2-2-3所示：bool del(i

12、nt l, int r, int num) if (seg_treenum.left + 1 = seg_treenum.right) /刪除到葉節(jié)點的情況 int f = seg_treenum.f; seg_treenum.f = 0; return f; if (seg_treenum.f = 1) /當前節(jié)點不為葉節(jié)點且被覆蓋 seg_treenum.f = 0; seg_tree2 * num.f = 1; seg_tree2 * num + 1.f = 1; if (r = seg_treenum.mid) return del(l, r, 2 * num + 1); else r

13、eturn del(l, seg_treenum.mid, 2 * num) & del(seg_treenum.mid, r, 2 * num + 1); 圖2-2-3相對插入操作，刪除操作比較復雜，需要考慮的情況很多，稍有不慎就會出錯，在比賽中寫刪除操作時務必聯(lián)系插入操作的實現(xiàn)過程，仔細思考，才能避免錯誤。2.2.4 線段樹的統(tǒng)計操作對應不同的問題，線段樹會統(tǒng)計不同的數(shù)據(jù)，比如線段覆蓋的長度，線段覆蓋連續(xù)區(qū)間的個數(shù)等等。其實現(xiàn)思路不盡相同，我們以下以統(tǒng)計線段覆蓋長度為例，簡要介紹線段樹統(tǒng)計信息的過程。文章之后的章節(jié)會講解一些要用到線段樹的題目，并會詳細介紹線段樹的用法，以及各種信息的統(tǒng)計過

14、程。 對于統(tǒng)計線段覆蓋長度的問題，可以采用以下的思路來統(tǒng)計信息，即從根節(jié)點開始搜索整棵線段樹，如果當前節(jié)點所代表的線段已被覆蓋，則將統(tǒng)計長度加上當前線段長度。否則，遞歸進入當前節(jié)點的左右子節(jié)點進行統(tǒng)計。實現(xiàn)代碼圖2-2-4所示：int cal(int num) if (seg_treenum.f) return seg_treenum.right seg_treenum.left + 1; if (seg_treenum.left + 1 = seg_treenum.right) /當遍歷到葉節(jié)點時返回 return 0; return cal(2 * num) + cal(2 * num +

15、 1); (圖2-2-4)小結(jié)：線段樹作為一種數(shù)據(jù)結(jié)構(gòu)只是解決問題的一個工具，具體的使用方法則非常靈活。以上介紹的僅僅為線段樹的基礎，在實際應用中，需要針對待解的題目設計節(jié)點存儲信息，以及修改維護操作等等。下面將由淺及深的介紹線段樹的一些應用，其中的一些線段樹使用方法值得思考和借鑒。3. 線段樹的應用舉例3.1 染色問題問題鏈接：/onlinejudge/showProblem.do?problemCode=1610代碼鏈接：/code/u/XadillaX/ZJU/1610 ACMDIY平臺為作者自主開發(fā)的一個在

16、線代碼庫平臺。問題大意：輸入n個有色線段a,b，問最后每種顏色有多少連續(xù)段？（所有數(shù)字在0,8000范圍內(nèi)）解題思路：這里是一個結(jié)構(gòu)體：struct treeint l, r, col, mid;tree *lc, *rc;l、r各代表左右端點，mid代表中點，col代表顏色。lc和rc各代表左兒子和右兒子。1. 創(chuàng)建線段樹1) 取最小和最大的兩個數(shù)作為端點，建立線段樹。2) 當前節(jié)點的兩個端點值之差等于一時，此時該節(jié)點即位葉子節(jié)點，不用再向下分。3) 否則，分裂該節(jié)點為a，(a + b) / 2, (a + b) / 2, b;4) 創(chuàng)建線段樹時，注意初始化操作。2. 線段樹著色（根據(jù)不同的

17、題目此操作各不相同，對zju_1610做分析）1) 當前節(jié)點的顏色與將要涂的顏色color相同，直接return。2) 當前線段樹節(jié)點的兩個端點和要涂的兩個端點正好都相同，則將該節(jié)點著為color，然后return。3) 要涂的兩個端點在當前節(jié)點的兩個端點之間時：先將當前節(jié)點的顏色向其子節(jié)點擴展，然后： 要涂的右端點小于或等于當前節(jié)點middle = (a + b) / 2時，向左子節(jié)點移動。 要涂的左端點大于或等于當前節(jié)點middle = (a + b) / 2時，向右子節(jié)點移動。 else （1 ，2）向左右子節(jié)點移動。源 代 碼：/*File:p1610.cpp*Author:xadil

18、lax*CreatedonMay4,2010,7:20PM*/#include#include#include#include#defineNOCOL-1#defineMULCOL-2usingnamespacestd;structtreeintl,r,col,mid;tree*lc,*rc;tree*root;intn,l,r,col,i;intcolor8001,cnt8001;tree*init(intl,intr)/建立一棵線段樹tree*rst;rst=(tree*)malloc(sizeof(tree);rst-l=l,rst-r=r,rst-mid=(l+r)/2,rst-col

19、=NOCOL;if(r-l=1)rst-lc=NULL;rst-rc=NULL;elserst-lc=init(rst-l,rst-mid);rst-rc=init(rst-mid,rst-r);returnrst;voidput(tree*p,intl,intr,intcol)if(p-l=l&p-r=r)p-col=col;return;if(p-col!=MULCOL)p-lc-col=p-col;p-rc-col=p-col;p-col=MULCOL;if(lmid&rp-mid)put(p-lc,l,p-mid,col);put(p-rc,p-mid,r,col);elseif(p-

20、midrc,l,r,col);elseput(p-lc,l,r,col);voidcal(tree*p,int*color)inti;if(p-col=MULCOL)cal(p-lc,color);cal(p-rc,color);elseif(p-col!=NOCOL)for(i=p-l;ir;i+)colori=p-col;elsefor(i=p-l;ir;i+)colori=NOCOL;free(p);intmain()while(scanf(%d,&n)!=EOF)root=init(0,8000);memset(color,0,sizeof(color);memset(cnt,0,si

21、zeof(cnt);while(n-)scanf(%d%d%d,&l,&r,&col);put(root,l,r,col);cal(root,color);if(color0!=NOCOL)cntcolor0+;for(i=1;i=7999;i+)if(colori!=NOCOL&colori!=colori-1)cntcolori+;for(i=0;i0)printf(%d%dn,i,cnti);printf(n);return0;3.2 城市景觀問題鏈接：/JudgeOnline/problem?id=3277問題大意：如圖所示，在一條水平線上有 N

22、個建筑物，建筑物都是長方形的，且可以互相遮蓋。給出每個建筑物的左右坐標值Ai,Bi 以及每個建筑物的高度Hi，需 要計算出這些建筑物總共覆蓋的面積。題目數(shù)據(jù)范圍： 建筑物個數(shù) N：1 = N = 40000 建筑物左右坐標值Ai, Bi：1 = Ai,Bi = 109 建筑物的高度 Hi：1 = Hi = 109解題思路：因為區(qū)間最大到10的9次方，開這么大的空間內(nèi)存肯定不夠，所以要離散化，用map存入然后用iterator遍歷得到的有序序列存入vector。然后以vector的下標建立線段樹，統(tǒng)計時若結(jié)點不是葉子結(jié)點，則它的值為左右孩子的值之和，否則返回 底*高 。源 代 碼： 此源代碼來自

23、文獻參考中的第七項。#include #include #include using namespace std;typedef struct nod int left,right,mid;long long h;bool cover;node,*nd;typedef struct plong long start,end,hi;point;/ 元素個數(shù)上限和存儲數(shù)組const int MAX_NUM=; /第一次交re,干脆開個大的node seg_tree3*MAX_NUM+1;point list40005;map my_map;map:iterator it;vector vec;/

24、創(chuàng)建 , l為左端點，r為右端點，num為在數(shù)組中的編號void make(int l,int r,int num)seg_treenum.left=l;seg_treenum.right=r;seg_treenum.h=0;seg_treenum.mid= (l+r)/2;if( l+1 != r )make(l,seg_treenum.mid,2*num);make(seg_treenum.mid,r,2*num+1);/ 插入操作，參數(shù)意義同上void Insert(int l,int r,int num ,long long &hi)if( seg_treenum.left=l & s

25、eg_treenum.right=r )if(seg_treenum.hhi) seg_treenum.h=hi;return ;if( r=seg_treenum.mid )Insert(l,r,2*num+1,hi);else Insert(l,seg_treenum.mid,2*num,hi);Insert(seg_treenum.mid,r,2*num+1,hi);/統(tǒng)計操作long long cal(long long hi,int num)if(hiseg_treenum.h) seg_treenum.h=hi;if( seg_treenum.left+1 = seg_treenu

26、m.right )return seg_treenum.h*( vec seg_treenum.right - vec seg_treenum.left );return cal( seg_treenum.h , 2*num ) + cal( seg_treenum.h , 2*num+1 );int main()int T,t=1;cinT;long long a,b,h;for(int i=0;iabh;my_mapa=0;my_mapb=0;listi.start=a; listi.end=b; listi.hi=h;vec.push_back(0); /壓入一個元素使vec從下標1開始

27、有效for( it=my_map.begin(); it!=my_map.end();+it )it-second=t+;vec.push_back( it-first );vec.push_back( vecvec.size()-1 +1 ); /將離散化之后的元素按順序壓入向量make(1,my_map.size()+1,1);for(int i=0;iT;+i)Insert( my_map listi.start , my_map listi.end ,1 , listi.hi );coutcal( seg_tree1.h ,1 )endl;return 0;4. 線段樹的應用總結(jié)線段樹

28、是一種高效的數(shù)據(jù)結(jié)構(gòu)。它的思想就是分治，非?；疽卜浅姶蟆Ｔ趯W習線段樹的過程中，要時刻記住，線段樹只是一種解題的工具，學習線段樹只是學習一種解題的思維，就像圖論中的 BFS 廣度優(yōu)先搜索，俗稱暴力搜索。 一樣。至于在具體的題目中如何去運用這個工具，則靈活的去建樹并維護相關(guān)信息。這也需要在平時進行積累，做題時才能應用熟練。5. 線段樹的練習題目推薦 以下題目是各 OJ 上比較有名的線段樹題目 Whu OnlineJudge /oak 題目號： 1071 1224 1361 1344 Pku OnlineJudge

29、/JudgeOnline 題目號 3225 2482 1177 1029 2182 2750 2104 2528 2828 2777 2886 2761 Zju OnlineJudge 題目號 2301 1128 1659 2112參考文獻1岳云濤.淺談線段數(shù)在信息學競賽中的應用J.2林濤.線段數(shù)的應用J,2004.3劉汝佳, 黃亮.算法藝術(shù)與信息學競賽M. 北京：清華大學出版社，2004.4Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest et al. Introduction to AlgorithmsM. 2nd Edition. America: The MIT Press, 2001.5廖勁宇. pku 3277 (線段樹+離散化)OL. /liaojinyu282/archive/2010/01/16/.aspx, 2010.6朱凱迪. ZOJ1610 Cou