線段樹及其應(yīng)用課件

1、線段樹及其應(yīng)用江蘇省華羅庚中學(xué) 楊志軍為什么要用線段樹？例1：有M個數(shù)排成一列，初始值全為0，然后做N次操作，每次我們可以進(jìn)行如下操作：（1）將指定區(qū)間的每個數(shù)加上一個值；（2）將指定區(qū)間的所有數(shù)置成一個值；（3）詢問一個區(qū)間上的最小值、最大值、所有數(shù)的和。為什么要用線段樹？一般的模擬算法： 用一張線性表表示整個數(shù)列，每次執(zhí)行前兩個操作的時候，將對應(yīng)區(qū)間里的數(shù)值逐一進(jìn)行修改，執(zhí)行第三個操作的時候，線性掃描詢問區(qū)間，求出三個統(tǒng)計(jì)值，每次維護(hù)的時間復(fù)雜度O(m)，整體的時間復(fù)雜度O(mn)。為什么要用線段樹？readln(m,n);for i:=1 to n dobegin read(t); if

2、 t=1 /指定區(qū)間加上一個值 then begin readln(left,right,x); for j:=left to right do aj:=aj+x; end;if t=2 /指定區(qū)間置成一個值then begin readln(left,right,x); for j:=left to right do aj:=x; end;為什么要用線段樹？if t=3 /詢問一個區(qū)間的最小值、最大值、和then begin readln(left,right); min:=aleft; max:=aleft; sum:=aleft; for j:=left+1 to right do be

3、gin if ajmax then max:=aj; sum:=sum+aj; end; writeln(min, ,max, ,sum); end;為什么要用線段樹？機(jī)器配置：Pentium 1.3G 512MM,N的規(guī)模一般的模擬M=100000,N=50002.06秒M=100000,N=100004.14秒M=100000,N=5000021.32秒M=100000,N=10000043.36秒時間復(fù)雜度是線性的！為什么要用線段樹？ 當(dāng)m、n的值比較大時，這個算法就太低效了。其低效的原因主要是我們在每一次操作中都是針對每個元素進(jìn)行維護(hù)的，而這里我們進(jìn)行的操作都是針對一個區(qū)間進(jìn)行操作的。

4、 假如設(shè)計(jì)一種數(shù)據(jù)結(jié)構(gòu)，能夠直接維護(hù)所需處理的區(qū)間，那么就能更加有效地解決這個問題。線段樹（區(qū)間樹）線段樹的結(jié)構(gòu)定義1：長度為1的線段稱為元線段。定義2：一棵樹被稱為線段樹，當(dāng)且僅當(dāng)這棵樹滿足如下條件： （1）該樹是一棵二叉樹； （2）樹中的每一個結(jié)點(diǎn)都對應(yīng)一條線段a,b； （3）樹中的結(jié)點(diǎn)是葉子結(jié)點(diǎn)，當(dāng)且僅當(dāng)它所代表的線段是元線段； （4）樹中非葉子結(jié)點(diǎn)都有左右兩棵子樹，左子樹樹根對應(yīng)線段a,(a+b)/2，右子樹樹根對應(yīng)線段(a+b)/2,b。線段樹的結(jié)構(gòu)如T(1,10)的結(jié)構(gòu)：1,10 1,5 5,10 1,3 3,5 5,7 7,10 1,2 2,3 3,4 4,5 5,6 6,7 7

5、,8 8,10 8,9 9,10 線段樹的結(jié)構(gòu) 常用的是需要對數(shù)列進(jìn)行處理，將區(qū)間a,b分解為a,(a+b)/2，(a+b)/2+1,b，當(dāng)a=b時表示為一個葉子結(jié)點(diǎn)，表示數(shù)列中的一個數(shù)。1,10 1,5 6,10 1,3 4,5 6,8 9,10 1,2 3,3 4,4 5,5 6,7 8,8 9,9 10,10 1,1 2,2 6,6 7,7 線段樹的性質(zhì)性質(zhì)1：長度范圍為1,L的一棵線段樹的深度不超過log2(L-1)+1；性質(zhì)2：線段樹上的結(jié)點(diǎn)個數(shù)不超過2L個；性質(zhì)3：線段樹把區(qū)間上的任意一條線段都分成不超過2log2L條線段。線段樹的存儲方式（1）鏈表實(shí)現(xiàn)： Node=TNode;

