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

課程網(wǎng)頁(yè)http

/JudgeOnline/summerschool/pku_acm_train.htm上機(jī)地點(diǎn)：理科1號(hào)樓1235線段樹(shù)和樹(shù)狀數(shù)組信息學(xué)院線段樹(shù)(Interval

Tree)實(shí)際上還是稱為區(qū)間樹(shù)更好理解一些。樹(shù)：是一棵樹(shù)，而且是一棵二叉樹(shù)。線段：樹(shù)上的每個(gè)節(jié)點(diǎn)對(duì)應(yīng)于一個(gè)線段(還是叫

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

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

9]的線段樹(shù)[1,9][1,5][6,9][1,3]3[1,2][4,5]

[6,7]

[8,9]4

5

6

7

891

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

+1

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

9]的線段樹(shù)上，區(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ī)則就是：如果有某個(gè)節(jié)點(diǎn)代表的區(qū)間，完全屬于待分解區(qū)間，則該節(jié)點(diǎn)為“終止”節(jié)點(diǎn)，不再繼續(xù)往下分解所有“終止”節(jié)點(diǎn)所代表的區(qū)間都不

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

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

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

以節(jié)點(diǎn)v為根建樹(shù)、v對(duì)應(yīng)區(qū)間為[l,r]{對(duì)節(jié)點(diǎn)v初始化if

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

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

Ai的節(jié)點(diǎn)的Sum進(jìn)行加操作，因此復(fù)雜度是

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

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

3264

Balanced

Lineup給定Q

(1≤Q

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

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

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

3264

Balanced

Lineup給定Q

(1≤Q

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

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

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

CNode{int

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

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

*

pLeft,

*

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

*

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

Input6

3

//6個(gè)數(shù)，3次個(gè)查詢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];//其實(shí)兩倍葉子節(jié)點(diǎn)的數(shù)量就夠

int

nCount=0;//總節(jié)點(diǎn)數(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)線段樹(shù)//將第i個(gè)數(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)個(gè)數(shù)A1,A2

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

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

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

3468

A

Simple

Problem

with

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

CNode{int

L

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

*

pLeft,

*

pRight;long

longnSum;//原來(lái)的和long

long

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

3468

A

Simple

Problem

with

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

<iostream>using

namespace

std;struct

CNode{int

L

,R;CNode

*

pLeft,

*

pRight;long

long

nSum;//原來(lái)的和

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;}離散化有時(shí)，區(qū)間的端點(diǎn)不是整數(shù)，或者區(qū)間太大導(dǎo)致建樹(shù)內(nèi)存開(kāi)銷(xiāo)過(guò)大MLE

,那么就需要進(jìn)行“離散化”后再建樹(shù)。POJ

2528

Mayor's

posters給定一些海報(bào)，可能互相，告訴你每個(gè)海報(bào)寬度（高度都一樣）和先后疊放次序，問(wèn)沒(méi)有被完全蓋住的海報(bào)有多少?gòu)垺：?bào)最多10,000張，但是墻有10,000,000塊瓷磚長(zhǎng)。海報(bào)端點(diǎn)不會(huì)落在瓷磚中間。POJ

2528

Mayor's

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

，然后建樹(shù)即可。這就是離散化。POJ

2528

Mayor's

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

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

------

從上往下依關(guān)鍵：次每張海報(bào)，這樣后能覆蓋先 的海報(bào)，因此的海報(bào)不可一張海報(bào)時(shí)，如果發(fā)現(xiàn)海報(bào)對(duì)應(yīng)區(qū)間有一部分露出來(lái)，就說(shuō)明該海報(bào)部分可見(jiàn)。POJ

2528

Mayor's

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

2528

Mayor's

postersstruct

CNode{int

L,R;bool

bCovered;CNode

*

pLeft,

*

pRight;};bCovered表示本區(qū)間是否已經(jīng)完全被海報(bào)蓋住#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]的海報(bào),返回true則說(shuō)明區(qū)間[L,R]是部分或全部可見(jiàn)的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é)點(diǎn)的覆蓋情況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;//去掉重復(fù)元素//下面離散化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--){//從后往前看每個(gè)板是否可見(jiàn)if(

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

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

0;}POJ

1151

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

1151

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

，建立起線段樹(shù)。POJ

1151

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

1151

Atlantisstruct

CNode{int

L,R;CNode

*

pLeft,

*

pRight;double

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

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

Len

=

0 Covers

=

0POJ

1151

Atlantis數(shù)據(jù)的順序：將矩形的縱邊從左到右排序，然后依次將這些縱邊線段樹(shù)。要記住哪些縱邊是一個(gè)矩形的左邊(開(kāi)始邊)，哪些縱邊是一個(gè)矩形的右邊（結(jié)束邊），時(shí)，對(duì)Len和Covers做不同的修改。一條邊后,就根據(jù)根節(jié)點(diǎn)的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;//當(dāng)前,本區(qū)間上有多長(zhǎng)的部分是落在那些矩形中的int

Covers;//本區(qū)間當(dāng)前被多少個(gè)矩形完全包含};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，則說(shuō)明本區(qū)間當(dāng)前仍然被某個(gè)矩形完全包含，則不能更新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，則說(shuō)明本區(qū)間當(dāng)前仍然被某個(gè)矩形完全包含，則不能更新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ū)間的個(gè)數(shù)，這些區(qū)間從0//開(kāi)始

，那么最后一個(gè)區(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;}有時(shí)，不一定能夠一眼看出

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

3321

Apple

Tree每個(gè)分叉點(diǎn)及末梢可能有蘋(píng)果（最多1個(gè)），每次可以摘掉一個(gè)蘋(píng)果，或有一個(gè)蘋(píng)果新長(zhǎng)出來(lái)，隨時(shí)查詢某個(gè)分叉點(diǎn)往上的子樹(shù)里，一共有多少個(gè)蘋(píng)果。POJ

3321

Apple

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

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

=

a[i

–

2k

+

1]

+

…

+

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

保留最右邊的1，其余位全變0i從1開(kāi)始算！C即為a的樹(shù)狀數(shù)組對(duì)于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對(duì)應(yīng)的2k

,lowbit(x)

=

x&(-x)lowbit(x)

實(shí)際上就是x的二進(jìn)制表示形式留下最右邊的1，其他位都變成0C[i]=a[i-lowbit(i)+1]+…+a[i]C包含哪些項(xiàng)看上去沒(méi)有規(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ù)組圖示樹(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ù)狀數(shù)組，sum(k)就能在O(logN)時(shí)間內(nèi)求出，N是a數(shù)組元素個(gè)數(shù)。而且更新一個(gè)a的元素所花的時(shí)間也是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(其實(shí)只能等于0）,n1大于0如：sum(6)=C[4]+C[6]lowbit(x)

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

=

ni

-

lowbit(ni)lowbit(x)

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

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

的二進(jìn)制里最多有幾個(gè)1？log2

k

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

k（向上取整）項(xiàng)，所以本次求和的復(fù)雜度就是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)]了)更新一個(gè)a元素，C也要跟著更新，復(fù)雜度是多少呢即C里有幾項(xiàng)要更新呢？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更新一個(gè)a元素，C也要跟著更新，復(fù)雜度是多少呢即C里有幾項(xiàng)要更新呢？如果a[i]更新了，那么以下的幾項(xiàng)都需要更新：C[n1],

C[n2],

…C[nm]其中，n1

=i

，ni+1=ni

+lowbit(ni)nm

+lowbit(nm)必須大于a

的元素個(gè)數(shù)N,

nm小于等于N同理，總的來(lái)說(shuō)更新一個(gè)元素的時(shí)間，也是logN的為什么如果a[i]更新了，那么有且僅有以下的幾項(xiàng)需要更新：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]更新,則對(duì)任何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開(kāi)始數(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，那當(dāng)然還是比i大初始狀態(tài)下由a構(gòu)建樹(shù)狀數(shù)組C的時(shí)間復(fù)雜度是多少？顯然是O(N)的因?yàn)镃[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ù)狀數(shù)組適合單個(gè)元素經(jīng)常修改而且還反復(fù)要求部分的區(qū)間的和的情況。上述問(wèn)題雖然也可以用線段樹(shù)解決，但是用樹(shù)狀數(shù)組來(lái)做，編程效率和程序運(yùn)行效率都更高（時(shí)間復(fù)雜度相同，但是樹(shù)狀數(shù)組常數(shù)小）如果每次要修改的不是單個(gè)元素，而是一個(gè)

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

