1、線前在信息學競賽中或是數列對數軸上的一個區間或是數列中的連續若干個進行一種相同的處理（見下面的例 1常規的做法一般依托于線性表這種數據結構，導致了處理只能針對各個元素逐個進行，因此算法的效率較低。顆粒度偏小了線是一種能夠有效處理區間操作的高級數據結構，利用這種數據結構能夠計出針對上述問題的更加高效的算法。本文主要介紹線與 RMQ、樹狀數組、平衡樹的異同一？例：有一列數，初始值全部為，每次可以進行以下三種操作中的一種：與樹狀數組的應用實例對比線前在信息學競賽中或是數列對數軸上的一個區間或是數列中的連續若干個進行一種相同的處理（見下面的例 1常規的做法一般依托于線性表這種數據結構，導致了處理只能針

2、對各個元素逐個進行，因此算法的效率較低。顆粒度偏小了線是一種能夠有效處理區間操作的高級數據結構，利用這種數據結構能夠計出針對上述問題的更加高效的算法。本文主要介紹線與 RMQ、樹狀數組、平衡樹的異同一？例：有一列數，初始值全部為，每次可以進行以下三種操作中的一種：與樹狀數組的應用實例對比給指定區間將指定區間的值詢問一個區間上的最小值、最大值、所有數的和在最樸素的模擬算法中， 通常用線性表過程中，假設這個數列的長度為n整體的時間復雜度為 O(mn)的時間復雜度為當 m及n比較小時，這無疑是一個不錯的策略。但是，如果m與 n的值比較大，則個算法顯然就太低效了這個算法低效的一個重要原因就是：所有都是

3、針對元素的，而題目中所有的所以假的優化也就應該從這里入手。總之：區間操作、宏觀化設計一種數據結構，能夠直所需處理的區間，那么，就能更加有效線需要處理的區間不相交地分成若干個小都可以在這樣一些分解后的區間上進行，并且查詢的時候也能夠根據些被分解了的區間上的信息，合并出整個詢問區間上的查詢結果。分治二線的結構 將區間分解 11的線段稱為元線段定義 2，當且僅當這棵樹滿足如下條件ab；樹中的結點是葉子結點，當且僅當它所代表的線段是元線段；a,(+)/2樹樹根對應線段(+)/2b。1是一棵二叉樹，樹中的每一個結點都表示了一個區間a,b。每一葉子結點上 a+1=b，這表示了一個初等區間對于每一結點 b-

4、a1，設根為a,b的（子）為 T(a,b)，則進一步此分為左子樹 T(a,(a+b)/2)，以及右子樹 T(a+b)/2,b)，直為一個等區間時為止。的結構是遞歸定義的。舉一個例子，比如 T(1,10)是一棵二叉樹，樹中的每一個結點都表示了一個區間a,b。每一葉子結點上 a+1=b，這表示了一個初等區間對于每一結點 b-a1，設根為a,b的（子）為 T(a,b)，則進一步此分為左子樹 T(a,(a+b)/2)，以及右子樹 T(a+b)/2,b)，直為一個等區間時為止。的結構是遞歸定義的。舉一個例子，比如 T(1,10)通常更加常用的是需要對數這時通常將區間a,b分解為a,(a+b)/2和(a+

5、b)/2+1,b 將前面的的那棵轉化為這種新的表示方法后，得到的圖暫略，見通常，后一種的定義形式更加常見三線性質 1：長度范圍為1,L的深度不超過 log2(L-1)+13上的結點個數不超過 2log2L把區間上的任意一條長度為 L的線段都分成不超過 2log2L四線方1、鏈表實現structLeft,Node*LeftChild,或2er=node; node = recordleft,leftchild,rightchild:2、使用數組模擬Left,Right,LeftChild,3、利用“除了最底一層外為滿二叉樹”的性質，可以使用類似二叉堆方式根結號單元中在1i號單元在左孩在i*2孩在

