6.1??? 線段樹簡(jiǎn)介

線段樹的定義如下：

?? ? ? ?一棵二叉樹，記為T (a,b)，參數(shù)a,b表示該結(jié)點(diǎn)表示區(qū)間[a,b]。區(qū)間的長(zhǎng)度b-a記為L(zhǎng)。遞歸定義T[a,b]：

?? ? ? ?若L>1 ：[a, (a+b) div 2]為 T的左兒子

?? ? ? ? ? ? ? ? ? ? ? ?[(a+b)div 2,b]為T的右兒子。
?? ? ? ?若L=1 ：T為一個(gè)葉子結(jié)點(diǎn)。

表示區(qū)間[1, 10]的線段樹表示如下：

樹一般有兩種形式：1、以點(diǎn)為結(jié)點(diǎn)。2、以線段為結(jié)點(diǎn)。區(qū)別如圖：上面一個(gè)以線段為結(jié)點(diǎn)，下面一個(gè)以點(diǎn)為結(jié)點(diǎn)：

對(duì)線段樹存在：

定理：線段樹把區(qū)間上的任意一條線段都分成不超過2logL條線段。

這個(gè)結(jié)論為線段樹能在O(logL)的時(shí)間內(nèi)完成一條線段的插入、刪除、查找等工作，提供了理論依據(jù)。

對(duì)線段樹的可以進(jìn)行擴(kuò)展。

1.? 測(cè)度。結(jié)點(diǎn)所表示區(qū)間中線段覆蓋過的長(zhǎng)度，存儲(chǔ)在各結(jié)點(diǎn)中。

2.? 獨(dú)立線段數(shù)。區(qū)間中互不相交的線段條數(shù)。

3.? 權(quán)和。區(qū)間所有元線段的權(quán)和。

測(cè)度的遞推公式如下：

?? ? ? ? ? ? ? ??a[j] - a[i] ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?該結(jié)點(diǎn) Count>0

M = ? ? ? ? ?0 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?該結(jié)點(diǎn)為葉結(jié)點(diǎn)且 Count=0

?? ? ? ? ? ? ? ??Leftchild ↑ .M + Rightchild ↑ .M ? ? ? ? 該結(jié)點(diǎn)為內(nèi)部結(jié)點(diǎn)且 Count=0連續(xù)段數(shù)

這里的連續(xù)段數(shù)指的是區(qū)間的并可以分解為多少個(gè)獨(dú)立的區(qū)間。如 [1 ， 2] ∪[2，3]∪ [5 ， 6] 可以分解為兩個(gè)區(qū)間[1 ， 3] 與 [5 ， 6] ，則連續(xù)段數(shù)為 2 。增加一個(gè)數(shù)據(jù)域 Lines_Tree.line 表示該結(jié)點(diǎn)的連續(xù)段數(shù)。 Line 的討論比較復(fù)雜，內(nèi)部結(jié)點(diǎn)不能簡(jiǎn)單地將左右孩子的 Line 相加。所以再增加 Lines_Tree.lbd 與 Lines_Tree.rbd 域。定義如下： ?

?? ? ? ? ? ? ? ? 1???左端點(diǎn) I 被描述區(qū)間蓋到

lbd? =?

?? ? ? ? ? ? ? ? 0??? 左端點(diǎn) I 不被描述區(qū)間蓋到

?

?? ? ? ? ? ? ? ?1???? 右端點(diǎn) J 被描述區(qū)間蓋到

rbd? =?

?? ? ? ? ? ? ? ?0???? 右端點(diǎn) J 不被描述區(qū)間蓋到

?

lbd 與 rbd 的實(shí)現(xiàn)：

?? ? ? ? ? ? ? ?1? 該結(jié)點(diǎn) count > 0

lbd? = ? ? ?0? 該結(jié)點(diǎn)是葉結(jié)點(diǎn)且 count = 0

?? ? ? ? ? ? ? ?leftchild ↑ .lbd??? 該結(jié)點(diǎn)是內(nèi)部結(jié)點(diǎn)且 Count=0

?? ? ? ? ? ? ? ?1? 該結(jié)點(diǎn) count > 0

rbd? =??? 0? 該結(jié)點(diǎn)是葉結(jié)點(diǎn)且 count = 0

?? ? ? ? ? ? ? ?rightchild ↑ .rbd?? 該結(jié)點(diǎn)是內(nèi)部結(jié)點(diǎn)且 Count=0

有了 lbd 與 rbd ， Line 域就可以定義了：

?? ? ? ? ? ? ? ?1? 該結(jié)點(diǎn) count > 0