6、TNode=record Left,Right:integer; LeftChild,RightChild:Node; end;（2）數(shù)組模擬鏈表：Left,Right,LeftChild,RightChild:array1.n of integer;（3）堆的結(jié)構(gòu)：根節(jié)點(diǎn)為1，對于結(jié)點(diǎn)x，其左孩子為2x，右孩子為2x+1線段樹的基本操作及實(shí)現(xiàn)線段樹的構(gòu)造procedure build(cur:Node;l,r:integer);begin cur.Left:=l; cur.Right:=r; if l=r then begin cur.LeftChild:=nil; cur.RightChi

7、ld:=nil; end else begin new(cur.LeftChild); new(cur.RightChild); build(cur.LeftChild,l,(l+r) div 2); build(cur.RightChild,(l+r) div 2+1,r); end; end;線段樹的基本操作及實(shí)現(xiàn)線段樹的查詢procedure query(cur:Node;l,r:integer);var LC,RC:Node;begin LC:=cur.LeftChild; RC:=cur.RightChild; if (l=cur.Left) and (cur.Right=r) th

8、en writeln(cur.Left, ,cur.Right); /可以增加其他操作 else begin if l(cur.Left+cur.Right) div 2 then query(RC,l,r); end;end;線段樹的維護(hù)方法對區(qū)間進(jìn)行修改對元素進(jìn)行修改設(shè)置為同一個數(shù)統(tǒng)一加上一個數(shù)修改查詢區(qū)間的和區(qū)間的最大值區(qū)間的最小值其它線段樹的維護(hù)方法 如果想要讓線段樹發(fā)揮實(shí)際的作用，必須在每個結(jié)點(diǎn)上維護(hù)額外的域來記錄更多的信息。 首先看一個引例的弱化版，假設(shè)每次修改操作只能對其中某個元素進(jìn)行修改。 在每個結(jié)點(diǎn)上額外維護(hù)3個域：max、min、sum，分別表示子樹上的最大值、最小值和所有

9、元素的和。（1）對元素進(jìn)行修改procedure insert(cur:Node;x,num:integer);var LC,RC:Node;begin LC:=cur.LeftChild; RC:=cur.RightChild; if cur.Left=cur.Right /對葉結(jié)點(diǎn)的處理 then begin cur.Min:=num; cur.Max:=num; cur.Sum:=num; end else begin if x(cur.Left+cur.Right) div 2 then insert(RC,x,num); cur.Sum:=LC.Sum+RC.Sum; /上推 if

10、(LC.MaxRC.Max) then cur.Max:=LC.Max else cur.Max:=RC.Max; if (LC.MinRC.Min) then cur.Min:=LC.Min else cur.Min:=RC.Min; end;end;（2）對區(qū)間進(jìn)行查詢function querysum(cur:Node;l,r:integer):integer;var LC,RC:Node; ret:integer;begin LC:=cur.LeftChild; RC:=cur.RightChild; ret:=0; if (l=cur.Left) and (cur.Right=r)

11、then ret:=cur.Sum else begin if l(cur.Left+cur.Right) div 2 then ret:=ret+querysum(RC,l,r); end; querysum:=ret;end;（3）對區(qū)間修改（統(tǒng)一加上一個數(shù)）procedure update(cur:Node;l,r,delta:integer);var LC,RC:Node; /需要給每個區(qū)間增加一個變量deltabegin LC:=cur.LeftChild; RC:=cur.RightChild; if (l=cur.Left) and (cur.Right=r) then cur.

12、Delta:=cur.Delta+delta /改變該區(qū)間的delta，注意sum else begin if l(cur.Left+cur.Right) div 2 then update(RC,l,r,delta); cur.Sum:=LC.Sum+LC.Delta*(LC.Right-LC.Left+1); cur.Sum:=cur.Sum+RC.Sum+ /上推 RC.Delta*(RC.Right-RC.Left+1); end;end;（4）對區(qū)間查詢function querysum(cur:Node;l,r:integer):integer;var LC,RC:Node; re

13、t:integer;begin LC:=cur.LeftChild; RC:=cur.RightChild; ret:=0; if (l=cur.Left) and (cur.Right=r) then ret:=ret+cur.Sum+(cur.Right-cur.Left+1)*cur.Delta else begin /將該區(qū)間的delta下傳 給左右區(qū)間，同時修改sum的值 cur.sum:=cur.sum+(cur.right-cur.left+1)*cur.delta; LC.Delta:=LC.Delta+cur.Delta; RC.Delta:=RC.Delta+cur.Del