6、4、上面第3er=node; node = recordleft,leftchild,rightchild:2、使用數組模擬Left,Right,LeftChild,3、利用“除了最底一層外為滿二叉樹”的性質，可以使用類似二叉堆方式根結號單元中在1i號單元在左孩在i*2孩在4、上面第3最底一層的結點可能很空，但是方式的改進的葉結點有 L=r可以使用這樣方式：對于區間L，r在(L+rLogicordiff(Lr)號單元中，其中是判斷兩個數是否相等的函數。若 L=r 則返回 0，否則返回 1與此類似，對于到了區間L*2,r*2的第一種表示方法，即葉結點 可以使用函數logicandequal(l+

7、l,r)，這里equal五線的基本操作及實線是遞歸定義的，因此的所有操作也都是遞歸的1、線【Cvoidbuild(Nodecur-Left = L; cur-Right=r; if (L!=r)cur-LeftChild = new Node; cur-RightChild=newNode;build(cur-LeftChild,L,build(cur-RightChild,(L+r)/2+1, cur-LeftChild=cur-Rightchild=【Pascalprocedurebuild(cur:Node;L,3cur.Left := L; cur.Right:=r; if Lr th

8、ennew( cur.LeftChild ); new(cur.RightChild);build(cur.LeftChild,L,build(cur.RightChild,(L+r)/2+1, cur.LeftChild := nil; cur.Rightchild:=nil;在這個過程中按照間為元區間時為cur.Left := L; cur.Right:=r; if Lr thennew( cur.LeftChild ); new(cur.RightChild);build(cur.LeftChild,L,build(cur.RightChild,(L+r)/2+1, cur.LeftCh

9、ild := nil; cur.Rightchild:=nil;在這個過程中按照間為元區間時為止，直到分解到待構造【C問題：查詢什么東西？根據什么條件查詢？是 L、R 嗎？一般會怎voidquery(Noder)Node*LC=cur-LeftChild,*RC=cur-if(LLeft)&(cur-RightLeft,cur-if(LLeft+cur-Right)/2) if(r(cur-Left+cur-【Pascalprocedurequery(cur:node;L,r: var LC, RC: node;:=:=(L=cur.Left)and(cur.Right=r)LR覆蓋了現有區間

10、n(cur.Left,4if(L (cur.Left + cur.Right)/2) then query(RC,L,r);這里的查詢操作其實并將查詢區間進行分的過程。如果當前結點表示的區間包含于分解出的區間之一則，根據查詢區間與當前區間的關系有的時候，兩邊都要遞歸處理，但是這種情況不會經常發生，因為線質保證了這種分解的結果不會超過lgL。3六線的方在具體問題中，必須要根據問題的需要一些信息來幫解if(L (cur.Left + cur.Right)/2) then query(RC,L,r);這里的查詢操作其實并將查詢區間進行分的過程。如果當前結點表示的區間包含于分解出的區間之一則，根據查詢

11、區間與當前區間的關系有的時候，兩邊都要遞歸處理，但是這種情況不會經常發生，因為線質保證了這種分解的結果不會超過lgL。3六線的方在具體問題中，必須要根據問題的需要一些信息來幫解上幾類常用根據應用問題的實例這首先看例 1 的一個弱化版，就是假每次的修改操作只能針對一個元進行，而詢問仍然是針對區間進行的為了達到這樣的目的需/sum、minmax上對元素進行修改 與樹狀數組比較 x的元素修改成num【Cvoidupdate(NodeNode*LC=cur-LeftChild,*RC=cur-if(cur-Left=cur-Right) 無num?以區間為粒度信息cur-min=cur-max if(

12、xsum=+cur-Right)/2) C,x,if(x(cur-+cur-update(RC,x,=LC-LC-RC- 匯總更新后來自左、右子樹的信?RC-【Pascalprocedureupdate(cur:Node;x,num: LC,RC:Node; LC:=RC:=5ifcur.Left=cur.Rightthen信ifx(cur.Left+cur.Right)/2C,ifcur.Left=cur.Rightthen信ifx(cur.Left+cur.Right)/2C,x,update(RC,x,cur.sum:=LC.sum+匯總更新后來自左、右子樹的信cur.min:=cur.

13、max=max LC.min,RC.minLC.max,RC.max這個遞歸過程展示了將上位置為 x的元素修改成 num的過程。因為這里是針max、min域都修改為num的值它的sum之后，因為這個變動，所有包含 x 移就可以了。上對區間進行查查詢什么？ 查詢當前區間的sum【Cquerysum(NodeNode*LC=cur-Leftchild,*RC=cur-ret=if(LLeft)&(cur-Rightsum;elseif(LLeft+cur-Right)/2) ret += querysum(LC,L,r);if(r(cur-Left+cur-Right)/2) ret += que

14、rysum(RC,L,r);return【Pascalfunctionquerysum(curNode;L,6LC,RC:LCRCret:=if(L=cur.Left)and(cur.Right=r)then ret := ret + cur.sum;ifL=(cur.Left+cur.Right)div2then ret := ret + querysum(LC,L,r);LC,RC:LCRCret:=if(L=cur.Left)and(cur.Right=r)then ret := ret + cur.sum;ifL(cur.Left+cur.Right)div2then ret := r

15、et + querysum(RC,L,r);returnret; 這個過程是查詢區間L,r已經對，這里只要套用前面區間分解的過程，進行一些小小的改動，將所有被分解求最大值與最小值的過程與此類似，在此不再寫出考慮到的高度是 log2L，每個查詢區間的分解不超過 2log2L個，因此，上面兩個過程的時間復雜度都是 O(log2L)，也就是說，利用這種數據結獲得一個比樸素算法更加高效的算法。 分解、分治 處理的顆粒度 前的修改操作還都是基于元素的，但是，例 1 上利用仍然能夠完成這樣的操作，只不過這樣會更加復雜一些們可以在這些分解出來的區間上進行標記，但是與前面介紹的情況不同，另一個查詢區間分解后包

16、括一個在當前區間子孫中的區間，那么，這個響能處理的會再對后續的結點產生影響了遲標記（lazy-tag）的技術就應運而生了7延遲標記的本意是希望把這種標記（如各種的信息，在此稱為標記）全部打在葉結上，這樣查詢起來就會很輕松。但是，如果每都將這種標顯然于是的初衷是相違背的還是按照最初的設計，將標記打在區間上。或查過程中處理傳遞給它的兩個子結點這樣就不需要考慮自根結點開始的影響了，并且，致整體處理的時間復雜度仍然能維持在 O(log2L)的水平上以下為這項技術在引例中的具體應用3延遲標記的本意是希望把這種標記（如各種的信息，在此稱為標記）全部打在葉結上，這樣查詢起來就會很輕松。但是，如果每都將這種標

17、顯然于是的初衷是相違背的還是按照最初的設計，將標記打在區間上。或查過程中處理傳遞給它的兩個子結點這樣就不需要考慮自根結點開始的影響了，并且，致整體處理的時間復雜度仍然能維持在 O(log2L)的水平上以下為這項技術在引例中的具體應用3、對一個區間整體加上一個/ 將區間L,r整體加上一個數 有無運用“延voidupdate(NodeNode*LC=cur-LeftChild,*RC=cur-if(LLeft)&(cur-Rightdelta += delta;elseif(LLeft+cur-C,L, r,if(r(cur-Left+cur-update(RC,L,r,cur-sum+=LC-s

18、umcur-sum+=RC-sumLC-delta*(LC-RC-delta*(RC-LC-RC-+/ xvoidinsert(Node有無運用Node*LC=cur-LeftChild,*RC=cur-if(cur-Left=cur-cur-sum =cur-deltaLC-delta+= RC-delta+= cur-deltacur-8if(xLeft+cur-Right)/2) insert(LC, x, num);if(x(cur-Left+cur-Right)/2) insert(RC, x, num);cur-sum=LC-sum+LC-delta*(LC-RightLC-Lef

19、t+cur-sum+=RC-sumif(xLeft+cur-Right)/2) insert(LC, x, num);if(x(cur-Left+cur-Right)/2) insert(RC, x, num);cur-sum=LC-sum+LC-delta*(LC-RightLC-Left+cur-sum+=RC-sum+RC-delta*(RC-RightRC-Left/ 查詢區間L,r上所有元素的querysum(NodeNode*LC=cur-LeftChild, ret = 0;*RC=cur-if(Lsum+(cur-Rightcur-Left+1)*cur-delta; cur-

20、delta = 0;if(LLeft+cur-Right)/2) ret += querysum(LC, x, num);if(r(cur-Left+cur-Right)/2) ret += querysum(RC, x, num);cur-sum = LC-sum + LC-delta * (LC-Right LC-Left + 1); cur-sum+=RC-sum+RC-delta*(RC-RightRC-Left+1);return4、將一個區間整體置為一個額外兩個域data和en。en表示一個區間是否為一的數。若en有效data這里父結點的 en 與 data 對子結點也有影響，但是

21、，這種影響與delta 就不完全同了eta的影響是可以從根結點開始下降，一路累加到當前（子）結點的；上面提到的這種n域與aa掉有子結點的信息，使它們都成為無效狀態。 什么意思？兩者不同也可以使用“延遲標記”技術來（優化）/ 9如了 en calcsum(Nodeif(cur-ruturn(cur-Rightcur-Left+1)*cur-data; return cur-sum;如了 en calcsum(Nodeif(cur-ruturn(cur-Rightcur-Left+1)*cur-data; return cur-sum;void insert(Node *cur,Node*LC=c

22、ur-LeftChild,*RC=cur-if(cur-Left=cur-Right) cur-sum = num;/*cur-en=false; if(cur-LC-data=RC-ur-LC-en=RC-en=cur-en=if(xLeft+cur-Right)/2) insert(LC, x, num);if(x(cur-Left+cur-Right)/2) insert(RC, x, num);cur-sum=calcsum(LC)+/ 將區間L,r上的所有元素置為voidupdate(NodeNode*LC=cur-LeftChild,*RC=cur-if (cur-en) if(L

23、C!=NULL)LC-data=cur-data,LC-en=true; if (RC!=NULL)RC-data=cur-data,RC-en=true; cur-en = false;if(LLeft)&(cur-Righten = true;cur-data = num;if(LLeft+cur-C,L, r,if(r(cur-Left+cur-Right)/2) update(RC, L, r, num);cur.sum=calcsum(LC)+if(LLeft)&(cur-Righten = true;cur-data = num;if(LLeft+cur-C,L, r,if(r(c

24、ur-Left+cur-Right)/2) update(RC, L, r, num);cur.sum=calcsum(LC)+/ 查詢區間L,r上所有元素的querysum(NodeNode*LC=cur-LeftChild,*RC=cur-ret=if(LRightdata=cur-data,LC-en=true; RC-data=cur-data,RC-en=true; Cur-en = false;if(LLeft+cur-Right)/2) ret += querysum(LC, L, r);if(r(cur-Left+cur-Right)/2) ret += querysum(RC

25、, L, r);cur-sum=LC-sum+LC-delta*(LC-LC-Left+cur-sum+=RC-sum+RC-delta*(RC-RightRC-Left+return可以總結出，上的信息通常有兩類（1）諸如 sum、max、min 之類的信息，表示了一個結點的性質，具有一定的遞推質，可以的時候自下向上（2）諸如 delta、en 與 data 整個子樹的性質，可以在需要進一步處理時，將這種性質自上而下于是可以總結出一個上對于當前區間if 達到某種邊界條件（如葉結點或被整個區間完全包含） 對將第二類標記傳遞下去（注意，在查詢過程中也要處理解決1（*）表示的區間的含義（包括一些坐

26、標轉化（離散化2上需的信息，并將這種信息分為前面所有的4、對于第一類信息，寫出遞推式5、對于第二類信息，寫出分解傳遞的算法67、確與線的空間復雜度是 O(L)，它提供了一種在 對于當前區間if 達到某種邊界條件（如葉結點或被整個區間完全包含） 對將第二類標記傳遞下去（注意，在查詢過程中也要處理解決1（*）表示的區間的含義（包括一些坐標轉化（離散化2上需的信息，并將這種信息分為前面所有的4、對于第一類信息，寫出遞推式5、對于第二類信息，寫出分解傳遞的算法67、確與線的空間復雜度是 O(L)，它提供了一種在 O(log2L)與查詢的結構但是，這種結構不是萬能的，它是一種遞歸定義的結構，因此，它所能

27、處理的所有問。七例 2：在所有不大于 30000的自然數范圍一個問題：已知 n條線段，把端點依次入給你，然后有（0：Mv=Ev-Cv=0v是葉結點：MvCv=0v不是葉結點：Mv先把坐標離散化，然后從左往右掃描每一條垂直于 x 到x行掃描，每掃描到一個點（設 x=m，就對 x=m 這條直線上的線段進行處理（分除，取得線段的并集長度 L，再計算 s:=s+L*(m-m1)（設下一個點坐標為 m1，即可。例 6：在平面上有 N個點，現在要求一些線段，使其滿足以下要求5：暫ab、線段的端點只能是這 N個點c、交于一點的兩條線段成 90度角d、線段都必須平行于坐標軸e、所有線段除在這 N個點外不自交f

28、、所有線段的長度之和必須最短如果存在這樣的線段，則輸出最小長度，否則輸出 0從該題的要求入手，先構造出符合要求的圖，再解決線段長度之和最。1N 個點為頂點的 N ，所以每個點只能與上下左右四個點相連。由于與一個點相連的兩條線段成 90 度角，每個頂點必須與一條平行于X軸和一條平行于y軸的線段相連。2、將所有點排序后發現，在同一水平線上的點中，設這些點為 P1、P2、P3、P4、 Pn，P1 要有一條平行于 X 軸的線段與其相連，就必須連它右邊的點P2，而 P3 如果再連P2，P2就有兩條平行于XP3只能連P4，P5只能連6述方法所構造出的線段是否合法滿足線段不在N個點之外自交：6：暫4、由于所有線段與坐標軸之一平行交判斷是否（1因為只可能是與X軸平行的線段和與YY軸平行的線段是否有線段與之相交。如果線段xy)-(,2)與線段x,)-(2y)相交，則應該符合1xx)、y2)。由條件x4、由于所有線段與坐標軸之一平行交判斷是否（1因為只可能是與X軸平行的線段和與YY軸平行的線段是否有線段與之相交。如果線段xy)