Line = ? ? 0? 該結(jié)點(diǎn)是葉結(jié)點(diǎn)且 count =0

?? ? ? ? ? ? ? ?Leftchild ↑ .Line? +? Rightchild ↑.Line? -? 1 ?當(dāng)該結(jié)點(diǎn)是內(nèi)部結(jié)點(diǎn)且 Count=0 ， Leftchild ↑ .rbd = 1 且 Rightchild ↑ .lbd = 1

?? ? ? ? ? ? ? ?Leftchild ↑.Line? +? Rightchild ↑ .Line?? 當(dāng)該結(jié)點(diǎn)是內(nèi)部結(jié)點(diǎn)且 Count=0 ， Leftchild ↑ .rbd 與 Rightchild ↑ .lbd 不都為1

6.2??? 利用線段樹實(shí)現(xiàn)區(qū)間的動(dòng)態(tài)插入和刪除

6.2.1???實(shí)例

PKU JudgeOnline, 1151, Atlantis.

6.2.2???問題描述

在二維平面分部著一些矩形，矩形有可能重合。求矩形的總面積。

6.2.3???分析

這個(gè)題在《算法藝術(shù)與信息學(xué)競(jìng)賽》中第一章介紹數(shù)據(jù)結(jié)構(gòu)時(shí)，講到線段樹的時(shí)候有解題分析。

用線段樹來記載縱向上是不是被覆蓋，用測(cè)度來表示區(qū)間中被覆蓋了多少長(zhǎng)度。

為了降低復(fù)雜度，可以將坐標(biāo)離散化，如下圖所示：

從左到右掃描長(zhǎng)方形的左側(cè)邊和右側(cè)邊，如果是左側(cè)邊則加入線段樹中，否則從線段書中刪除。同時(shí)用橫向掃描的距離乘以線段樹的測(cè)度，就得到了掃描過了的被覆蓋的面積。

本題和PKU JudgeOnline,1117, Picture題都對(duì)線段樹進(jìn)行了擴(kuò)展。本題只用到了測(cè)度的擴(kuò)展，而1117題還用到了獨(dú)立線段數(shù)的擴(kuò)展。

6.2.4???程序

