線段樹在算法中的應(yīng)用

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

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

3、該線段，線段數(shù)不超過1 + log(b (a + b)div2)，也不超過 log(b a)，成立。對于d = b的情況證明類似，不在贅述。在區(qū)間(a, b)中，對于任意線段也用歸納法證明。對于單位區(qū)間，最多分為一段，成立。若(a, b)的左兒子與右兒子均成立，則對于線段(c, d)若d= (a +b) div 2則該區(qū)間所分該線段等于其左兒子區(qū)間所分該線 段，線段數(shù)小于log(b (a + b)div2 a) (a + b) div 2則該區(qū)間所分該線段等于其右兒子區(qū)間所分該線 段，線段數(shù)小于log(b (a + b)div2) V.Lson.bi，分 該線段數(shù)不超過log(b (a + b

4、)div2)，而在右兒子區(qū)間分該線段滿足 c = V.Rson.a2，分該線段不超過log(b (a + b)div2 1)，所以在該 區(qū)間分該線段不超過2 log(b a)，成立。這個結(jié)論為線段數(shù)能在O(logL)的時間內(nèi)完成一條線段的插入、刪除、查找等工作提 供了理論依據(jù)。除了以上性質(zhì)，線段數(shù)還具有以下一些性質(zhì)：線段數(shù)是一個平衡樹，樹的高度為log N。任兩個結(jié)點(diǎn)要么是包含關(guān)系要么沒有公共部分，不可能重疊。給定一個葉子p，從根到p路徑上所有結(jié)點(diǎn)代表的區(qū)間都包含點(diǎn)p，且其它結(jié)點(diǎn)代 表的區(qū)間都不包含p。線段樹的基本存儲結(jié)構(gòu)和操作Lson為Left Son的縮寫，表示左兒子。Rson為Reft

