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

第10章線段樹和樹狀數(shù)組∮10.1從一個(gè)實(shí)例入手引例線段覆蓋問題有一根長(zhǎng)度為L(zhǎng)的白色條狀物。有兩種操作：用一條長(zhǎng)度為T的黑布蓋住條狀物的[a,a+T]這個(gè)區(qū)間(0<=a,T<=L)。把某條黑布拿走。輸入L和n次操作，要你輸出每次操作之后：條狀物上有多少個(gè)黑區(qū)間。條狀物上黑區(qū)間的總長(zhǎng)度。001234567891011121314151617181920L=20黑布a=5,T=3輸出1,301234567891011121314151617181920黑布a=7,T=2輸出1,401234567891011121314151617181920撤去黑布a=5,T=3輸出1,201234567891011121314151617181920黑布a=16,T=3輸出2,501234567891011121314151617181920分析1—線性表見上圖示，我們可以用一個(gè)數(shù)組來保存木板的狀態(tài)。Count:array[0..L+1]ofInteger;一開始Count數(shù)組的所有元素置0。如果要添加一根布條(a,T)，那么：foriatoa+T-1doCount[i]Count[i]+1如果要撤掉一根布條(a,T)，那么：foriatoa+T-1doCount[i]Count[i]-1每次要輸有多少個(gè)黑色區(qū)間可以這樣做：Count[L+1]0Interval0fori1toLdoif(Count[i]>0)and(Count[i+1]==0)thenIntervalInterval+1Writeln(Interval)每次要輸出黑色區(qū)間的總長(zhǎng)度：Sum0fori0toL-1ifCount[i]>0thenSumSum+1Writeln(Sum)這種直觀的做法是對(duì)白色條狀物被黑布覆蓋情況的忠實(shí)模擬。雖然編程復(fù)雜度和思維復(fù)雜度都很低，但是時(shí)間復(fù)雜度過高——O(nL)。當(dāng)n和L達(dá)到100000的規(guī)模是，算法就無能為力了。下面我們來看另一種思路。分析2—線段樹整個(gè)條狀物可以看作是一條長(zhǎng)度為L(zhǎng)的線段。建立一棵樹：0~200~200~1010~200~55~105~77~107~88~108~99~10………………代表[a,b]這一段線段a~b根節(jié)點(diǎn)是[0,L]，代表整條線段。然后從根節(jié)點(diǎn)開始，遞歸的將每個(gè)節(jié)點(diǎn)分成盡量等長(zhǎng)的兩段，作為左右子樹；直到節(jié)點(diǎn)變成[a,a+1]的形式為止。這顯然是一顆平衡樹，深度為O(Log2L)，節(jié)點(diǎn)總數(shù)為O(n)（也就是說空間復(fù)雜度為O(n)，建樹的復(fù)雜度也是O(n)）。對(duì)于任意一條線段，我們都可以將其分解成為樹中一些線段來表示：0~200~200~1010~200~55~105~77~107~88~108~99~10………………紅色節(jié)點(diǎn)構(gòu)成了線段[7,20]設(shè)根節(jié)點(diǎn)是Root，節(jié)點(diǎn)X的左孩子是LChild(x)、右孩子是RChild(x)，節(jié)點(diǎn)X代表的線段區(qū)間是[L(x)..R(x)]。那么添加一條黑布[a,b]可以這么進(jìn)行：procedureAdd(Root,a,b);beginifRoot=NILthenExit;if(a<=L(Root))and(b>=R(Root))then{[a,b]完全包含該線段}Count[Root]Count[Root]+1{因?yàn)镽oot代表的線段被覆蓋了，所以將其標(biāo)記}elseif(b<=L(Root)or(a>=R(Root))then{[a,b]和該線段不相交}Exit{不執(zhí)行任何操作}else{[a,b]和Root代表的線段有交集，但是卻不完全包含}beginAdd(LChild(Root),a,b);Add(RChild(Root),a,b);end;end;撤掉一條黑布可以類似的操作，只要把Count[Root]Count[Rotot]+1改成Count[Root]Count[Root]-1即可。那么上面過程的時(shí)間復(fù)雜度是多少呢？我們用f(Root)表示執(zhí)行Add(Root,a,b)的時(shí)間復(fù)雜度。下面我們證明f(Root)~O(Log2n)。如果(a<=L(Root))and(b>=R(Root))，也就是說[a,b]完全包含了Root代表的線段，那么f(Root)=1。否則如果(b<=L(Root)or(a>=R(Root))，也就是說[a,b]和Root代表的線段完全沒有交集，那么f(Root)=1。如果以上兩項(xiàng)都不滿足，那么[a,b]和Root代表的線段有交集，并且不是完全包含。假設(shè)[a,b]和Root的交集是[x,y]。令m=(L(Root)+R(Root))/2，也就是說LChild(Root)代表的線段是[L(Root)..m]，RChild(Root)代表的線段是[m..R(Root)]。首先我們歸納證明，當(dāng)x=LChild(Root)或者y=RChild(Root)時(shí)，f(Root)<=Log2n成立。(這個(gè)我們稱之為引理)其中n=R(Root)-L(Root)，我們對(duì)n進(jìn)行歸納。f(Root)=f(LChild(Root))+f(RChild(Root))1.如果x=L(Root)如果y<=m，那么f(RChild(Root))=0，所以f(Root)=f(LChild(Root))。根據(jù)歸納假設(shè)f(LChild(Root))<=Log2n。所以f(Root)<=Log2n如果y>m，那么：f(Root)=f(LChild(Root))+f(RChild(Root))此時(shí)[a,b]完全覆蓋LChild(Root)，所以f(LChild(Root))=1；因?yàn)長(zhǎng)(RChild(Root))=m，而[a,b]和RChild(Root)的交集是[m,y]，根據(jù)引理的歸納假設(shè)f(RChild(Root))<=log2(n/2)。也就是說：f(Root)=1+f(RChild(Root))<=1+log2(n/2)=log2n2.如果y=R(Root)和x=L(Root)類似。以上兩點(diǎn)綜合可以證明，當(dāng)[a,b]和Root線段的交集在Root的左邊界或者右邊界重合時(shí)，f(Root)=log2n。(n=R(Root)-L(Root))接下來我們歸納證明對(duì)于一般情況f(Root)<=2log2n。（還是對(duì)n歸納。n=R(Root)-L(Root)）[a,b]和Root線段的交集還是設(shè)為[x,y]。m是Root線段的中點(diǎn)。1.如果[x,y]完全包含于[L(Root)..m]之內(nèi)，則f(RChild(Root))=0，所以：f(Root)=f(LChild(Root))根據(jù)歸納假設(shè)f(LChild(Root))<=2log2n。2.如果[x,y]完全包含于[m..R(Root)]之內(nèi)，則f(LChild(Root))=0。和1類似。3.如果1.,2.都不滿足，那么必然有L(Root)<=x<=m，m<=y<=R(Root)。那么f(LChild(Root))和f(RChild(Root))就都落入了引理的研究范圍，即f(LChild(Root)),f(RChild(Root))都滿足<=log2n/2。所以f(Root)=f(LChild(Root))+f(RChild(Root))<=2log2n/2<=2log2n。綜上所述，總有f(Root)<=2log2n。即f(Root)~O(log2n)。這就是說我們插入或者拿走一根黑布的時(shí)間復(fù)雜度是O(logn)?；氐皆瓉淼念}目。如何輸出有黑色區(qū)間的總長(zhǎng)度？給每個(gè)節(jié)點(diǎn)加入一個(gè)屬性Len，用Len(Root)表示。Len(Root)的意義就是：把以Root為根的子樹中所有的黑布條疊加起來，被染黑區(qū)間的總長(zhǎng)度。如果Count(Root)>0，則Len(Root)=R(Root)-L(Root)。否則Len(Root)=Len(LChild(Root))+Len(RChild(Root))。因?yàn)槊看翁砑?去掉布條只要改動(dòng)樹中至多2log2n個(gè)節(jié)點(diǎn)，所以也只有這2log2n個(gè)節(jié)點(diǎn)的Len值會(huì)出現(xiàn)變動(dòng)，及時(shí)更新即可，時(shí)間復(fù)雜度O(log2n)。每次添加刪除布條后直接輸出Len(Root)即可。新的Add過程如下：procedureAdd(Root,a,b);beginifRoot=NILthenExit;if(a<=L(Root))and(b>=R(Root))then{[a,b]完全包含該線段}Count[Root]Count[Root]+1{因?yàn)镽oot代表的線段被覆蓋了，所以將其標(biāo)記}elseif(b<=L(Root)or(a>=R(Root))then{[a,b]和該線段不相交}Exit{不執(zhí)行任何操作}else{[a,b]和Root代表的線段有交集，但是卻不完全包含}beginAdd(LChild(Root),a,b);Add(RChild(Root),a,b);end;ifCount[Root]>0thenLen[Root]=R(Root)-L(Root)ElseLen[Root]=Len(LChild(Root))+Len(RChild(Root))end;接下來考慮每次操作后要輸出黑色區(qū)間的個(gè)數(shù)。類似的定義Interval(Root)，表示把以Root為根的子樹中的黑布條全部疊加起來，有多少個(gè)黑區(qū)間。如果Count[Root]>0，則顯然Interval(Root)=1。否則Interval(Root)=Interval(LChild(Root))+Interval(RChild(Root))-Connect(Root)這里Connect(Root)是關(guān)于Root的一個(gè)函數(shù)。如果LChild(Root)的右邊界被染黑了、并且RChild(Root)的左邊界被染黑了，那么Connect(Root)=1，否則Connect(Root)=0。為了計(jì)算Connect(Root)我們必須對(duì)每個(gè)節(jié)點(diǎn)X都保存兩個(gè)變量：CoverLeft∈{True,False}代表X的左邊界有沒有被黑色覆蓋。CoverRight∈{True,False}代表X的右邊界有沒有被黑色覆蓋。關(guān)于CoverLeft的計(jì)算：如果Count(Root)>0，則CoverLeft(Root)True；否則CoverLeft(Root)CoverLeft(LChild(Root))。關(guān)于CoverRight的計(jì)算：如果Count(Root)>0，則CoverRight(Root)True；否則CoverRight((Root)CoverRight(RChild(Root))。因?yàn)槊看翁砑?去掉黑布條只會(huì)涉及到2log2n個(gè)節(jié)點(diǎn)的修改，所以即時(shí)更新CoverLeft,CoverRight,Connect和Interval的時(shí)間復(fù)雜度也是O(log2n)。整個(gè)問題解決了。時(shí)間復(fù)雜度被優(yōu)化到了O(nlog2L)。我們從兩個(gè)角度分析了同一個(gè)試題。讀者可以在比較中學(xué)習(xí)兩種算法。第二種算法高效的原因是采用了高級(jí)數(shù)據(jù)結(jié)構(gòu)——線段樹。線段樹的最重要特點(diǎn)就是把有共同點(diǎn)的零散信息整合到一起。比如插入的線段如果是[0,L]，在第一個(gè)算法中就需要把0~L的每一個(gè)數(shù)組元素都訪問一次，而第二個(gè)算法只要對(duì)根節(jié)點(diǎn)的Count值加一即可?！?0.2關(guān)于線段樹一個(gè)更復(fù)雜的應(yīng)用上一節(jié)我們介紹了線段樹的一個(gè)簡(jiǎn)單應(yīng)用。一般來說，線段樹的每個(gè)節(jié)點(diǎn)代表一個(gè)區(qū)間。根節(jié)點(diǎn)代表整條線段，我們從根節(jié)點(diǎn)開始遞歸的把每個(gè)節(jié)點(diǎn)代表的線段分成均等的兩份，作為左右兒子，直到線段被分解成為長(zhǎng)度等于一的單位線段為止，就得到了一棵線段樹（有的書上稱之為區(qū)間樹）。對(duì)于每個(gè)節(jié)點(diǎn)要記錄什么信息要根據(jù)具體題目而定。下面我們來考察一個(gè)更復(fù)雜的例子。(IOI1998的Picture)

PictureAnumberofrectangularposters,photographsandotherpicturesofthesameshapearepastedonawall.Theirsidesareallverticalorhorizontal.Eachrectanglecanbepartiallyortotallycoveredbytheothers.Thelengthoftheboundaryoftheunionofallrectanglesiscalledtheperimeter.TaskWriteaprogramtocalculatetheperimeter.Anexamplewith7rectanglesisshowninFigure1.Figure1.Asetof7rectanglesThecorrespondingboundaryisthewholesetoflinesegmentsdrawninFigure2.Figure2.TheboundaryofthesetofrectanglesTheverticesofallrectangleshaveintegercoordinates.InputDataThefirstlineofthefilePICTURE.INcontainsthenumberofrectanglespastedonthewall.Ineachofthesubsequentlines,onecanfindtheintegercoordinatesofthelowerleftvertexandtheupperrightvertexofeachrectangle.Thevaluesofthosecoordinatesaregivenasorderedpairsconsistingofanx-coordinatefollowedbyay-coordinate.SampleInput:7-150510-58202515-424140-61642151022301036203404016ThiscorrespondstotheexampleofFigure1.OutputDataThefilePICTURE.OUTmustcontainasinglelinewithanon-negativeintegerwhichcorrespondstotheperimeterfortheinputrectangles.SampleOutput:228Thisisthecontentsoftheoutputfilefortheexampleabove.Constraints0numberofrectangles<5000Allcoordinatesareintherange[-10000,10000]andanyexistingrectanglehasapositivearea.Thenumericvalueoftheresultmayneeda32-bitsignedrepresentation.以下是翻譯：圖片墻上貼了一些矩形的張貼畫和照片。他們的邊都是垂直或者水平的。每個(gè)矩形可以部分后者全部被其他的矩形覆蓋。把這些矩形看作一個(gè)整體，他們的邊界長(zhǎng)度就是他們的輪廓長(zhǎng)度。任務(wù)寫一個(gè)程序計(jì)算輪廓長(zhǎng)度。下面的圖1是一個(gè)7個(gè)矩形的例子：圖1：七個(gè)矩形這些矩形的輪廓如下圖2所示：圖2：圖1中7個(gè)矩形的輪廓所有矩形的頂點(diǎn)坐標(biāo)都是整數(shù)。輸入數(shù)據(jù)PICTURE.IN的第一行包含一個(gè)整數(shù)n，代表墻上貼了多少個(gè)矩形。在接下來的第i行描述第i個(gè)矩形，包括四個(gè)整數(shù)，分別表示矩形的左下角X坐標(biāo)、左下角Y坐標(biāo)、右上角X坐標(biāo)和右上角Y坐標(biāo)。樣例輸入7-150510-58202515-424140-61642151022301036203404016該樣例對(duì)應(yīng)于圖1。輸出數(shù)據(jù)PICTURE.OUT包含一個(gè)非負(fù)整數(shù)，輪廓長(zhǎng)度。樣例輸出228限制0n<5000所有的坐標(biāo)都在[-10000,10000]的范圍之內(nèi)，所有的矩形的面積都大于0。結(jié)果可能需要32位帶符號(hào)變量保存。

分析：這是一道國(guó)際競(jìng)賽的試題，從當(dāng)時(shí)的角度來看還是很難的。不難想出O(n2)的算法。因?yàn)閚<5000，所以O(shè)(n2)的時(shí)間復(fù)雜度也能勝任。但是如果n的范圍擴(kuò)大到100000呢？實(shí)際上利用線段樹，我們可以設(shè)計(jì)出一個(gè)時(shí)間復(fù)雜度O(nlogn)的高效算法。比如只有兩個(gè)矩形，如下圖3所示。我們根據(jù)他們的垂直邊界進(jìn)行“離散化”。（也就是劃出很多豎線將整個(gè)圖形分成很多條形區(qū)域）建立一棵空的線段樹。圖3兩個(gè)矩形被“離散”成三個(gè)區(qū)域我們從左到右依次考察每個(gè)離散區(qū)間。如上，考察第一個(gè)離散區(qū)間。藍(lán)色的線段顯然要算入最后的“輪廓長(zhǎng)度”。我們把藍(lán)色線段插入線段樹。在第二個(gè)區(qū)間我們加入了另一個(gè)矩形的左邊界，如上圖藍(lán)色線段。把這條線段加入到線段樹中。但是用圓形圈起來的部分不應(yīng)該算到“輪廓長(zhǎng)度”里面去。究其原因，因?yàn)閳A形圈起來的部分和之前已經(jīng)插入的線段重合了。也就是說每插入一條新線段，只有不和之前已插入線段重合的部分才應(yīng)該被算到“輪廓長(zhǎng)度”里面去。歸納起來：假設(shè)插入該線段前，線段樹中的線段總長(zhǎng)度是X，插入后的總長(zhǎng)度是Y，那么對(duì)于這條線段而言就有長(zhǎng)度為Y-X的部分要算入輪廓中。接著考察第三個(gè)區(qū)間，我們面對(duì)的是一個(gè)矩形的右邊界，如上圖藍(lán)色線段所示。在最開始的時(shí)候我們把綠色的線段插入到了線段樹中，而這里藍(lán)色線段是綠色線段的右邊界、也就是終結(jié)。從此以后，綠色的線段就對(duì)結(jié)果沒有任何影響了。因此我們要把綠色險(xiǎn)段從樹中刪除。(實(shí)際上在線段樹中，藍(lán)色和綠色線段是同一條線段)上圖的藍(lán)色線段中，圓形圈起來的部分不算到輪廓里面去。究其原來，是因?yàn)檫@個(gè)部分和除被刪除線段之外的線段有交集。歸納起來：假設(shè)刪除該線段前，線段樹中的線段總長(zhǎng)度是X，刪除后的總長(zhǎng)度是Y，那么對(duì)于這條線段而言就有長(zhǎng)度為X-Y的部分要算入輪廓中?？疾熳詈笠粋€(gè)區(qū)間，又是一條右邊界，把它從線段樹中刪除即可。因?yàn)樗缓彤?dāng)前線段樹中的任何部分重合，所以整條線段都要算入輪廓長(zhǎng)度。如上掃描了所有區(qū)間后，被算入輪廓的線段如下：也就是說所有垂直的邊我們都考察完畢了。接著只要把圖形旋轉(zhuǎn)90度，用同樣的方法處理一次即可把水平的邊也考察完畢。以上算法可以歸納為：根據(jù)X坐標(biāo)離散。從左到右掃描。碰到左邊界就插線段。碰到右邊界就刪線段。每次插入/刪除操作之前，線段樹中線段覆蓋的總長(zhǎng)度是X；之后的總長(zhǎng)度是Y。那么應(yīng)該算入輪廓的長(zhǎng)度就是|X-Y|。（也就是ResRes+|X-Y|）關(guān)于如何動(dòng)態(tài)維護(hù)線段樹中“線段覆蓋的總長(zhǎng)度”在上一節(jié)中已經(jīng)介紹了。這里不再贅述。整個(gè)算法的時(shí)間復(fù)雜度是O(nlogn)的。實(shí)際上我們并不需要先處理垂直邊，把圖形旋轉(zhuǎn)90度，再處理水平邊?？梢岳谩熬€段樹中有多少個(gè)不相交的區(qū)間”（也就是上一節(jié)例題中要求輸出的第一個(gè)值），來直接計(jì)算水平邊的輪廓長(zhǎng)度。讀者可以自己思考。通過這個(gè)例子讀者可以感覺到，線段樹的難度并不在它本身的操作多么復(fù)雜，而在于如何去應(yīng)用它，也在于在什么情況下我們想到要去應(yīng)用它。一般來說對(duì)于這種查找、統(tǒng)計(jì)類的題目，與區(qū)間、線段掛鉤的，我們都可以考慮線段樹。線段樹的節(jié)點(diǎn)一般包含“線段總覆蓋長(zhǎng)度”和“線段覆蓋的不相交區(qū)間數(shù)”這兩個(gè)屬性。∮10.3樹狀數(shù)組及其應(yīng)用&10.3.1引子線段樹是時(shí)空效率都非常高——時(shí)間復(fù)雜度O(logn)，空間復(fù)雜度O(n)；但是系數(shù)卻很大。比如線段樹的每個(gè)節(jié)點(diǎn)都要存兩個(gè)指針，指向左右孩子，等等。對(duì)于長(zhǎng)度為n的線段，線段樹有2n個(gè)節(jié)點(diǎn)。種種這些都加重了內(nèi)存的負(fù)擔(dān)。如果題目的空間限制很嚴(yán)格，那么使用線段樹就很有可能會(huì)丟分。下面介紹一種特殊的高效數(shù)據(jù)結(jié)構(gòu)：樹狀數(shù)組。這種數(shù)據(jù)結(jié)構(gòu)的時(shí)空復(fù)雜度都和線段樹類似，但是它的系數(shù)要小得多。但是讀者不要對(duì)這種數(shù)據(jù)結(jié)構(gòu)抱有太大的期望，因?yàn)槭芟抻谒慕Y(jié)構(gòu)特殊性，樹狀數(shù)組的應(yīng)用范圍并不廣泛。&10.3.2定義和復(fù)雜度分析引例2假設(shè)有一列數(shù){Ai}(1≤i≤n)，支持如下兩種操作：將Ak的值加D。（k,D是輸入的數(shù)）輸出As+As+1+…+At。（s,t都是輸入的數(shù)，S≤T）分析1——線段樹建立一棵線段樹（線段長(zhǎng)度1~n）。一開始所有節(jié)點(diǎn)的Count值等于0。對(duì)于操作1，如果把Ak的值加D，則把所有覆蓋了Ak的線段的Count值加D。只有l(wèi)og2n條線段會(huì)受到影響，因此時(shí)間復(fù)雜度是O(log2n)。每條線段[X..Y]的Count值實(shí)際上就是Ax+Ax+1+…+Ay的值。對(duì)于操作2，實(shí)際上就是把[S..T]這條線段分解成為線段樹中的節(jié)點(diǎn)線段，然后把所有的節(jié)點(diǎn)線段的Count值相加。類似上一節(jié)介紹的Add過程。時(shí)間復(fù)雜度也是O(log2n)。分析2——樹狀數(shù)組首先定義：l(x)—x的二進(jìn)制最后有多少個(gè)0p(x)—x-2l(x)讀者可能對(duì)l(x),p(x)沒有感性認(rèn)識(shí)。直觀的說l(x)表示x里面含有多少個(gè)2因子，比如4含有兩個(gè)2，8含有三個(gè)2，12含有兩個(gè)2。p(x)表示把x的二進(jìn)制中最后一個(gè)1改成0之后得到的數(shù)。比如12=(1100)2，最后一個(gè)1用紅色標(biāo)出了，所以p(12)=(1000)2=8。又比如44=(101100)2，所以p(44)=(101000)2=40。為了描述方便，我們還定義：S(x)—A1+A2+…+Ax(特別的S(0)=0)S(x..y)—S(y)-S(x-1)(也就是Ax+Ax+1+…+Ay)下面我們定義樹狀數(shù)組：F(x)=S(p(x)+1..x)比如F(12)=S(p(12)+1..12)=S(8+1..12)=S(9..12)=A9+A10+A11+A12。F(x)就稱之為{Ai}數(shù)列的樹狀數(shù)組。操作1：AkAk+D。我們必須對(duì)集合S={x|p(x)<k&&x>k}中的每一個(gè)元素x都執(zhí)行一次F(x)F(x)+D。另外還要對(duì)F(k)也執(zhí)行F(k)F(k)+D。下面考慮每一個(gè)x(x>k)如何滿足p(x)<k這個(gè)條件。設(shè)k=(atat-1…a0)2，x=(btbt-1…b0)2。設(shè)x的二進(jìn)制表示中和k的二進(jìn)制表示中最高的不同位是v，即bv>av(v是滿足此條件的最大值)：必然有bv=1,av=0。如果bv不是x二進(jìn)制表示中最后一個(gè)1，那么p(x)必然是形如(btbt-1..bvXXXX)2的形式(X表示任意數(shù)：0或者1)。因?yàn)?atat-1..av-1)2=(btbt-1..bv-1)2，bv>av，所以p(x)>k。此時(shí)的x不屬于集合S。所以bv必然是x二進(jìn)制表示中的最后一個(gè)1。因?yàn)?atat-1..av-1)2=(btbt-1..bv-1)2，而且p(x)=(btbt-1..bv-100..0)2，必然有p(x)≤k。如果av,av-1,…a0這些數(shù)位全部都是0的話，那么就有p(x)=k，不滿足p(x)<k的條件。所以av,av-1,…,a0里面至少有一個(gè)1。綜上，S集合中的數(shù)x是這樣的數(shù)：設(shè)k=(atat-1…a0)2中的最后一個(gè)1是av。對(duì)于任意一個(gè)i滿足v≤i≤t，ai=0，可以構(gòu)造出x=(atat-1..ai-1100..0)2。直觀地說，也就是把(atat-1…a0)2的最后一個(gè)1之前的某一個(gè)0改成1，并把這個(gè)1后面的數(shù)位全部置為0。用一種巧妙的偽代碼過程表達(dá)如下：Power1xkwhilex<=ndobeginF(x)F(x)+DWhilePowerandx=0doPowerPower*2;xx+Power;end;比如x=36=(100100)2。那么需要被改動(dòng)的F(x)有：x=kx=(0100100)2=36x=0100100x=(0101000)2=40x=0100100x=(0110000)2=48x=0100100x=(1000000)2=64以上紅色的部分表示上文的ai，也就是被改動(dòng)的那個(gè)數(shù)位。很顯然，操作1的時(shí)間復(fù)雜度是O(log2n)的。操作2：計(jì)算S[s..t]。S[s..t]=S[t]-S[s-1]，所以關(guān)鍵在于：給定x，計(jì)算S[x]?？梢赃@樣做：Sum0Whilex>=0dobeginSumSum+F[x];Xp(x);End;此過程正確性顯然。p(x)可以預(yù)處理。所以操作2的時(shí)間復(fù)雜度也是O(log2n)。&10.3.3樹狀數(shù)組的實(shí)戰(zhàn)應(yīng)用下面是一道IOI2001的試題。MobilephonesPROBLEMSupposethatthefourthgenerationmobilephonebasestationsintheTampereareaoperateasfollows.Theareaisdividedintosquares.ThesquaresformanSSmatrixwiththerowsandcolumnsnumberedfrom0toS-1.Eachsquarecontainsabasestation.Thenumberofactivemobilephonesinsideasquarecanchangebecauseaphoneismovedfromasquaretoanotheroraphoneisswitchedonoroff.Attimes,eachbasestationreportsthechangeinthenumberofactivephonestothemainbasestationalongwiththerowandthecolumnofthematrix.Writeaprogram,whichreceivesthesereportsandanswersqueriesaboutthecurrenttotalnumberofactivemobilephonesinanyrectangle-shapedarea.INPUTANDOUTPUTTheinputisreadfromstandardinputasintegersandtheanswerstothequeriesarewrittentostandardoutputasintegers.Theinputisencodedasfollows.Eachinputcomesonaseparateline,andconsistsofoneinstructionintegerandanumberofparameterintegersaccordingtothefollowingtable.InstructionParametersMeaning0SInitializethematrixsizetoSScontainingallzeros.Thisinstructionisgivenonlyonceanditwillbethefirstinstruction.1XYAAddAtothenumberofactivephonesintablesquare(X,Y).Amaybepositiveornegative.2LBRTQuerythecurrentsumofnumbersofactivemobilephonesinsquares(X,Y),whereLXR,BYT3Terminateprogram.Thisinstructionisgivenonlyonceanditwillbethelastinstruction.Thevalueswillalwaysbeinrange,sothereisnoneedtocheckthem.Inparticular,ifAisnegative,itcanbeassumedthatitwillnotreducethesquarevaluebelowzero.Theindexingstartsat0,e.g.foratableofsize44,wehave0X3and0Y3.Yourprogramshouldnotansweranythingtolineswithaninstructionotherthan2.Iftheinstructionis2,thenyourprogramisexpectedtoanswerthequerybywritingtheanswerasasinglelinecontainingasingleintegertostandardoutput.PROGRAMMINGINSTRUCTIONSIntheexamplesbelow,theintegerlastisthelastonetobereadfromaline,andansweristheintegervariablecontainingyouranswer.IfyouprograminC++anduseiostreams,youshouldusethefollowingimplementationforreadingstandardinputandwritingtostandardoutput: cin>>last;cout<<answer<<endl<<flush;IfyouprograminCorC++andusescanfandprintf,youshouldusethefollowingimplementationforreadingstandardinputandwritingtostandardoutput:scanf("%d",&last); printf("%d\n",answer);fflush(stdout);IfyouprograminPascal,youshouldusethefollowingimplementationofreadingstandardinputandwritingtostandardoutput: Read(last);...Readln;Writeln(answer);EXAMPLEstdin stdout explanation04 Initializetablesizeto44.1123 Updatetableat(1,2)with+3.20022 Querysumofrectangle0X2,0Y2. 3 Answerthequery.1112 Updatetableat(1,1)with+2.112-1 Updatetableat(1,2)with-1.21123 Querysumofrectangle1X2,1Y3. 4 Answerthequery.3 Terminateprogram.CONSTRAINTSTablesizeSS11SS10241024CellvalueVatanytimeV0V215–1(=32767)UpdateamountA-215A215–1(=32767)NoofinstructionsininputU3U60002MaximumnumberofphonesinthewholetableMM=230Outofthe20inputs,16aresuchthatthetablesizeisatmost512512.NOTE:Thewebtestfacilityfeedsyourinputfiletoyourprogram’sstandardinput.下面是翻譯：移動(dòng)電話問題描述假設(shè)第四代移動(dòng)電話的收發(fā)站是這樣運(yùn)行。整個(gè)區(qū)域被分割成很小的方格。所有的方格組成了一個(gè)S*S的矩陣，行和列從0~S-1編號(hào)。每個(gè)小方格都包含一個(gè)收發(fā)站。每個(gè)方格內(nèi)的開機(jī)的移動(dòng)電話數(shù)量可以不斷改變，因?yàn)槭謾C(jī)用戶在各個(gè)方格之間移動(dòng)，也有用戶開機(jī)或者關(guān)機(jī)。一旦某個(gè)方格里面開機(jī)的移動(dòng)電話數(shù)量發(fā)生了變化，該方格里的收發(fā)站就會(huì)向總部發(fā)送一條信息說明這個(gè)改變量?？偛恳銓懸粋€(gè)程序，用來管理從各個(gè)收發(fā)站收到的信息。老板可能隨時(shí)會(huì)問：某一個(gè)給定矩形區(qū)域內(nèi)有多少部開機(jī)的移動(dòng)電話??？你的程序必須要能隨時(shí)回答老板的問題。輸入輸出數(shù)據(jù)要求從標(biāo)準(zhǔn)輸入讀入整數(shù)，向標(biāo)準(zhǔn)輸出寫入你對(duì)老板問題的回答。輸入數(shù)據(jù)的格式如下：每個(gè)輸入獨(dú)立成一行。一個(gè)輸入包括一個(gè)指示數(shù)和一些參數(shù)，見下表：指示數(shù)參數(shù)意義0S初始指令。整個(gè)區(qū)域由S*S個(gè)小格子組成。這個(gè)指令只會(huì)在一開始出現(xiàn)一次。1XYA方格(X,Y)內(nèi)的開機(jī)移動(dòng)電話量增加了A。A可能是正數(shù)也可能是負(fù)數(shù)。2LBRT詢問在矩形區(qū)域(L,B)—(R,T)內(nèi)有多少部開機(jī)的移動(dòng)電話。矩形區(qū)域(L,B)—(R,T)包括所有的格子(X,Y)滿足LXR,BYT。3終止程序。這個(gè)指示只會(huì)在最后出現(xiàn)一次。所有的數(shù)據(jù)總是在給定的范圍內(nèi)，你不需要查錯(cuò)。特別的，如果A是負(fù)數(shù)，你可以認(rèn)為該操作不會(huì)讓該格子的開機(jī)移動(dòng)電話數(shù)變成負(fù)數(shù)。格子是從0開始編號(hào)的，比如一個(gè)4*4的區(qū)域，所有的格子(X,Y)應(yīng)該表示為0X3,0Y3。對(duì)于除了2之外的指示，你的程序不應(yīng)該輸出任何東西。如果指示是2，那么你的程序應(yīng)該向標(biāo)準(zhǔn)輸出寫入一個(gè)整數(shù)。編程指示在下面的例子中，整數(shù)Last是你從一行中讀入的最后一個(gè)數(shù)；整數(shù)answer是你的答案。如果你使用C++語言，而且使用iostreams，你應(yīng)該用下面的實(shí)現(xiàn)方法來訪問標(biāo)準(zhǔn)輸入/舒出：cin>>last;cout<<answer<<endl<<flush;如果你使用C或者C++語言，而且使用scanf和printf，你應(yīng)該用下面的實(shí)現(xiàn)方法來訪問標(biāo)準(zhǔn)輸入/輸出：scanf("%d",&last); printf("%d\n",answer);fflush(stdout);如果你使用Pascal語言，你應(yīng)該用下面的實(shí)現(xiàn)方法來訪問標(biāo)準(zhǔn)輸入/輸出：Read(last);...Readln;Writeln(answer);例子標(biāo)準(zhǔn)輸入 標(biāo)準(zhǔn)輸出 解釋04 初始化44的區(qū)域.1123 格子(1,2)加3。20022 詢問矩形0X2,0Y2里面的開機(jī)移動(dòng)電話總量。 3 回答詢問。1112 格子(1,1)加2。112-1 格子(1,2)減1。21123 詢問矩形1X2,1Y3里面的開機(jī)移動(dòng)電話總