線段樹線段樹和樹狀數(shù)組

課程網(wǎng)頁http

/JudgeOnline/summerschool/pku_acm_train.htm上機地點：理科1號樓1235線段樹和樹狀數(shù)組信息學院線段樹(Interval

Tree)實際上還是稱為區(qū)間樹更好理解一些。樹：是一棵樹，而且是一棵二叉樹。線段：樹上的每個節(jié)點對應于一個線段(還是叫

“區(qū)間”更容易理解，區(qū)間的起點和終點通常為整數(shù))同一層的節(jié)點所代表的區(qū)間，相互不會

。葉子節(jié)點的區(qū)間是單位長度，不能再分了。線段樹是一棵二叉樹，樹中的每一個結(jié)點表示了一個區(qū)間[a,b]。a,b通常是整數(shù)。每一個葉子節(jié)點表示了一個單位區(qū)間。對于每一個非葉結(jié)點所表示的結(jié)點[a,b]，其左兒子表示的區(qū)間為[a,(a+b)/2]，右兒子表示的區(qū)間為[(a+b)/2+1,b](除法去尾取整）。區(qū)間[1,

9]的線段樹[1,9][1,5][6,9][1,3]3[1,2][4,5]

[6,7]

[8,9]4

5

6

7

891

2每個區(qū)間的長度是區(qū)間內(nèi)整數(shù)的個數(shù)葉子節(jié)點長度為1，不能再往下分若一個節(jié)點對應的區(qū)間是[a,b],則其子節(jié)點對應的區(qū)間分別是[a,(a+b)/2]和[(a+b)/2+1,b]（除法去尾取整）線段樹的平分構(gòu)造，實際上是用了二分的方法。若根節(jié)點對應的區(qū)間是[a,b],那么它的深度為log2(b-a+1)

+1

(向上取整）。葉子節(jié)點的數(shù)目和根節(jié)點表示區(qū)間的長度相同.線段樹是滿二叉樹（節(jié)點要么0度，要么2度）,因此若葉子節(jié)點數(shù)目為N,則線段樹總結(jié)點數(shù)目為2N-1區(qū)間[1,

9]的線段樹上，區(qū)間[2,8]的分解[1,9][1,5]

[6,9][1,3]

[4,5]

[6,7]

[8,9]34

5

6

7

8[1,2]

91

2分解的規(guī)則就是：如果有某個節(jié)點代表的區(qū)間，完全屬于待分解區(qū)間，則該節(jié)點為“終止”節(jié)點，不再繼續(xù)往下分解所有“終止”節(jié)點所代表的區(qū)間都不

，且加在一起就覆蓋了整條待分解區(qū)間區(qū)間[1,

9]的線段樹上，區(qū)間[2,8]的分解[1,9][1,5]

[6,9][1,3]

[4,5]

[6,7]

[8,9]34

5

6

7

8[1,2]

91

2區(qū)間分解的時候，每層最多2個“終止節(jié)點”，所以終止節(jié)點總數(shù)也是log(n)量級的證明每層最多2個“終止節(jié)點”:[a,b][c,d][e,f]X代表終止節(jié)點。上述情況不可能發(fā)生線段樹的特征1、線段樹的深度不超過log2(n)+1（向上取整，n是根節(jié)點對應區(qū)間的長度）。2、線段樹上，任意一個區(qū)間被分解后得到的“終止節(jié)點”數(shù)目都是log(n)量級。線段樹上更新葉子節(jié)點和進行區(qū)間分解時間復雜度都是O(log(n))的這些結(jié)論為線段樹能在O(log(n))的時間內(nèi)完成一個區(qū)間的建樹，

數(shù)據(jù)，查找、統(tǒng)計等工作，提供了理論依據(jù)線段樹的構(gòu)建function

以節(jié)點v為根建樹、v對應區(qū)間為[l,r]{對節(jié)點v初始化if

(l!=r){以v的左孩子為根建樹、區(qū)間為[l,(l+r)/2]以v的右孩子為根建樹、區(qū)間為[(l+r)/2+1,r]}}線段樹的基本用途線段樹適用于和區(qū)間統(tǒng)計有關(guān)的問題。比如某些數(shù)據(jù)可以按區(qū)間進行劃分，按區(qū)間動態(tài)進行修改，而且還需要按區(qū)間多次進行查詢，那么使用線段樹可以達到較快查詢速度。線段樹應用舉例給你一個數(shù)的序列A1A2……An。并且可能多次進行下列兩個操作：1、對序列里面的某個數(shù)進行加減2、詢問這個序列里面任意

續(xù)的子序列AiAi+1……Aj的和是多少。希望第2個操作每次能在log(n)時間內(nèi)完成線段樹應用舉例顯然，[1,n]就是根節(jié)點對應的區(qū)間可以在每個節(jié)點記錄該節(jié)點對應的區(qū)間里面的數(shù)的和Sum。對于操作1：因為序列里面Ai最多只會被線段樹的log(n)個節(jié)點覆蓋。只要求對線段樹覆蓋

Ai的節(jié)點的Sum進行加操作，因此復雜度是

log(n)對于操作2：同樣只需要找到區(qū)間所覆蓋的節(jié)點，然后把所找節(jié)點的Sum累加起來。因為這些節(jié)點的數(shù)量是O（log(n))的，所以這一步的復雜度也是log(n)線段樹應用舉例如果走到節(jié)點[L,R]時，如果要查詢的區(qū)間就是[L,R](求AL到AR的和）那么直接返回該節(jié)點的Sum，并累加到總的和上;如果不是，則：對于區(qū)間[L,R]，取mid=（L+R）/2；然后看要查詢的區(qū)間與[L,mid]或[mid+1,R]哪個有交集，就進入哪個區(qū)間進行進一步查詢。因為這個線段樹的深度最深的LogN，所以每次遍歷操作都在LogN的內(nèi)完成。但是常數(shù)可能很大。線段樹應用舉例如果是對區(qū)間所對應的一些數(shù)據(jù)進行修改，過程和查詢類似。用線段樹解題，關(guān)鍵是要想清楚每個節(jié)點要存哪些信息（當然區(qū)間起終點，以及左右子節(jié)點指針是必須的），，查詢。不要一更新就可能變成O(n)以及這些信息如何高效更新，就更新到葉子節(jié)點，那樣更新效率的了。先建樹，然后

數(shù)據(jù)，然后更新，查詢。例題：POJ

3264

Balanced

Lineup給定Q

(1≤Q

≤200,000)個數(shù)A1,A2

…AQ,，多次求任一區(qū)間Ai

–Aj中最大數(shù)和最小數(shù)的差。本題樹節(jié)點結(jié)構(gòu)是什么?例題：POJ

3264

Balanced

Lineup給定Q

(1≤Q

≤200,000)個數(shù)A1,A2

…AQ,，多次求任一區(qū)間Ai

–Aj中最大數(shù)和最小數(shù)的差。本題樹節(jié)點結(jié)構(gòu)：struct

CNode{int

L,R;//區(qū)間起點和終點int

nMin,nMax;//本區(qū)間里的最大最小值CNode

*

pLeft,

*

pRight;};也可以不要左右節(jié)點指針，用一個數(shù)組存放線段樹。根節(jié)點下標為0。假設(shè)線段樹上某節(jié)點下標為i,則其左子節(jié)點下表為i*2+1,右子節(jié)點下標為i

*

2+2即(i<<1)+1和(i<<1)+2Sample

Input6

3

//6個數(shù)，3次個查詢2Sample

Output630#include

<iostream>#include

<algorithm>#include

<numeric>using

namespacestd;#define

MY_MIN

99999999#define

MY_MAX

-99999999struct

CNode{int

L,R;int

nMin,nMax;CNode

*

pLeft,

*

pRight;};int

nMax,

nMin;CNode

Tree[1000000];//其實兩倍葉子節(jié)點的數(shù)量就夠

int

nCount=0;//總節(jié)點數(shù)目void

BuildTree(CNode

*

pRoot,

int

L,int

R){pRoot->L

=L;pRoot->R=

R;pRoot->nMin

=

MY_MIN;pRoot->nMax

=

MY_MAX;if

(

L

!=

R)

{nCount

++;pRoot->pLeft

=

Tree

+

nCount;nCount

++;pRoot->pRight

=

Tree

+

nCount;BuildTree(

pRoot->pLeft,

L,

(

L

+

R

)/2);BuildTree(

pRoot->pRight,

(L

+

R)

/

2

+

1,R);}}void

Insert(

CNode*

pRoot

,

int

i,int

v)線段樹//將第i個數(shù)，其值為v，{if(

pRoot->L

==

i

&&

pRoot->R

==

i

)

{pRoot->nMin

=

pRoot->nMax

=

v;return;}pRoot->nMin

=

min(pRoot->nMin,v);pRoot->nMax

=max(pRoot->nMax,v);if(

i

<=

(pRoot->L

+

pRoot->R

)/2

)Insert(

pRoot->pLeft,i,v);elseInsert(

pRoot->pRight,i,v);}void