14、ta; cur.Delta:=0; if l(cur.Left+cur.Right) div 2 then ret:=ret+querysum(RC,l,r); end; querysum:=ret;end;（5）對區(qū)間修改（設(shè)置為同一個數(shù)）procedure update(cur:Node;l,r,num:integer);var LC,RC:Node;begin LC:=cur.LeftChild; RC:=cur.RightChild; if cur.En /如果該區(qū)間已經(jīng)是同一個值，將值下傳給左右區(qū)間 then begin cur.sum:=(cur.right-cur.left+1)

15、*cur.data; if LCnil then begin LC.Data:=cur.Data; LC.En:=true; end; if RCnil then begin RC.Data:=cur.Data; RC.En:=true; end; cur.En:=false; end; if (l=cur.Left) and (cur.Right=r) then begin cur.En:=true; cur.Data:=num; end else begin if l(cur.Left+cur.Right) div 2 then update(RC,l,r,num); cur.Sum:=c

16、alcsum(LC)+calcsum(RC); end;end;function calcsum(cur:Node):integer;begin if cur.En then calcsum:=(cur.Right-cur.Left+1)*cur.Data else calcsum:=cur.Sum;end;（6）對區(qū)間查詢function querysum(cur:Node;l,r:integer):integer;var LC,RC:Node; ret:integer;begin LC:=cur.LeftChild; RC:=cur.RightChild; ret:=0; if (l=cu

17、r.Left) and (cur.Right=r) then ret:=ret+calcsum(cur) else begin if cur.En /如果該區(qū)間是同一個數(shù)，將值下傳給左右區(qū)間 then begin LC.Data:=cur.Data; LC.En:=true; RC.Data:=cur.Data; RC.En:=true; cur.En:=false; end; if l(cur.Left+cur.Right) div 2 then ret:=ret+querysum(RC,l,r); end; querysum:=ret;end;線段樹的維護(hù)方法線段樹上的參數(shù)通常有兩種維護(hù)方

18、法：（1）一類參數(shù)表達(dá)了結(jié)點(diǎn)的性質(zhì)，通常具有樹型的遞推性質(zhì)，可以從下向上進(jìn)行遞推計(jì)算；（如sum,max,min）（2）一類參數(shù)表達(dá)了子樹的性質(zhì)，維護(hù)的時候可以先打上標(biāo)記，在需要進(jìn)一步訪問其子結(jié)點(diǎn)的時候從上向下傳遞。（如delta,en）線段樹的維護(hù)方法線段樹上維護(hù)或者詢問過程的一般過程：對于當(dāng)前區(qū)間l,rif 達(dá)到某種邊界條件（如葉結(jié)點(diǎn)或被整個區(qū)間完全包含）then 對維護(hù)或是詢問作相應(yīng)處理else 將第二類標(biāo)記傳遞下去(注意，在查詢過程中也要處理) 根據(jù)區(qū)間的關(guān)系，對兩個孩子結(jié)點(diǎn)遞歸處理 利用遞推關(guān)系，根據(jù)孩子結(jié)點(diǎn)的情況維護(hù)第一類信息為什么要用線段樹？M,N的規(guī)模一般的模擬線段樹M=100

19、000,N=50002.06秒0. 57秒M=100000,N=100004.14秒0. 61秒M=100000,N=5000021.32秒1.21秒M=100000,N=10000043.36秒2.03秒應(yīng)用舉例例2、線段覆蓋 在所有不大于30000的自然數(shù)范圍內(nèi)討論一個問題：已知n條線段，把端點(diǎn)依次輸入告訴你，然后有m（30000）個詢問，每個詢問輸入一個點(diǎn)，要求這個點(diǎn)在多少條線段上出現(xiàn)過。0 1 2 3 4 5 6 7 8n=4 m=3線段：0,3 4,6 2,6 5,7詢問：1，3，5應(yīng)用舉例（線段覆蓋） 可以直接對問題處理的區(qū)間建立線段樹，在線段樹上維護(hù)區(qū)間被覆蓋的次數(shù)。將n條線段插

20、入線段樹，然后對于詢問的每個點(diǎn)，直接查詢被覆蓋的次數(shù)即可。應(yīng)用舉例（線段覆蓋） 這道題目完全可以不用線段樹，將每個線段拆分成(L,+1)，(R+1,-1)的兩個事件點(diǎn)，每個詢問點(diǎn)也在對應(yīng)坐標(biāo)處加上一個詢問的事件點(diǎn)，排序之后掃描就可以完成題目的詢問。Sum 1 1 2 2 2 3 3 1 0 +1-1-1-10 1 2 3 4 5 6 7 8+1+1+1-1應(yīng)用舉例（線段覆蓋） 因?yàn)榇藛栴}是一個離線的問題，這是一個很簡單的離線算法。線段樹在處理在線問題的時候會更加有效，因?yàn)樗S護(hù)了一個實(shí)時的信息。應(yīng)用舉例例3、售票系統(tǒng) 某次列車途經(jīng)C個城市，城市編號依次為1到C，列車上共有S個座位，每一個售票申