//離散化+ 線段樹+ 掃描線 //本題與JudgeOnline 1177 picture 極相似,現(xiàn)在回想起來甚至比1177 還要簡(jiǎn)單一些.與1177 不同的是本題中的坐標(biāo)是浮點(diǎn) //類型的故不能將坐標(biāo)直接離散.我們必須為它們建立一個(gè)對(duì)應(yīng)關(guān)系,用一個(gè)整數(shù)去對(duì)應(yīng)一個(gè)浮點(diǎn)數(shù) //這樣的對(duì)應(yīng)關(guān)系在本題的數(shù)組y[] 中 #include<iostream> #include<algorithm> #include<cmath> #include<iomanip> using namespace std; struct node{ int st, ed,c; //c : 區(qū)間被覆蓋的層數(shù),m: 區(qū)間的測(cè)度 double m; }ST[802]; struct line{ doublex,y1,y2; //縱方向直線, x:直線橫坐標(biāo), y1 y2:直線上的下面與上面的兩個(gè)縱坐標(biāo) bools; //s = 1: 直線為矩形的左邊, s = 0:直線為矩形的右邊 }Line[205]; double y[205],ty[205]; //y[] 整數(shù)與浮點(diǎn)數(shù)的對(duì)應(yīng)數(shù)組;ty[]:用來求y[]的輔助數(shù)組 void build(int root, int st, int ed){ ST[root].st = st; ST[root].ed = ed; ST[root].c = 0; ST[root].m = 0; if(ed - st> 1){ int mid= (st+ed)/2; build(root*2, st, mid); build(root*2+1, mid, ed); } } inline void updata(int root){ if(ST[root].c> 0) //將線段樹上區(qū)間的端點(diǎn)分別映射到y(tǒng)[]數(shù)組所對(duì)應(yīng)的浮點(diǎn)數(shù)上,由此計(jì)算出測(cè)度 ST[root].m = y[ST[root].ed-1] -y[ST[root].st-1]; else if(ST[root].ed - ST[root].st == 1) ST[root].m = 0; elseST[root].m = ST[root*2].m + ST[root*2+1].m; } void insert(int root, int st, int ed){ if(st <=ST[root].st && ST[root].ed <= ed){ ST[root].c++; updata(root); return; } if(ST[root].ed- ST[root].st == 1)return ;//不出錯(cuò)的話這句話就是冗余的 int mid =(ST[root].ed + ST[root].st)/2; if(st <mid) insert(root*2, st, ed); if(ed >mid) insert(root*2+1, st, ed); updata(root); } void Delete(int root, int st, int ed){ if(st <=ST[root].st && ST[root].ed <= ed){ ST[root].c--; updata(root); return; } if(ST[root].ed- ST[root].st == 1)return ; //不出錯(cuò)的話這句話就是冗余的 int mid =(ST[root].st + ST[root].ed)/2; if(st <mid) Delete(root*2, st, ed); if(ed >mid) Delete(root*2+1, st, ed); updata(root); } int Correspond(int n, double t){ //二分查找出浮點(diǎn)數(shù)t 在數(shù)組y[]中的位置(此即所謂的映射關(guān)系) intlow,high,mid; low = 0; high = n-1; while(low< high){ mid = (low+high)/2; if(t> y[mid]) low = mid + 1; elsehigh = mid; } returnhigh+1; } bool cmp(line l1, line l2){ return l1.x< l2.x; } int main() { intn,i,num,l,r,c=0; doublearea,x1,x2,y1,y2; while(cin>>n,n){ for(i =0; i < n; i++){ cin>>x1>>y1>>x2>>y2; Line[2*i].x = x1; Line[2*i].y1 =y1; Line[2*i].y2 = y2; Line[2*i].s = 1; Line[2*i+1].x = x2; Line[2*i+1].y1= y1; Line[2*i+1].y2 = y2; Line[2*i+1].s = 0; ty[2*i] = y1; ty[2*i+1] = y2; } n <<= 1; sort(Line, Line+n, cmp); sort(ty, ty+n); y[0] = ty[0]; //處理數(shù)組ty[]使之不含重覆元素,得到新的數(shù)組存放到數(shù)組y[]中 for(i=num=1;i < n; i++) if(ty[i]!= ty[i-1]) y[num++] = ty[i]; build(1, 1, num); //樹的葉子結(jié)點(diǎn)與數(shù)組y[]中的元素個(gè)數(shù)相同,以便建立一一對(duì)應(yīng)的關(guān)系 area = 0; for(i =0; i < n-1; i++){ //由對(duì)應(yīng)關(guān)系計(jì)算出線段兩端在樹中的位置 l = Correspond(num, Line[i].y1); r = Correspond(num, Line[i].y2); if(Line[i].s)//插入矩形的左邊 insert(1, l, r); else //刪除矩形的右邊 Delete(1, l, r); area += ST[1].m * (Line[i+1].x -Line[i].x); } cout<<"Testcase #"<<++c<<endl<<"Totalexplored area: "; cout<<fixed<<setprecision(2)<<area<<endl<<endl; } return 0; }

6.3??? 計(jì)算數(shù)組區(qū)間第K大的數(shù)

PKU JudgeOnline, 2761, Feed the dogs則是線段樹的另外一個(gè)應(yīng)用：實(shí)用線段樹來計(jì)算數(shù)組區(qū)間[i, j]中元素第k小（或第K大）的數(shù)。只要添寫一個(gè)函數(shù)，根據(jù)線段樹中每個(gè)結(jié)點(diǎn)的覆蓋樹木來判斷第k大的樹是哪一個(gè)。

當(dāng)初始化，或者區(qū)間[i, j]發(fā)生變化時(shí)，需要對(duì)線段樹進(jìn)行添加或者刪除操作。每當(dāng)增加（或刪除）一個(gè)大小為X的點(diǎn)時(shí)，就在樹上添加（或刪除）一條(X,MaxLen)的線段（不含端點(diǎn)），當(dāng)要查詢一個(gè)點(diǎn)的排名時(shí)，只要看看其上有多少條線段就可以了。

int query(int root, intcount) { if(count<= ST[root].c){ returnST[root].st; }else if(ST[root].ed - ST[root].st == 1){ returnST[root].ed; } count -= ST[root].c; if(count<= ST[root*2+1].c){ returnquery(root*2, count); }else{ returnquery(root*2+1, count); } }
1.4??? 實(shí)例

PKU JudgeOnline, 1151, Atlantis.

PKU JudgeOnline, 1117, Picture.

PKU JudgeOnline, 2761, Feed the dogs.

PKU JudgeOnline, 2528, Mayor'sposters.

本文章歡迎轉(zhuǎn)載，請(qǐng)保留原始博客鏈接http://blog.csdn.net/fsdev/article

轉(zhuǎn)載于:https://www.cnblogs.com/jpa2/archive/2011/10/13/2527921.html

總結(jié)

以上是生活随笔為你收集整理的实用算法实现-第6篇线段树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。