3321

Apple

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

Input31

21

33Q

1C

2Q1Sample

Output32根據(jù)題意，一開(kāi)始時(shí)，所有能長(zhǎng)蘋(píng)果的地方都有蘋(píng)果//樹(shù)狀數(shù)組做/*一棵樹(shù)上長(zhǎng)了蘋(píng)果，每一個(gè)樹(shù)枝節(jié)點(diǎn)上有長(zhǎng)蘋(píng)果和不長(zhǎng)蘋(píng)果

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

int

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

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ù)組要處理的原始數(shù)組下標(biāo)范圍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ù)狀數(shù)組的節(jié)點(diǎn)的值

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ù)組和樹(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]這個(gè)矩陣?yán)锏乃性氐暮停﹊1=x,

i2

=i1-lowbit(i1),

…ik

=

ik-1-lowbit(ik-1)

…..j1=y,

j2

=

j1-lowbit(j1),

…jk

=

jk-1-lowbit(jk-1)

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

1195

Mobile

phones一個(gè)由數(shù)字構(gòu)成的大矩陣，開(kāi)始是全0,能進(jìn)行兩種操作對(duì)矩陣?yán)锏哪硞€(gè)數(shù)加上一個(gè)整數(shù)（可正可負(fù)）查詢某個(gè)子矩陣?yán)锼袛?shù)字的和要求對(duì)每次查詢，輸出結(jié)果Sample

Input0

41

1

2

32

0

0

2

21

1

1

21

1

2

-12

1

1

2

33Sample

Output34//下面為二維樹(shù)狀數(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;}}}二維線段樹(shù)一維線段樹(shù)的每個(gè)節(jié)點(diǎn)代表一個(gè)一維區(qū)間，那么二維線段樹(shù)的每個(gè)節(jié)點(diǎn)就代表一個(gè)二維區(qū)間（一個(gè)矩陣）二維線段樹(shù)是一棵4叉樹(shù)。如果一個(gè)節(jié)點(diǎn)代表的區(qū)間是矩陣[x1,y1]–[x2,y2]，那么它的四個(gè)子節(jié)點(diǎn)代表的區(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]二維線段樹(shù)二維線段樹(shù)的四叉樹(shù)實(shí)現(xiàn)形式，請(qǐng)參考：http

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

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

1195

Mobile

phones#include

<iostream>using

namespace

std;#d