Query(CNode

*

pRoot,

int

s,

int

e)//查詢區(qū)間[s,e]中的最小值和最大值，如果更優(yōu)就記在全局變量里{if(

pRoot->nMin

>=

nMin

&&

pRoot->nMax

<=

nMax

)return;if(

s

==

pRoot->L

&&

e

==

pRoot->R){nMin

=

min(pRoot->nMin,nMin);nMax=max(pRoot->nMax,nMax);return;}if(

e

<=

(pRoot->L

+

pRoot->R)

/

2)Query(pRoot->pLeft,

s,e);else

if(

s

>=

(pRoot->L

+pRoot->R)

/

2

+

1)Query(pRoot->pRight,

s,e);else

{Query(pRoot->pLeft,

s,(pRoot->L+

pRoot->R)

/

2);Query(pRoot->pRight,

(pRoot->L

+

pRoot->R)

/

2+1

,e);}}int

main(){int

n,q,h;int

i,j,k;scanf("%d%d",&n,&q);nCount

=

0;BuildTree(Tree,1,n);for(

i

=

1;i

<=

n;i

++

)

{scanf("%d",&h);Insert(

Tree,i,h);}for(

i

=

0;i

<

q;i

++

)

{int

s,e;scanf("%d%d",

&s,&e);nMax

=

MY_MAX;nMin

=

MY_MIN;Query(Tree,s,e);printf("%d\n",nMax

-nMin);}return

0;}POJ

3468

A

Simple

Problem

with

Integers給定Q

(1≤Q

≤100,000)個數(shù)A1,A2

…AQ,，以及可能多次進行的兩個操作:對某個區(qū)間Ai

