樹狀數(shù)組詳解NOICSP

樹狀數(shù)組詳解NOI_CSP_ACMICPC樹狀數(shù)組的應(yīng)用背景區(qū)間查詢問題是信息學(xué)競賽中高級(jí)別比賽的一個(gè)重要類型題。往往在一個(gè)10^6大小的區(qū)間內(nèi)，進(jìn)行10^4的操作（在線或離線）。這種情況下，我們很難將10^4次操作進(jìn)行壓縮，唯一可以考慮的壓縮對(duì)象就是10^6的區(qū)間?？紤]在對(duì)數(shù)時(shí)間復(fù)雜度內(nèi)處理這個(gè)區(qū)間的問題，一般有兩個(gè)角度：倍增或樹結(jié)構(gòu)。而樹狀數(shù)組就是倍增法在區(qū)間查詢問題的體現(xiàn)，線段樹是樹結(jié)構(gòu)在這個(gè)問題上的應(yīng)用。樹狀數(shù)組樹狀數(shù)組又稱二叉索引樹（BinaryIndexedTree）多用于高效計(jì)算數(shù)列的前綴和、區(qū)間和等RMQ問題。我們知道所有的整數(shù)都可以表示成2的冪和，例如19可以表示為16+2+1，即2^4+2^1+2^0。這樣一串序列可以表示成一系列子序列的和。這樣，便可將一個(gè)前綴和劃分成多個(gè)子序列的和，而劃分的方法與數(shù)的2的冪和極其相似。樹狀數(shù)組呈如下樣子：數(shù)組第一個(gè)元素的值為數(shù)列第一個(gè)元素的值；第二個(gè)元素的值為數(shù)列前兩個(gè)元素值的和；第三個(gè)元素值為數(shù)列第三個(gè)元素的值；第四個(gè)元素值為數(shù)列前四個(gè)元素的值......，以此類推。C[1]=A[1]C[2]=A[1]+A[2]C[3]=A[3]C[4]=A[1]+A[2]+A[3]+A[4]=C[2]+C[3]+A[4]這樣如果我們知道整個(gè)數(shù)列前7個(gè)元素的累加和，只需要累加樹狀數(shù)組中第四，第六，第七個(gè)元素即可。基于此，利用前綴和/差分技術(shù)（詳見文章《信息學(xué)競賽中的差分技巧》）就可以求得某一個(gè)區(qū)間內(nèi)的值的累加和，即區(qū)間和。上面已經(jīng)解釋了如何用樹狀數(shù)組求區(qū)間和。那么如果要更新某一個(gè)點(diǎn)的值呢？已知C[i]=C[i+2^k]+C[i+2^k+2^k]+...+A[i]，那么更新某A[i]的值，則會(huì)影響到所有包含有A[i]位置，如C[i+2^k]、C[(i+2^k)+2^k]...。那么構(gòu)造一個(gè)樹狀數(shù)組的代碼則為：Lowbit()技術(shù)這里需要介紹一下lowbit()技術(shù)。Lowbit()技術(shù)實(shí)在涉及到二進(jìn)制位運(yùn)算中普遍涉及的一種結(jié)束。在樹狀數(shù)組、狀態(tài)壓縮動(dòng)態(tài)規(guī)劃、數(shù)位哈希等問題都有應(yīng)用。Lowbit()技術(shù)利用了負(fù)數(shù)的存儲(chǔ)特性：負(fù)數(shù)以補(bǔ)碼存儲(chǔ)。對(duì)于整數(shù)運(yùn)算x&(-x)有：當(dāng)x為0時(shí)，即0&0，結(jié)果為0；當(dāng)x為奇數(shù)時(shí)，最后一個(gè)比特位為1，取反加1沒有進(jìn)位，故x和-x除最后一位外前面的位正好相反，按位與結(jié)果為0。結(jié)果為1。當(dāng)x為偶數(shù)，且為2的m次方時(shí)，x的二進(jìn)制表示中只有一位是1即從右往左的第m+1位。其右邊有m位0，故x取反加1后，從右到左第有m個(gè)0，第m+1位及其左邊全是1。這樣x&(-x)得到的就是x。 當(dāng)x為偶數(shù)，卻不為2的m次方的形式時(shí)，可以寫作x=y*(2^k)。其中，y的最低位為1。實(shí)際上就是把x用一個(gè)奇數(shù)左移k位來表示。這時(shí)，x的二進(jìn)制表示最右邊有k個(gè)0，從右往左第k+1位為1。當(dāng)對(duì)x取反時(shí)，最右邊的k位0變成1，第k+1位變?yōu)?；再加1，最右邊的k位就又變成了0，第k+1位因?yàn)檫M(jìn)位的關(guān)系變成了1。左邊的位因?yàn)闆]有進(jìn)位，正好和x原來對(duì)應(yīng)的位上的值相反。二者按位與，得到：第k+1位上為1，左邊右邊都為0。結(jié)果為2^k。簡言之，x&(-x)當(dāng)x為0時(shí)結(jié)果為0；x為奇數(shù)時(shí)，結(jié)果為1；x為偶數(shù)時(shí)，結(jié)果為x中2的最大次方的因子。lowbit()即取2^k。例題：單點(diǎn)修改+區(qū)間查詢C國的死對(duì)頭A國這段時(shí)間正在進(jìn)行軍事演習(xí)，所以C國間諜頭子Derek和他手下Tidy又開始忙乎了。A國在海岸線沿直線布置了N個(gè)工兵營地,Derek和Tidy的任務(wù)就是要監(jiān)視這些工兵營地的活動(dòng)情況。由于采取了某種先進(jìn)的監(jiān)測(cè)手段，所以每個(gè)工兵營地的人數(shù)C國都掌握的一清二楚,每個(gè)工兵營地的人數(shù)都有可能發(fā)生變動(dòng)，可能增加或減少若干人手,但這些都逃不過C國的監(jiān)視。中央情報(bào)局要研究敵人究竟演習(xí)什么戰(zhàn)術(shù),所以Tidy要隨時(shí)向Derek匯報(bào)某一段連續(xù)的工兵營地一共有多少人。例如Derek問:“Tidy,馬上匯報(bào)第3個(gè)營地到第10個(gè)營地共有多少人!”Tidy就要馬上開始計(jì)算這一段的總?cè)藬?shù)并匯報(bào)。但敵兵營地的人數(shù)經(jīng)常變動(dòng)，而Derek每次詢問的段都不一樣，所以Tidy不得不每次都一個(gè)一個(gè)營地的去數(shù)，很快就精疲力盡了。Derek對(duì)Tidy的計(jì)算速度越來越不滿。Tidy很苦惱，這么算他真的會(huì)崩潰的，聰明的讀者，你能寫個(gè)程序幫他完成這項(xiàng)工作嗎？輸入第一行一個(gè)整數(shù)T，表示有T組數(shù)據(jù)。每組數(shù)據(jù)第一行一個(gè)正整數(shù)N（N<=50000）,表示敵人有N個(gè)工兵營地，接下來有N個(gè)正整數(shù),第i個(gè)正整數(shù)ai代表第i個(gè)工兵營地里開始時(shí)有ai個(gè)人（1<=ai<=50）。接下來每行有一條命令，命令有4種形式：(1)Addij,i和j為正整數(shù),表示第i個(gè)營地增加j個(gè)人（j不超過30）(2)Subij,i和j為正整數(shù),表示第i個(gè)營地減少j個(gè)人（j不超過30）;(3)Queryij,i和j為正整數(shù),i<=j，表示詢問第i到第j個(gè)營地的總?cè)藬?shù);(4)End表示結(jié)束，這條命令在每組數(shù)據(jù)最后出現(xiàn);每組數(shù)據(jù)最多有40000條命令。對(duì)第i組數(shù)據(jù),首先輸出“Casei:”和回車,對(duì)于每個(gè)Query詢問，輸出一個(gè)整數(shù)并回車,表示詢問的段中的總?cè)藬?shù),這個(gè)數(shù)保持在int以內(nèi)。此題是一道單點(diǎn)修改，區(qū)間查詢的模板題。觀察數(shù)據(jù)量可以看出此題為多樣例題目，而且每組有4*10^4個(gè)命令，每個(gè)命令涉及的區(qū)間有5*10^4個(gè)數(shù)據(jù)。這樣的數(shù)據(jù)量采用普通的數(shù)據(jù)結(jié)構(gòu)是無法在有效的時(shí)間復(fù)雜度內(nèi)勝任的。所以可以考慮樹狀數(shù)組，當(dāng)然考慮線段樹也是可行的。這個(gè)問題在其他相關(guān)文章中會(huì)進(jìn)行討論。題目中的調(diào)增，即加法運(yùn)算可以用加法運(yùn)算；調(diào)減，即減法運(yùn)算可以累加一個(gè)負(fù)值。通過lowbit()技術(shù)找出在某個(gè)單點(diǎn)調(diào)增/調(diào)減所涉及到的所有的點(diǎn)，然后逐一進(jìn)行增減。即完成單點(diǎn)修改。在區(qū)間查詢，如查詢[l,r]區(qū)間的區(qū)間和時(shí)，可以考慮使用前綴和技巧，用sum[r]-sum[l-1]，在O(1)的時(shí)間復(fù)雜度內(nèi)解決前綴和問題。當(dāng)然前綴和的查詢也需要使用lowbit(）技術(shù)查出樹狀數(shù)組所影響到的所有點(diǎn)，然后進(jìn)行累加。篇幅所限，題目樣例及代碼請(qǐng)發(fā)消息討論。謝謝。例題：區(qū)間修改+單點(diǎn)查詢：N個(gè)氣球排成一排，從左到右依次編號(hào)為1,2,3....N。每次給定2個(gè)整數(shù)a，b(a<=b),lele便為騎上他的“小飛鴿"牌電動(dòng)車從氣球a開始到氣球b依次給每個(gè)氣球涂一次顏色。但是N次以后lele已經(jīng)忘記了第i個(gè)氣球已經(jīng)涂過幾次顏色了，你能幫他算出每個(gè)氣球被涂過幾次顏色嗎？每個(gè)測(cè)試實(shí)例第一行為一個(gè)整數(shù)N,(N<=100000)。接下來的N行，每行包括2個(gè)整數(shù)a，b(1<=a<=b<=N)。當(dāng)N=0，輸入結(jié)束。每個(gè)測(cè)試實(shí)例輸出一行，包括N個(gè)整數(shù)，第i個(gè)數(shù)代表第i個(gè)氣球總共被涂色的次數(shù)。此題為區(qū)間修改（一部分氣球染色）及單點(diǎn)查詢（染色次數(shù)）的模板題目?？梢远x數(shù)組a[]為氣球被染色的次數(shù)。如果暴力處理N次區(qū)間修改時(shí)間復(fù)雜度為O(n^2)，這個(gè)時(shí)間復(fù)雜度時(shí)不可接受的。而采用樹狀數(shù)組，將區(qū)間[L,R]內(nèi)的數(shù)a[x]逐一進(jìn)行單點(diǎn)修改，時(shí)間復(fù)雜度會(huì)更差，為O(n^2*logn)。這種情況可以考慮用差分?jǐn)?shù)組處理區(qū)間修改問題。（詳見文章《信息學(xué)競賽中的差分技巧》）。差分?jǐn)?shù)組定義為D[k]=a[k]-a[k-1]，即原數(shù)組相鄰元素的差。從定義可得，a[k]為差分?jǐn)?shù)組D[k]的前綴和，即a[k]=D1+D2+...+D[k]。將求a[k]轉(zhuǎn)化為求D[k]的前綴和，利用樹狀數(shù)組來處理。對(duì)于區(qū)間[L,R]的修改問題，作操作將D[L]加上d;將D[R+1]減去d。用樹狀數(shù)組sum()函數(shù)求前綴和sum[x]=D[1]+D[2]+...+D[x]。則有：1<=x<L，前綴和sum[x]不變；L<=x<=R,前綴和sum[x]增加了d；R<x<=n,前綴和sum[x]不變，被D[R+1]中減去的d抵消了。sum[x]就是a[x]，這樣得到單點(diǎn)查詢的結(jié)果。利用差分，可以將區(qū)間問題轉(zhuǎn)換為單點(diǎn)問題。如果區(qū)間內(nèi)每個(gè)元素都修改，復(fù)雜度為O(n)；用差分轉(zhuǎn)換為只記錄兩個(gè)端點(diǎn)后，時(shí)間復(fù)雜度將為O(1)。篇幅所限，題目樣例及代碼請(qǐng)發(fā)消息討論。謝謝。區(qū)間修改+區(qū)間查詢當(dāng)查詢不再是一個(gè)單點(diǎn)的值，而是一個(gè)區(qū)間[l,r]的和，僅用一個(gè)樹狀數(shù)組是無法高效完成區(qū)間修改和區(qū)間查詢的。因?yàn)闃錉顢?shù)組tree[]已經(jīng)用于區(qū)間修改了，它的sum()函數(shù)計(jì)算了單點(diǎn)的值，不能再用于求[l,r]的區(qū)間和。如果采用另一個(gè)樹狀數(shù)組做區(qū)間查詢，效率也不高。因?yàn)樽鲆淮伍L度為k的區(qū)間修改，計(jì)算區(qū)內(nèi)每一個(gè)單點(diǎn)的時(shí)間復(fù)雜度為O(logN)。如果繼續(xù)用另一個(gè)樹狀數(shù)組處理這k個(gè)單點(diǎn)，復(fù)雜度為O(k*logN)。做n次修改查詢時(shí)間復(fù)雜度為O(n^2*logN)。這個(gè)時(shí)間復(fù)雜度是難以被接受的。一般情況下，區(qū)間修改+區(qū)間查詢?cè)诟傎悓?shí)踐中會(huì)采用線段樹+lazyTag技術(shù)解決。當(dāng)然如果一定要要用樹狀數(shù)組解決區(qū)間修改+區(qū)間查詢問題，需要用差分?jǐn)?shù)組與樹狀數(shù)組相結(jié)合的二階數(shù)狀數(shù)組完成。例題：樹狀數(shù)組區(qū)間修改+區(qū)間查詢已知一個(gè)數(shù)列，你需要進(jìn)行下面兩種操作：將某區(qū)間每一個(gè)數(shù)加上k。求出某區(qū)間每一個(gè)數(shù)的和。輸入第一行包含兩個(gè)整數(shù)n,m，分別表示該數(shù)列數(shù)字的個(gè)數(shù)和操作的總個(gè)數(shù)。第二行包含n個(gè)用空格分隔的整數(shù)，其中第i個(gè)數(shù)字表示數(shù)列第i項(xiàng)的初始值。接下來m行每行包含3或4個(gè)整數(shù)，表示一個(gè)操作，具體如下：1xyk：將區(qū)間[x,y]內(nèi)每個(gè)數(shù)加上k。2xy：輸出區(qū)間[x,y]內(nèi)每個(gè)數(shù)的和。輸出包含若干行整數(shù)，即為所有操作2的結(jié)果。本題求區(qū)間和，即sum(L,R)=a[L]+a[L+1]+...+a[R]=sum(1,R)-sum(1,L-1)。故，區(qū)間和問題轉(zhuǎn)換為求sum(1,k)的問題。定義一個(gè)差分?jǐn)?shù)組D[]。它和原數(shù)組a[]的關(guān)系仍然是D[k]=a[k]-a[k-1]。有a[k]=D[1]+D[2]+...+D[k]。推導(dǎo)區(qū)間和：若區(qū)間和與前綴和有關(guān)，可用樹狀數(shù)組求解。a1+a2+...+ak=D1+(D1+D2)+...+(D1+D2+...+Dk)=k*D1+(k-1)*D2+(k-2)*D3+...+(k-(k-1))*Dk=k*(D1+D2+...+Dk)-(D2+2*D3+...+(k-1)*Dk)公式的最后一行求兩個(gè)前綴和，用兩個(gè)樹狀數(shù)組分別處理，一個(gè)實(shí)現(xiàn)Di，一個(gè)實(shí)現(xiàn)(i-1)*Di。代碼時(shí)間復(fù)雜度為O(m*logN)。時(shí)間復(fù)雜度可以被接受。篇幅所限，題目樣例及代碼請(qǐng)發(fā)消息討論。謝謝。例題：二維區(qū)間修改+區(qū)間查詢第一分鐘，X說，要有矩陣，于是便有了一個(gè)里面寫滿了0的n*m矩陣。第二分鐘，L說，要能修改，于是便有了將左上角為(a,b)，右下角為(c,d)的一個(gè)矩形區(qū)域內(nèi)的全部數(shù)字加上一個(gè)值的操作。第三分鐘，k說，要能查詢，于是便有了求給定矩形區(qū)域內(nèi)的全部數(shù)字和的操作。第四分鐘，彩虹喵說，要基于二叉樹的數(shù)據(jù)結(jié)構(gòu)，于是便有了數(shù)據(jù)范圍。第五分鐘，和雪說，要有耐心，于是便有了時(shí)間限制。第六分鐘，吃鋼琴男說，要省點(diǎn)事，于是便有了保證運(yùn)算過程中及最終結(jié)果均不超過32位有符號(hào)整數(shù)類型的表示范圍的限制。第七分鐘，這道題終于造完了，然而，造題的神牛們?cè)僖膊幌雽戇@道題的程序了?！渡系墼炻泐}的七分鐘》。所以這個(gè)神圣的任務(wù)就交給你了。輸入數(shù)據(jù)的第一行為X，n，m，代表矩陣大小為n*m。從輸入數(shù)據(jù)的第二行開始到文件尾的每一行會(huì)出現(xiàn)以下兩種操作：Labcddelta——代表將(a,b),(c,d)為頂點(diǎn)的矩形區(qū)域內(nèi)的所有數(shù)字加上delta。kabcd——代表求(a,b),(c,d)為頂點(diǎn)的矩形區(qū)域內(nèi)所有數(shù)字的和。請(qǐng)注意，k為小寫。針對(duì)每個(gè)k操作，輸出一行答案。此題明顯為二維區(qū)間問題。解決二維區(qū)間問題，需要用二維差分?jǐn)?shù)組。定義二維差分?jǐn)?shù)組D[][]，它與矩陣元素a[][]的關(guān)系：D[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]。a[c][d]可以看作是(1,1)(c,d)為頂點(diǎn)的矩陣內(nèi)的D[i][j