21、請包含三個參數(shù)，分別用O、D、N表示，O為起始站，D為目的地站，N為車票張數(shù)，售票系統(tǒng)對該售票申請作出受理或不受理的決定。只有在從O到D的區(qū)段內(nèi)列車上都有N個或N個以上的空座位時該售票申請才被受理。1=C=60000，1=S=60000，1=R=60000，C為城市個數(shù)，S為列車上的座位數(shù)，R為所有售票申請總數(shù)。應(yīng)用舉例（售票系統(tǒng)）輸入：4 6 41 4 21 3 22 4 31 2 3輸入：YESYESNONO應(yīng)用舉例（售票系統(tǒng)） 可以把所有的車站順次放在一個數(shù)軸上，在數(shù)軸上建立線段樹，在線段樹上維護(hù)區(qū)間的delta與max，每次判斷一個售票申請是否可行就是查詢區(qū)間上的最大值；每個插入一個售

22、票請求，就是給一個區(qū)間上所有的元素加上購票數(shù)。應(yīng)用舉例（售票系統(tǒng)）procedure build(cur:node;l,r:longint);begin cur.left:=l; cur.right:=r; if l=r then begin cur.leftchild:=nil; cur.rightchild:=nil; cur.delta:=0; cur.max:=0; end else begin new(cur.leftchild); new(cur.rightchild); build(cur.leftchild,l,(l+r) div 2); build(cur.rightchil

23、d,(l+r) div 2+1,r); end;end;應(yīng)用舉例（售票系統(tǒng)）procedure update(cur:node;l,r,delta:longint);var lc,rc:node;begin lc:=cur.leftchild; rc:=cur.rightchild; if (l=cur.right) then begin cur.delta:=cur.delta+delta; cur.max:=cur.max+delta; end else begin if l(cur.left+cur.right) div 2 then update(rc,l,r,delta); if l

24、c.maxrc.max then cur.max:=lc.max+cur.delta else cur.max:=rc.max+cur.delta; end;end;function querymax(cur:node;l,r:longint):longint;var lc,rc:node; ret:longint;begin lc:=cur.leftchild; rc:=cur.rightchild; ret:=0; if (l=cur.left) and (cur.right=r) then ret:=cur.max else begin lc.delta:=lc.delta+cur.de

25、lta;rc.delta:=rc.delta+cur.delta; lc.max:=lc.max+cur.delta; rc.max:=rc.max+cur.delta; cur.delta:=0; if l(cur.left+cur.right) div 2 then if rets then writeln(NO) else begin writeln(YES); update(tree,a,b-1,x); end; end;end.算法改進(jìn)Function test(cur:node;l,r,x,remain:longint):boolean;var lc,rc:node; ret:bo

26、olean;begin lc:=cur.leftchild; rc:=cur.rightchild; ret:=true; if (l=cur.right) then if cur.max+xremain then ret:=false else ret:=true else if (remain-cur.delta=0) then begin if l(cur.left+cur.right) div 2 then ret:=ret and test(rc,l,r,x,remain-cur.delta) end; test:=ret;end;應(yīng)用舉例例4、采礦 金礦的老師傅年底要退休了。經(jīng)理為

27、了獎賞他的盡職盡責(zé)的工作，決定送他一塊長方形地。長度為S，寬度為W。老師傅可以自己選擇這塊地。顯然其中包含的采金點(diǎn)越多越好。你的任務(wù)就是計(jì)算最多能得到多少個采金點(diǎn)。如果一個采金點(diǎn)的位置在長方形的邊上，它也應(yīng)當(dāng)被計(jì)算在內(nèi)。讀入采金點(diǎn)的位置。計(jì)算最大的價值。 數(shù)據(jù)范圍：1=s,w=10000 1=s,w=10000 -30000=x,y=30000應(yīng)用舉例（采礦）L1L2SW應(yīng)用舉例（采礦）對于每一個點(diǎn)的縱坐標(biāo)y，建立兩個事件點(diǎn)(y,+1)，(y+w+1,-1)如5個點(diǎn)的縱坐標(biāo)分別是(5,3,9,1,9),w=2得到10個事件點(diǎn)：(5,+1),(8,-1),(3,+1),(6,-1),(9,+1)