…Aj的每個數(shù)都加n(n可變）求某個區(qū)間Ai

…Aj的數(shù)的和本題樹節(jié)點要存哪些信息？只存該區(qū)間的數(shù)的和，行不行？POJ

3468

A

Simple

Problem

with

Integers只存和，會導致每次加數(shù)的時候都要更新到葉子節(jié)點，速度太慢，這是必須要避免的。本題樹節(jié)點結(jié)構(gòu)：struct

CNode{int

L

,R;//區(qū)間起點和終點CNode

*

pLeft,

*

pRight;long

longnSum;//原來的和long

long

Inc;//增量n的累加};//本節(jié)點區(qū)間的和實際上是nSum+Inc*(R-L+1)POJ

3468

A

Simple

Problem

with

Integers在增加時，如果要加的區(qū)間正好覆蓋一個節(jié)點，則增加其節(jié)點的Inc值，不再往下走，否則要更新nSum,再將增量往下傳在查詢時，如果待查區(qū)間不是正好覆蓋一個節(jié)點，就將節(jié)點的Inc往下帶，然后將Inc代表的所有增量累加到nSum上后將Inc清0，接下來再往下查詢。#include

<iostream>using

namespace

std;struct

CNode{int

L

,R;CNode

*

pLeft,

*

pRight;long

long

nSum;//原來的和

long

long

Inc;//增量c的累加};CNode

Tree[1000000];int

nCount

=

0;int

Mid(

CNode

*

pRoot){return

(pRoot->L

+

pRoot->R)/2;}void

BuildTree(CNode

*

pRoot,int

L,

int

R){pRoot->L

=L;pRoot->R=

R;pRoot->nSum

=

0;pRoot->Inc

=0;if(

L

==

R)return;nCount

++;pRoot->pLeft

=

Tree

+

nCount;nCount

++;pRoot->pRight

=

Tree

+

nCount;BuildTree(pRoot->pLeft,L,(L+R)/2);BuildTree(pRoot->pRight,(L+R)/2+1,R);}void

Insert(

CNode

*

pRoot,int

i,

int

v){if(

pRoot->L

==

i

&&

pRoot->R

==

i)

{pRoot->nSum

=

v;return

;}pRoot->nSum

+=

v;if(

i

<=

Mid(pRoot))Insert(pRoot->pLeft,i,v);elseInsert(pRoot->pRight,i,v);}void

Add(

CNode

*

pRoot,

int

a,

int

b,

long

long

c){if(

pRoot->L

==

a

&&

pRoot->R

==b)

{pRoot->Inc

+=

c;return;}pRoot->nSum

+=

c

*

(

b

-

a

+

1)

;if(

b<=

(pRoot->L

+

pRoot->R)/2)Add(pRoot->pLeft,a,b,c);else

if(

a

>=

(pRoot->L

+

pRoot->R)/2

+1)Add(pRoot->pRight,a,b,c);else

{Add(pRoot->pLeft,a,(pRoot->L

+

pRoot->R)/2

,c);Add(pRoot->pRight,(pRoot->L

+pRoot->R)/2

+1,b,c);}}long

long

QuerynSum(

CNode

*

pRoot,

int

a,

int

b){if(

pRoot->L

==

a

&&

pRoot->R

==

b)return

pRoot->nSum

+(pRoot->R

-

pRoot->L

+

1)*

pRoot->Inc

;pRoot->nSum

+=

(pRoot->R

-pRoot->L

+

1)

*

pRoot->Inc

;Add(

pRoot->pLeft,pRoot->L,Mid(pRoot),pRoot->Inc);Add(

pRoot->pRight,Mid(pRoot)

+

1,pRoot->R,pRoot->Inc);pRoot->Inc

=

0;if(

b

<=

Mid(pRoot))return

QuerynSum(pRoot->pLeft,a,b);else

if(

a

>=

Mid(pRoot)

+

1)return

QuerynSum(pRoot->pRight,a,b);else

{return

QuerynSum(pRoot->pLeft,a,Mid(pRoot))

+QuerynSum(pRoot->pRight,Mid(pRoot)

+

1,b);}}int

main(){int

n,q,a,b,c;char

cmd[10];scanf("%d%d",&n,&q);int

i,j,k;nCount

=

0;BuildTree(Tree,1,n);for(

i

=

1;i<=

n;i++

)

{scanf("%d",&a);Insert(Tree,i,a);}for(

i

=

0;i<

q;i

++

)

{scanf("%s",cmd);if

(

cmd[0]

==

'C'

)

{scanf("%d%d%d",&a,&b,&c);Add(

Tree,a,b,c);}else

{scanf("%d%d",&a,&b);printf("%I64d\n",QuerynSum(Tree,a,b));}}return0;}離散化有時，區(qū)間的端點不是整數(shù)，或者區(qū)間太大導致建樹內(nèi)存開銷過大MLE

,那么就需要進行“離散化”后再建樹。POJ

2528

Mayor's

posters給定一些海報，可能互相，告訴你每個海報寬度（高度都一樣）和先后疊放次序，問沒有被完全蓋住的海報有多少張。海報最多10,000張，但是墻有10,000,000塊瓷磚長。海報端點不會落在瓷磚中間。POJ

2528

Mayor's

posters如果每個葉子節(jié)點都代表一塊瓷磚，那么線段樹會導致MLE，即單位區(qū)間的數(shù)目太多。實際上，由于最多10,000個海報，共計20,000個端點，這些端點把墻最多分成19,999個單位區(qū)間（題意為整個墻都會被蓋到）只要對這19,999個區(qū)間

，然后建樹即可。這就是離散化。POJ

2528

Mayor's

posters.這些單位區(qū)間

段樹上是葉子節(jié)點.每個單位區(qū)間要么全被覆蓋，要么全部露出.沒有海報的端點會落在一個單位區(qū)間.每張海報一定完整覆蓋若干個連續(xù)的單位區(qū)間.要算出一共有多少個單位區(qū)間，并且算出每張海報覆蓋的單位區(qū)間[a,b](海報覆蓋了從a號單位區(qū)間到b號單位區(qū)間）按上圖的離散化方法，求每張海報覆蓋了哪些單位區(qū)間比較慢nlog(n)，或比較難想更好的離散化方法，是將所有海報的端點瓷磚排序，把每個海報的端點瓷磚都看做一個單位區(qū)間，兩個相鄰的端點瓷磚之間的部分是一個單位區(qū)間這樣最多會有20000+19999個單位區(qū)間數(shù)據(jù)的順序

------

從上往下依關(guān)鍵：次每張海報，這樣后能覆蓋先 的海報，因此的海報不可一張海報時，如果發(fā)現(xiàn)海報對應區(qū)間有一部分露出來，就說明該海報部分可見。POJ

2528

Mayor's

posters如果海報端點坐標是浮點數(shù)，其實也一樣處理。樹節(jié)點要保存哪些信息，而且這些信息該如何動態(tài)更新呢？POJ

2528

Mayor's

postersstruct

CNode{int

L,R;bool

bCovered;CNode

*

pLeft,

*

pRight;};bCovered表示本區(qū)間是否已經(jīng)完全被海報蓋住#include

<iostream>#include

<algorithm>#include

<math.h>using

namespace

std;int

n;struct

CPost{int

L,R;};CPost

posters[10100];int

x[20200];int

hash[10000010];//hash[i]表示瓷磚i所處的離散化后的區(qū)間

struct

CNode{int

L,R;bool

bCovered;//區(qū)間[L,R]是否已經(jīng)被完

CNode

*

pLeft,*

pRight;};CNode

Tree[1000000];int

nNodeCount

=

0;int

Mid(

CNode

*

pRoot){return

(pRoot->L

+

pRoot->R)/2;}void

BuildTree(

CNode

*

pRoot,

int

L,

int

R){pRoot->L

=L;pRoot->R=

R;pRoot->bCovered

=

false;if(

L

==

R

)return;nNodeCount

++;pRoot->pLeft

=

Tree

+

nNodeCount;nNodeCount

++;pRoot->pRight

=

Tree

+

nNodeCount;BuildTree(

pRoot->pLeft,L,(L+R)/2);BuildTree(

pRoot->pRight,(L+R)/2

+

1,R);}bool

Post(

CNode *pRoot,

int

L,

int

R){//

一張正好覆蓋區(qū)間[L,R]的海報,返回true則說明區(qū)間[L,R]是部分或全部可見的if(

pRoot->bCovered

) return

false;if(

pRoot->L

==

L

&&

pRoot->R

==

R){pRoot->bCovered

=

true;return

true;}bool

bResult

;if(

R

<=

Mid(pRoot)

)bResult

=

Post(

pRoot->pLeft,L,R);else

if(

L

>=

Mid(pRoot)

+

1)bResult

=

Post(

pRoot->pRight,L,R);else

{bool

b1

=

Post(pRoot->pLeft

,L,Mid(pRoot));bool

b2

=

Post(

pRoot->pRight,Mid(pRoot)

+

1,R);bResult

=

b1

||

b2;}//要更新根節(jié)點的覆蓋情況if(

pRoot->pLeft->bCovered

&&pRoot->pRight->bCovered

)pRoot->bCovered

=

true;return

bResult;}int

main(){int

t;

int

i,j,k;scanf("%d",&t);int

nCaseNo

=

0;while(t--)

{nCaseNo

++;scanf("%d",&n);int

nCount

=

0;for(

i

=

0;i

<

n;i

++

)

{scanf("%d%d",

&

posters[i].L,&

posters[i].R

);x[nCount++]

=

posters[i].L;x[nCount++]

=

posters[i].R;}sort(x,x+nCount);nCount=unique(x,x+nCount)-x;//去掉重復元素//下面離散化int

nIntervalNo=

0;for(

i

=

0;i

<

nCount;i

++

)

{hash[x[i]]

=

nIntervalNo;if(

i

<

nCount

-

1)

{if(

x[i+1]

-

x[i]

==1)nIntervalNo

++;elsenIntervalNo

+=

2;}}BuildTree(

Tree,0,nIntervalNo

);int

nSum

=

0;for(

i=n-1;i>=0;i--){//從后往前看每個板是否可見if(

Post(Tree,hash[posters[i].L],hash[posters[i].R]))nSum

++;}printf("%d\n",nSum);}return

0;}POJ

1151

Atlantis給定一些矩形，其頂點坐標是浮點數(shù)，可能互相，問這些矩形覆蓋到的面積是多大。用線段樹做，先要離散化！！POJ

1151

Atlantis在Y軸進行離散化。n個矩形的2n個橫邊縱坐標共構(gòu)成最多2n-1個區(qū)間的邊界，對這些區(qū)間

，建立起線段樹。POJ

1151

Atlantis線段樹的節(jié)點要保存哪些信息？如何將一個個矩形線段樹？過程中這些信息如何更新？怎樣查詢？POJ

1151

Atlantisstruct

CNode{int

L,R;CNode

*

pLeft,

*

pRight;double

Len;//當前,本區(qū)間上有多長的部分是落在那些矩形中的int

Covers;//本區(qū)間當前被多少個矩形完全包含};一開始，所有區(qū)間

Len

=

0 Covers

=

0POJ

1151

Atlantis數(shù)據(jù)的順序：將矩形的縱邊從左到右排序，然后依次將這些縱邊線段樹。要記住哪些縱邊是一個矩形的左邊(開始邊)，哪些縱邊是一個矩形的右邊（結(jié)束邊），時，對Len和Covers做不同的修改。一條邊后,就根據(jù)根節(jié)點的Len

值增加總覆蓋面積的值。增量是Len

*

本邊到下一條邊的距離#include

<iostream>#include

<algorithm>#include

<math.h>#include

<set>using

namespace

std;double

y[210];struct

CNode{int

L,R;CNode

*

pLeft,

*

pRight;double

Len;//當前,本區(qū)間上有多長的部分是落在那些矩形中的int

Covers;//本區(qū)間當前被多少個矩形完全包含};CNode

Tree[1000];struct

CLine{double

x,y1,y2;bool

bLeft;//是否是矩形的左邊}

lines[210];int

nNodeCount

=

0;bool

operator<

(

const

CLine

&

l1,const

CLine

&

l2){return

l1.x

<

l2.x;}template

<class

F,class

T>

F

bin_search(F

s,

F

e,

T

val){F

L

=

s;F

R

=

e

-

1;while(L

<=

R

)

{F

mid=

L

+

(R-L)/2;if(

!(

*

mid

<

val ||

val

<

*

mid

))return

mid;else

if(val

<

*

mid)R

=

mid

-

1;elseL

=

mid

+

1;}returne;}int

Mid(CNode

*

pRoot){return

(pRoot->L

+

pRoot->R

)>>1;}void

Insert(CNode

*

pRoot,int

L,

int

R)矩形左邊的一部分或全部，該左邊的一部分或全//在區(qū)間pRoot部覆蓋了區(qū)間[L,R]{if(

pRoot->L

==

L

&&

pRoot->R

==R){pRoot->Len

=

y[R+1]

-

y[L];pRoot->Covers

++;return;}if(

R

<=

Mid(pRoot))Insert(pRoot->pLeft,L,R);else

if(

L

>=

Mid(pRoot)+1)Insert(pRoot->pRight,L,R);else

{Insert(pRoot->pLeft,L,Mid(pRoot));Insert(pRoot->pRight,Mid(pRoot)+1,R);}if(

pRoot->Covers==0)

//如果不為0，則說明本區(qū)間當前仍然被某個矩形完全包含，則不能更新LenpRoot->Len

=

pRoot->pLeft

->Len

+pRoot->pRight

->Len;}void

Delete(CNode

*

pRoot,int

L,

int

R)

{/在區(qū)間pRoot

刪除矩形右邊的一部分或全部，該矩形右邊的一部分或全部覆蓋了區(qū)間[L,R]if(

pRoot->L

==

L

&&

pRoot->R

==

R)

{pRoot->Covers

--;if(

pRoot->Covers

==

0

)if(

pRoot->L

==

pRoot->R

)pRoot->Len

=

0;elsepRoot->Len

=

pRoot->pLeft

->Len

+pRoot->pRight

->Len;return

;}if(

R

<=

Mid(pRoot))Delete(pRoot->pLeft,L,R);else

if(

L

>=

Mid(pRoot)+1)Delete(pRoot->pRight,L,R);else

{Delete(pRoot->pLeft,L,Mid(pRoot));Delete(pRoot->pRight,Mid(pRoot)+1,R);}if(pRoot->Covers==0)//如果不為0，則說明本區(qū)間當前仍然被某個矩形完全包含，則不能更新LenpRoot->Len

=

pRoot->pLeft

->Len

+

pRoot->pRight

->Len;}void

BuildTree(

CNode

*

pRoot,

int

L,int

R){pRoot->L

=L;pRoot->R=

R;pRoot->Covers

=

0;pRoot->Len=

0;if(

L

==

R)return;nNodeCount

++;pRoot->pLeft

=

Tree

+

nNodeCount;nNodeCount

++;pRoot->pRight

=

Tree

+

nNodeCount;BuildTree(

pRoot->pLeft,L,(L+R)/2);BuildTree(

pRoot->pRight,(L+R)/2+1,R);}int

main(){int

n;int

i,j,k; double

x1,y1,x2,y2; int

yc,lc;int

nCount

=

0;int

t

=

0;while(true)

{scanf("%d",&n);if(

n

==

0)

break;t

++; yc

=

lc

=

0;for(

i

=

0;i

<

n;i

++

)

{scanf("%lf%lf%lf%lf",&x1,

&y1,&x2,&y2);y[yc++]

=y2;lines[lc].y1

=

y1;y[yc++]

=y1;lines[lc].x

=

x1;lines[lc].y2

=

y2;lines[lc].bLeft

=

true;lc

++;lines[lc].x

=

x2;

lines[lc].y1

=

y1;lines[lc].y2

=

y2;lines[lc].bLeft

=

false;lc

++;}sort(y,y

+

yc);yc

=

unique(y,y+yc)

-

y;nNodeCount

=

0;//yc是橫線的條數(shù)，yc-1是縱向區(qū)間的個數(shù)，這些區(qū)間從0//開始

，那么最后一個區(qū)間//

就是yc-1-1BuildTree(Tree,

0,

yc

-

1

-

1);sort(lines,lines

+

lc);double

Area

=

0;for(

i

=

0;i

<

lc

-

1

;

i

++

)

{int

L

=

bin_search(

y,y+yc,lines[i].y1)

-

y;int

R=

bin_search(

y,y+yc,lines[i].y2)

-y;if(

lines[i].bLeft

)Insert(Tree,L,R-1);elseDelete(Tree,L,R-1);Area

+=

Tree[0].Len

*

(lines[i+1].x

-

lines[i].x);}printf("Test

case

#%d\n",t);printf("Total

explored

area:%.2lf\n",Area);printf("\n",Area);}return0;}有時，不一定能夠一眼看出

“區(qū)間”，這就要靠仔細觀察，造出“區(qū)間”來。例如：POJ

3321

Apple

Tree每個分叉點及末梢可能有蘋果（最多1個），每次可以摘掉一個蘋果，或有一個蘋果新長出來，隨時查詢某個分叉點往上的子樹里，一共有多少個蘋果。POJ

3321

Apple

Tree深度優(yōu)先遍歷整個蘋果樹，為每個節(jié)點標記一個開始時間和結(jié)束時間（所有時間都不相同），顯然子樹里面所有節(jié)點的開始和結(jié)束時間，都位于子樹樹根的開始和結(jié)束時間之間。問題變成：有n個節(jié)點，就有2n個開始結(jié)束時間，它們構(gòu)成序列A1A2….A2n序列里每個數(shù)是0或者1，可變化，隨時查詢某個區(qū)間里數(shù)的和。當然由于蘋果樹上每個放蘋果的位置對應于數(shù)列里的兩個數(shù)，所以結(jié)果要除以2樹狀數(shù)組對于序列a，

設(shè)一個數(shù)組CC[i]

=

a[i

–

2k

+

1]

+

…

+

a[i]k為i在二進制下末尾0的個數(shù)2k就是i

保留最右邊的1，其余位全變0i從1開始算！C即為a的樹狀數(shù)組對于i,如何求2k

？2k=i

&(i^(i-1))也就是i&(-i)以6為例(6)10=(0110)2xorand通常6-1=(5)10=(0101)2(0011)2(6)10=

(0110)2(0010)2

=

(4)10用lowbit(x)表示x對應的2k

,lowbit(x)

=

x&(-x)lowbit(x)

實際上就是x的二進制表示形式留下最右邊的1，其他位都變成0C[i]=a[i-lowbit(i)+1]+…+a[i]C包含哪些項看上去沒有規(guī)律C1=A1C2=A1+A2C3=A3C4=A1+A2+A3+A4C5=A5C6=A5+A6C7=A7C8=A1+A2+A3+A4+A5+A6+A7+A8…………C16=A1+A2+A3+A4+A5+A6+A7+A8+A9+A10+A11+A12+A13+A14+A15+A16樹狀數(shù)組圖示樹狀數(shù)組的好處在于能快速求任意區(qū)間的和a[i]

+

a[i+1]

+

…

+

a[j]設(shè)sum(k)=a[1]+a[2]+…+a[k]則a[i]+a[i+1]+…+a[j]=sum(j)-sum(i-1)有了樹狀數(shù)組，sum(k)就能在O(logN)時間內(nèi)求出，N是a數(shù)組元素個數(shù)。而且更新一個a的元素所花的時間也是O(logN)的(a更新了C也得更新)。為什么呢？根據(jù)C的構(gòu)成規(guī)律，可以發(fā)現(xiàn)sum(k)可以表示為：sum(k)

=

C[n1]+C[n2]

+

…+

C[nm]其中nm=kni-1=ni

-lowbit(ni)而且n1

–lowbit(n1

)必須小于或等于0(其實只能等于0）,n1大于0如：sum(6)=C[4]+C[6]lowbit(x)

實際上就是x的二進制表示形式留下最右邊的1，其他位都變成0那么，sum(k)最多有幾項呢？這個決定了求區(qū)間和的時間復雜度那么，sum(k)最多有幾項呢？sum(k)=C[n1]+C[n2]+…+C[nm]其中nm=kni-1

=

ni

-

lowbit(ni)lowbit(x)

實際上就是x的二進制表示形式留下最右邊的1，其他位都變成0ni

-lowbit(ni)是什么樣子？就是ni的二進制去掉最右邊的1k

的二進制里最多有幾個1？log2

k

（向上取整）個sum(k)最多l(xiāng)og2

k（向上取整）項，所以本次求和的復雜度就是log2

k那么，為什么sum(k)

=

C[n1]+C[n2]

+

…+

C[nm]其中nm=kni-1

=

ni

-

lowbit(ni)證：C[i]

=

a[i-lowbit(i)+1]

+

…+

a[i]i-lowbit(i)+1

是什么？就是i把最右邊的1去掉，然后再加1那么，為什么sum(k)=a[1]+a[2]+…+a[k]=C[n1]+C[n2]+…+C[nm](其中nm=k)證明：C[nm]

=

a[nm-lowbit(nm)+1]

+

…

+

a[nm]C[nm-1]

=

a[nm-1-lowbit(nm-1)+1]

+

…

+a[nm-1]=

a[nm-1-lowbit(nm-1)+1]

+

…

+

a[nm-lowbit(nm)]C[nm-2]

=

a[nm-2-lowbit(nm-2)+1]

+

…

+

a[nm-2]=

a[nm-1-lowbit(nm-1)+1]

+

…

+

a[nm-1-lowbit(nm-1)]……..C[n1]

=

a[n1-lowbit(n1)+1]

+

…+

a[n1]=

a[1]

+

…+

a[n1](因n1-lowbit(n1)必須等于0，否則就還需要C[n1-lowbit(n1)]了)更新一個a元素，C也要跟著更新，復雜度是多少呢即C里有幾項要更新呢？C1=A1C2=A1+A2C3=A3C4=A1+A2+A3+A4C5=A5C6=A5+A6C7=A7C8=A1+A2+A3+A4+A5+A6+A7+A8…………C16=A1+A2+A3+A4+A5+A6+A7+A8+A9+A10+A11+A12+A13+A14+A15+A16更新一個a元素，C也要跟著更新，復雜度是多少呢即C里有幾項要更新呢？如果a[i]更新了，那么以下的幾項都需要更新：C[n1],

C[n2],

…C[nm]其中，n1

=i

，ni+1=ni

+lowbit(ni)nm

+lowbit(nm)必須大于a

的元素個數(shù)N,

nm小于等于N同理，總的來說更新一個元素的時間，也是logN的為什么如果a[i]更新了，那么有且僅有以下的幾項需要更新：C[n1],

C[n2],

…C[nm]其中，n1

=i

，ni+1=ni

+lowbit(ni)a[i]更新->C[i]必須更新C[i]更新->C[i+lowbit(i)]必須更新:C[i+lowbit(i)]

=

a[

(i+lowbit(i))

–

lowbit(i+lowbit(i))

+1]

+….

+a[i+lowbit(i)]證明i+lowbit(i)–lowbit(i+lowbit(i))+1<=i，就證明

C[i+lowbit(i)]要更新lowbit(i)顯然比lowbit(i+lowbit(i))要小所以i+lowbit(i)–lowbit(i+lowbit(i))+1<=i下面要證明，若C[i]更新,則對任何k,(i<k<i+lowbit(i)),C[k]都不需要更新（

C[k]不包含a[i])C[k]

=

a[k-lowbit(k)+1]

+

…

+

a[k]只要證明k-lowbit(k)+1比i大即可因

i<k

<i+lowbit(i)

,假設(shè)i的最右邊的1是從右到左從0開始數(shù)的第n位，那么i+lowbit(i)就是將i的低n位全變成1后，再加1。那么k一定是從第n位到最

都和i相同，但是低n位比i大(即k低n位中有1，因i低n位全是0)k-lowbit(k)+1就是k去掉最右邊的1，然后再加1，那當然還是比i大初始狀態(tài)下由a構(gòu)建樹狀數(shù)組C的時間復雜度是多少？顯然是O(N)的因為C[k]

=

sum(k)

–

sum(k-lowbit(k))證：sum(k)

=

C[n1]+C[n2]

+

…+

C[nm-1]

+C[nm]

(nm

=

k)nm-1

=

k-lowbit(k)sum(k-lowbit(k))

=

C[n1]+C[n2]

+

…+

C[nm-1]所以，樹狀數(shù)組適合單個元素經(jīng)常修改而且還反復要求部分的區(qū)間的和的情況。上述問題雖然也可以用線段樹解決，但是用樹狀數(shù)組來做，編程效率和程序運行效率都更高（時間復雜度相同，但是樹狀數(shù)組常數(shù)?。┤绻看我薷牡牟皇菃蝹€元素，而是一個

區(qū)間，那就不能用樹狀數(shù)組了(效率過低）。POJ

3321

Apple

Tree每個分叉點及末梢可能有蘋果（最多1個），每次可以摘掉一個蘋果，或有一個蘋果新長出來，隨時查詢某個分叉點往上的子樹里，一共有多少個蘋果。此題可用樹狀數(shù)組來做Sample

Input31

21

33Q

1C

2Q1Sample

Output32根據(jù)題意，一開始時，所有能長蘋果的地方都有蘋果//樹狀數(shù)組做/*一棵樹上長了蘋果，每一個樹枝節(jié)點上有長蘋果和不長蘋果

兩種狀態(tài)，兩種操作，一種操作能夠改變樹枝上蘋果的狀態(tài)，另一種操作詢問某一樹枝節(jié)點一下的所有的蘋果有多少。具體做法是做一次dfs，記下每個節(jié)點的開始時間Start[i]和結(jié)束時間End[i]，那么對于i節(jié)點的所有子孫的開始時間和結(jié)束時間都應位于Start[i]和End[i]之間，另外用一個數(shù)組C[i]記錄附加在節(jié)點i上的蘋果的個數(shù)，然后用樹狀數(shù)組統(tǒng)計Start[i]到End[i]之間的附加蘋果總數(shù)。這里用樹狀數(shù)組統(tǒng)計區(qū)間可以用Sum(Start[i])-Sum(End[i]-1)來計算。*/#include

<iostream>#include

<vector>using

namespace

std;#define

MY_MAX

220000int

C[MY_MAX];typedef

vector<int>

VCT_INT;vector<VCT_INT>

G(MY_MAX/2);int

Lowbit[MY_MAX];bool

HasApple[MY_MAX/2];int

Start[MY_MAX];//dfs時的開始時間

int

End[MY_MAX];//dfs時的結(jié)束時間

int

nCount=0;void

Dfs(int

v){Start[v]

=

++

nCount;for(

int

i

=

0;i

<

G[v].size();i

++

)Dfs(G[v][i]);End[v]

=

++

nCount;}int

QuerySum(int

p){int

nSum

=0;while(

p

>

0

)

{nSum

+=

C[p];p-=

Lowbit[p];}return

nSum;}void

Modify(

int

p,int

val){while(

p

<=

nCount)

{C[p]

+=

val;p

+=

Lowbit[p];}}int

main(){int

n;scanf("%d",&n);int

x,y;int

i,j,k;//建圖for(

i

=

0;i

<

n

-1

;i

++

)

{int

a,b;scanf("%d%d",&a,&b);G[a].push_back(b);}nCount

=

0;Dfs(1);//樹狀數(shù)組要處理的原始數(shù)組下標范圍1--

nCountfor(

i

=

1;i

<=

nCount;i

++)

{Lowbit[i]

=

i

&

(

i

^(

i

-

1));}for(

i

=

1;i

<=

n;i

++

)HasApple[i]

=

1;intm;//求C數(shù)組，即樹狀數(shù)組的節(jié)點的值

for(

i=1;i<=nCount;i++)C[i]

=

i

-

(i

-

Lowbit[i]

+

1)

+

1;scanf("%d",&m);for(

i

=

0;i

<

m;i

++

)

{char

cmd[10];inta;scanf("%s%d",cmd,&a);if(

cmd[0]

==

'C'

)

{if(

HasApple[a]

)

{Modify(

Start[a],-1); Modify(

End[a],-1);HasApple[a]

=

0;}else

{Modify(

Start[a],1);

Modify(End[a],1);HasApple[a]

=

1;}}else

{int

t1

=

QuerySum(End[a]);int

t2

=QuerySum(Start[a]);printf("%d\n",(QuerySum(End[a])

–QuerySum(Start[a]))/2

+

HasApple[a]);}}}二維樹狀數(shù)組原始數(shù)組和樹狀數(shù)組都是二維的C[x][y]

=

∑

{a[i][j]}x-lowbit[x]+1

<=

i

<=xy-lowbit[y]+1

<=

j

<=ySum[x][y]=∑{C[i][j]} (從[1,1]

到[x,y]這個矩陣里的所有元素的和）i1=x,

i2

=i1-lowbit(i1),

…ik

=

ik-1-lowbit(ik-1)

…..j1=y,

j2

=

j1-lowbit(j1),

…jk

=

jk-1-lowbit(jk-1)

…..用于快速求數(shù)字子矩陣的和,更新和查詢的時間復雜度都是log(n)*log(m)(n,m分別為兩維的大小)POJ

1195

Mobile

phones一個由數(shù)字構(gòu)成的大矩陣，開始是全0,能進行兩種操作對矩陣里的某個數(shù)加上一個整數(shù)（可正可負）查詢某個子矩陣里所有數(shù)字的和要求對每次查詢，輸出結(jié)果Sample

Input0

41

1

2

32

0

0

2

21

1

1

21

1

2

-12

1

1

2

33Sample

Output34//下面為二維樹狀數(shù)組解法

#include<iostream>#include<vector>using

namespace

std;#define

MY_MAX

1100int

C[MY_MAX][MY_MAX];int

Lowbit[MY_MAX];int

s;void

Add(

int

y,

int

x,int

a){while(

y

<=

s

)

{int

tmpx

=

x;while(

tmpx

<=

s

)

{C[y][tmpx]

+=

a;tmpx

+=

Lowbit[tmpx];}y

+=

Lowbit[y];}}int

QuerySum(

int

y,

int

x)//查詢第1行到第y行，第1列到第x列的和{int

nSum

=0;while(y

>

0

)

{int

tmpx

=x;while(

tmpx

>

0)

{nSum

+=

C[y][tmpx];tmpx

-=

Lowbit[tmpx];}y

-=Lowbit[y];}return

nSum;}int

main()

{intcmd; int

x,y,a,l,b,r,t; int

i,j,k; int

n1,n2;for(

i

=

1;i

<=

MY_MAX;i

++

)

Lowbit[i]

=

i

&

(

i

^(i

-

1));while(

true)

{scanf("%d",&cmd);switch(

cmd)

{case

0:scanf("%d",&s);memset(C,0,sizeof(C));break;case

1:scanf("%d%d%d",&x

,&y,&a);Add(

y

+

1,x

+1,

a);break;case2:scanf("%d%d%d%d",&l

,

&b,

&r,&t);int

n1,n2,n3,n4;l

++;

b++;

r

++;

t++;printf("%d\n",QuerySum(t,r)

+QuerySum(b-1,l-1)

-

QuerySum(t,l-1)

-

QuerySum(b-1,r));break;case

3: return0;}}}二維線段樹一維線段樹的每個節(jié)點代表一個一維區(qū)間，那么二維線段樹的每個節(jié)點就代表一個二維區(qū)間（一個矩陣）二維線段樹是一棵4叉樹。如果一個節(jié)點代表的區(qū)間是矩陣[x1,y1]–[x2,y2]，那么它的四個子節(jié)點代表的區(qū)間分別為[x1,y1]

–

[(x1+x2)/2,

(y1+y2)/2][x1,(y1+y2)/2+1]

–

[(x1+x2)/2,y2][

(x1+x2)/2+1,y1]

–

[x2,

(y1+y2)/2][(x1+x2)/2+1,

(y1+y2)/2+1]

–

[x2,y2]二維線段樹二維線段樹的四叉樹實現(xiàn)形式，請參考：http

/menjitianya/archive/2011/04/03/143374.html二維線段樹還可以用樹套樹方式實現(xiàn)，即每個外層線段樹的節(jié)點對應于一棵內(nèi)層線段樹。如果外層線段樹根對應的區(qū)間是x方向的[1,n]，內(nèi)層線段樹根節(jié)點對應的區(qū)間是y方向的[1,m],那么整個線段樹可以存在一個n行m列的二維數(shù)組里。樹套樹方式

、修改、查找等時間復雜度為O(log(n)*log(m))。用二維線段樹做POJ

1195

Mobile

phones#include

<iostream>using

namespace

std;#d