5、Son的縮寫，表示右兒子。2.1線段數(shù)的基本存儲結(jié)構(gòu)線段數(shù)的一個結(jié)點(diǎn)的最基本存儲數(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分別表示該結(jié)點(diǎn)的左右端點(diǎn)，而mid則是中點(diǎn)。這樣就不需要在每次 再計算了。而lson和rson分別指向該結(jié)點(diǎn)的左兒子和右兒子，如果沒有，則為NULL。這只是線段樹結(jié)點(diǎn)的最基本結(jié)構(gòu)，在解決實(shí)際問題時，還需要根據(jù)實(shí)際情況添加各種需 要儲存的數(shù)據(jù)。如ZOJ1610 Count the Colors H

6、YPERLINK /onlinejudge/showProblem.do7problemCodeT610%ef%bc%8c%e6%9f%93%e8%89%b2%e9%97%ae%e9%a2%98%e3%80%82%e4%b8%8b%e6%96%87%e4%bc%9a%e5%85%b7%e4%bd%93%e8%ae%b2%e8%a7%a3%e3%80%82 /onlinejudge/showProblem.do7problemCodeT610，染色問題。下文會具體講解。中，我建立的線段樹結(jié)點(diǎn)結(jié)構(gòu)體如圖2-1-2所 示：struct tree（int l, r, col, mid;tree *lc

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

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

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

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

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

12、為0,則遞歸進(jìn)入此節(jié)點(diǎn)的左右子節(jié)點(diǎn)進(jìn)行刪除。而如果當(dāng)前節(jié)點(diǎn) 所代表的線段已被覆蓋，即cover值為1，則要考慮兩種情況。一是刪除的線段完 全覆蓋當(dāng)前節(jié)點(diǎn)所代表的線段，則將當(dāng)前節(jié)點(diǎn)的cover值置0。我們應(yīng)該遞歸的在當(dāng) 前節(jié)點(diǎn)的子樹上所有節(jié)點(diǎn)刪除線段。另一種情況是刪除的線段未完全覆蓋當(dāng)前節(jié)點(diǎn) 所代表的線段，比如當(dāng)前節(jié)點(diǎn)代表的線段為1,10)，而要刪除的線段為4,7)，則刪除 后剩下線段1,4)和7,10)，我們采用的方法是，將當(dāng)前節(jié)點(diǎn)的cover置0,并將其左 右子節(jié)點(diǎn)的cover置1，然后遞歸的進(jìn)入左右子節(jié)點(diǎn)進(jìn)行刪除。刪除操作的代碼如 bool del(int l, int r, int nu

13、m)(if (seg_treenum.left + 1 = seg_treenum.right)(/刪除到葉節(jié)點(diǎn)的情況int f = seg_treenum.f;seg_treenum.f = 0;return f;if (seg_treenum.f = 1)(當(dāng)前節(jié)點(diǎn)不為葉節(jié)點(diǎn)且被覆蓋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);elsereturn del(l, seg_treenum.mid, 2

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

15、信息，即從根節(jié)點(diǎn) 開始搜索整棵線段樹，如果當(dāng)前節(jié)點(diǎn)所代表的線段已被覆蓋，則將統(tǒng)計長度加上當(dāng) 前線段長度。否則，遞歸進(jìn)入當(dāng)前節(jié)點(diǎn)的左右子節(jié)點(diǎn)進(jìn)行統(tǒng)計。實(shí)現(xiàn)代碼圖2-2-4 所示：int cal(int num)(if (seg_treenum.f)return seg_treenum.right eg_treenum.left + 1;if (seg_treenum.left + 1 = seg_treenum.right)當(dāng)遍歷到葉節(jié)點(diǎn)時返回return 0;return cal(2 * num) + cal(2 * num + 1);(圖 2-2-4)小結(jié)：線段樹作為一種數(shù)據(jù)結(jié)構(gòu)只是解決問題

16、的一個工具，具體的使用方法則 非常靈活。以上介紹的僅僅為線段樹的基礎(chǔ)，在實(shí)際應(yīng)用中，需要針對待解的題目 設(shè)計節(jié)點(diǎn)存儲信息，以及修改維護(hù)操作等等。下面將由淺及深的介紹線段樹的一些 應(yīng)用，其中的一些線段樹使用方法值得思考和借鑒。線段樹的應(yīng)用舉例3.1染色問題問題鏈接： HYPERLINK /onlinejudge/showProblem.do?problemCode=1610 /onlinejudge/showProblem.do?problemCode=1610代碼鏈接： HYPERLINK http:/www.acmdiy.nct/code/u/XadillaX/ZJU/16104 http:

17、/www.acmdiy.nct/code/u/XadillaX/ZJU/1610 ACMDIY平臺為作者自主開發(fā)的一個在線代碼庫平臺。問題大意:輸入n個有色線段a,b，問最后每種顏色有多少連續(xù)段？(所有數(shù)字在0,8000 范圍內(nèi))解題思路：這里是一個結(jié)構(gòu)體：struct tree(int l, r, col, mid;tree *lc, *rc;l、r各代表左右端點(diǎn)，mid代表中點(diǎn)，col代表顏色。lc和rc各代表左 兒子和右兒子。1.創(chuàng)建線段樹取最小和最大的兩個數(shù)作為端點(diǎn)，建立線段樹。當(dāng)前節(jié)點(diǎn)的兩個端點(diǎn)值之差等于一時，此時該節(jié)點(diǎn)即位葉子節(jié)點(diǎn)，不 用再向下分。否則，分裂該節(jié)點(diǎn)為a，(a + b

18、) / 2, (a + b) / 2, b;創(chuàng)建線段樹時，注意初始化操作。2.線段樹著色(根據(jù)不同的題目此操作各不相同，對zju_1610做分析)當(dāng)前節(jié)點(diǎn)的顏色與將要涂的顏色color相同，直接return o當(dāng)前線段樹節(jié)點(diǎn)的兩個端點(diǎn)和要涂的兩個端點(diǎn)正好都相同，則將該節(jié) 點(diǎn)著為color，然后return。要涂的兩個端點(diǎn)在當(dāng)前節(jié)點(diǎn)的兩個端點(diǎn)之間時：先將當(dāng)前節(jié)點(diǎn)的顏色 向其子節(jié)點(diǎn)擴(kuò)展，然后：要涂的右端點(diǎn)小于或等于當(dāng)前節(jié)點(diǎn)middle = (a + b) / 2時，向左子 節(jié)點(diǎn)移動。要涂的左端點(diǎn)大于或等于當(dāng)前節(jié)點(diǎn)middle = (a + b) / 2時，向右子 節(jié)點(diǎn)移動。else (1，2)向左

19、右子節(jié)點(diǎn)移動。源代碼：/*File: p1610.cppAuthor: xadillax*Created on May 4, 2010, 7:20 PM*/#include #include #include #include #define NOCOL -1#define MULCOL -2using namespace std;struct tree(int l, r, col, mid;tree *lc, *rc;；tree *root;int n, l, r, col, i;int color8001, cnt8001;tree *init(int l, int r) 建立一棵線段樹t

20、ree *rst;rst = (tree *)malloc(sizeof(tree);rst-l = l, rst-r = r, rst-mid = (l + r) / 2, rst-col = 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);return rst;void put(tree *p, int l, int r, int col)if(p-l = l & p-r = r)p-col = col;return;

21、if(p-col != MULCOL)p-lc-col = p-col;p-rc-col = p-col;p-col = MULCOL;if(l mid & r p-mid)put(p-lc, l, p-mid, col);put(p-rc, p-mid, r, col);elseif(p-mid rc, l, r, col);else put(p-lc, l, r, col);void cal(tree *p, int *color)int i;if(p-col = MULCOL)cal(p-lc, color);cal(p-rc, color);elseif(p-col != NOCOL)

22、for(i = p-l; i r; i+) colori = p-col;elsefor(i = p-l; i r; i+) colori = NOCOL;free(p);int main()while(scanf(%d, &n) != EOF)root = init(0, 8000);memset(color, 0, sizeof(color);memset(cnt, 0, sizeof(cnt);while(n-)scanf(%d%d%d, &l, &r, &col);put(root, l, r, col);cal(root, color);if(color0 != NOCOL) cnt

23、color0+;for(i = 1; i = 7999; i+)if(colori != NOCOL & colori != colori - 1)cntcolori+;for(i = 0; i 0) printf(%d %dn, i, cnti);printf(n);return 0;3.2城市景觀問題鏈接：/JudgeOnline/problem?id=3277問題大意：如圖所示，在一條水平線上有N個建筑物，建筑物都是長方形的，且可以 互相遮蓋。給出每個建筑物的左右坐標(biāo)值A(chǔ)i,Bi以及每個建筑物的高度Hi， 需要計算出這些建筑物總共覆蓋的面積。題目數(shù)據(jù)范圍：建筑物個數(shù) N： 1 = N =

24、 40000建筑物左右坐標(biāo)值A(chǔ)i, Bi： 1 = Ai,Bi = 109建筑物的高度Hi： 1 = Hi = 109解題思路：因?yàn)閰^(qū)間最大到10的9次方，開這么大的空間內(nèi)存肯定不夠，所以要離散 化，用map存入然后用iterator遍歷得到的有序序列存入vector0然后以vector 的下標(biāo)建立線段樹，統(tǒng)計時若結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則它的值為左右孩子的值 之和，否則返回底*高。源代碼：5#include #include #include using namespace std;typedef struct nodint left,right,mid;long long h;bool cove

25、r;node,*nd;typedef struct plong long start,end,hi;point;/元素個數(shù)上限和存儲數(shù)組const int MAX_NUM=200000;第一次交 re,干脆開個大的node seg_tree3*MAX_NUM+1;point list40005;5此源代碼來自文獻(xiàn)參考中的第七項(xiàng)。 map my_map;map:iterator it;vector vec;/創(chuàng)建,l為左端點(diǎn)，r為右端點(diǎn)，num為在數(shù)組中的編號void make(int l,int r,int num)seg_treenum.left=l;seg_treenum.right=r;

26、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 & seg_treenum.right=r )if(seg_treenum.hhi) seg_treenum.h=hi;return ;if( r=seg_treenum.mid )Insert(l,r

27、,2*num+1,hi);elseInsert(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_treenum.right )return seg_treenum.h*( vec seg_treenum.right - vec seg_treenum.left );return cal( seg_treen

28、um.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從下標(biāo)1開始有效for( it=my_map.begin(); it!=my_map.end();+it ) it-second=t+;vec.push_back( it-first );一vec.push_back

29、( 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;線段樹的應(yīng)用總結(jié)線段樹是一種高效的數(shù)據(jù)結(jié)構(gòu)。它的思想就是分治，非?；疽卜浅?qiáng)大。在學(xué)習(xí)線段 樹的過程中，要時刻記住，線段樹只是一種解題的工具，學(xué)習(xí)線段樹只是學(xué)習(xí)一種解題的思 維，就像圖論中的BFS6 一樣。至于在具體的題目中如何去

30、運(yùn)用這個工具，則靈活的去建 樹并維護(hù)相關(guān)信息。這也需要在平時進(jìn)行積累，做題時才能應(yīng)用熟練。線段樹的練習(xí)題目推薦以下題目是各oj上比較有名的線段樹題目Whu OnlineJudge HYPERLINK /oak /oak題目號：1071 1224 1361 1344Pku OnlineJudge HYPERLINK /JudgeOnline /JudgeOnline題目號 3225 2482 1177 1029 2182 2750 2104 2528 2828 2777 2886 2761Zju OnlineJudge HYPERLINK 題目號 2301 1128 1659 2112參考文獻(xiàn)岳

31、云濤.淺談線段數(shù)在信息學(xué)競賽中的應(yīng)用J.林濤.線段數(shù)的應(yīng)用J,2004.劉汝佳，黃亮.算法藝術(shù)與信息學(xué)競賽M.北京：清華大學(xué)出版社，2004.Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest et al. Introduction to AlgorithmsM. 2nd Edition. America: The MIT Press, 2001.廖勁宇.pku 3277 （線段樹+離散化）OL. HYPERLINK /liaojinyu282/archive/2010/01/16/5200521.aspx /liaojinyu282/archive/2010/01/16/5200521.aspx, 2010.朱凱迪.ZOJ1610 Count the ColorsOL.