28、,(12,-1),(1,+1),(4,-1),(9,+1),(12,-1)1 2 3 4 5 6 7 8 9 10 11 12+1 +1 -1 +1 -1 -1 +2 -2然后從低到高求和，這些和中最大的一個就是該帶狀區(qū)域中一個包含最多點(diǎn)數(shù)的矩形。 1 2 1 2 1 0 +2 0應(yīng)用舉例例5、面積 平面上有若干個平行于坐標(biāo)軸的矩形，它們可以相互重疊且每個矩形頂點(diǎn)的坐標(biāo)都是整數(shù)，求這些矩形覆蓋的總面積。輸入：210 10 20 2015 15 25 30 輸出：225 應(yīng)用舉例（面積）10152025應(yīng)用舉例（面積） 先把坐標(biāo)離散化，然后從左往右掃描每一條垂直于X軸的線段，如果一條線段是矩形的

29、左邊界，則插入線段；如果是矩形的右邊界，則刪除線段。取得線段的長度即可得到當(dāng)前離散條的面積。 定義add、del兩個數(shù)組分別記錄每個矩形的左邊界、右邊界。輸入：210 10 20 2015 15 25 30 add10,1.h1=10; add10,1.h2=20;del20,1.h1=10; del20,1.h2=20;add15,1.h1=15; add15,1.h2=30;del25,1.h1=15; del25,1.h2=30;應(yīng)用舉例（面積）procedure build(cur:node;l,r:longint);begin cur.left:=l; cur.right:=r; i

30、f l+1=r then begin cur.leftchild:=nil; cur.rightchild:=nil; cur.delta:=0; cur.sum:=0; end else begin new(cur.leftchild); new(cur.rightchild); build(cur.leftchild,l,(l+r) div 2); build(cur.rightchild,(l+r) div 2,r); end;end;procedure update(cur:node;l,r,t:longint);var lc,rc:node;begin lc:=cur.leftchi

31、ld; rc:=cur.rightchild; if (l=cur.left) and (cur.right=r) then if t=0 then dec(cur.delta) else inc(cur.delta) else begin if l(cur.left+cur.right) div 2 then update(rc,l,r,t); if lc.delta0 then cur.sum:=lc.right-lc.left else cur.sum:=lc.sum; if rc.delta0 then cur.sum:=cur.sum+rc.right-rc.left else cu

32、r.sum:=cur.sum+rc.sum; end;end;應(yīng)用舉例（面積）主程序：for i:=1 to 30000 dobegin addi:=nil; deli:=nil;end;readln(n);for i:=1 to n dobegin readln(x1,y1,x2,y2); new(p); p.h1:=y1; p.h2:=y2; p.next:=addx1; addx1:=p; new(p); p.h1:=y1; p.h2:=y2; p.next:=delx2; delx2:=p;end;new(tree); build(tree,0,30000); sum:=0;for i

33、:=0 to 30000 dobegin p:=deli; while pnil do begin update(tree,p.h1,p.h2,0); p:=p.next; end; p:=addi; while pnil do begin update(tree,p.h1,p.h2,1); p:=p.next; end; if tree.delta0 then sum:=sum+30000 else sum:=sum+tree.sum;end;writeln(sum);應(yīng)用舉例例6、蛇在平面上有N個點(diǎn)，現(xiàn)在要用一些線段將它們連起來，使其滿足以下要求：（1）這些線段必須閉合（2）線段的端點(diǎn)只能是這N個點(diǎn)（3）交于一點(diǎn)的兩條線段成90度角（4）線段都必須平行于X軸或Y軸（5）所有線段除了在這N個點(diǎn)外不相交（6）所有線段的長度之和必須最短如果存在這樣的線段，則輸出最小長度，否則輸出0。 XY應(yīng)用舉例（蛇）1、所有線段都要和坐標(biāo)軸平行，所以每個點(diǎn)只能與上下左右四個點(diǎn)相連，由于與一個點(diǎn)相連的兩條線段成90度，每個頂點(diǎn)必須與一條平行于X軸和一條平行于Y軸的線段相連。2、在同一水平線上的點(diǎn)中，按X軸排序后設(shè)為P1，P2，Pn，P1必須與P2相連，P3必須與P4相連，在同一垂直線上的點(diǎn)也同樣，所以線段