樹狀數(shù)組及其應用雙語版

樹狀數(shù)組及其應用BinaryIndexedTree

引例【題目描述】輸入一個數(shù)列A1,A2….An(1<=N<=100000)，在數(shù)列上進行M(1<=M<=100000)次操作，操作有以下兩種：格式為CIX，其中C為字符“C”，I和X(1<=I<=N,|X|<=10000)都是整數(shù)，表示把把a[I]改為X格式為QLR，其中Q為字符“Q”，L和R表示詢問區(qū)間為[L,R](1<=L<=R<=N)，表示詢問A[L]+…+A[R]的值?！据斎搿康谝恍休斎隢(1<=N<=100000)，表述數(shù)列的長度，接下來N行，每行一個整數(shù)(絕對值不超過10000)依次輸入每個數(shù)；接下來輸入一個整數(shù)M(1<=M<=100000)，表示操作數(shù)量，接下來M行，每行為CIX或者QLR?！据敵觥繉τ诿總€QLR的操作輸出答案。如果直接用數(shù)組模擬，那么修改是O(1),查詢是O(n),如果維護另一個數(shù)組b[i]，表示a[1]到a[i]的和，那么修改是O(n),查詢時O(1)。一個程序的時間復雜度取決于其中最大的時間復雜度。樹狀數(shù)組的目的就是平攤修改和查詢的時間，使復雜度由O(n)降到O(lgn)。樹狀數(shù)組是一種數(shù)據(jù)結(jié)構(gòu)，這種結(jié)構(gòu)能讓我們的程序變得高效，數(shù)據(jù)結(jié)構(gòu)大多數(shù)時候是為了優(yōu)化算法而用的。樹狀數(shù)組對于原數(shù)組a維護另一個數(shù)組c，c[i]表示sum(a[j]),i-lowbit(i)+1<=j<=i,其中l(wèi)owbit(i)表示取出i二進制表示中最右邊的1。例如lowbit(6)=lowbit(110)2=(10)2=2所以c[6]=a[5]+a[6];lowbit(4)=lowbit(100)2=(100)2=4

c[4]=a[1]+a[2]+a[3]+a[4]lowbit[5]=lowbit(101)2=(1)2=1;c[5]=a[5]其比較簡單的算法為

lowbit(i)=i&(-i)

或i&(i^(i-1))lowbit(i)=iand(-i)

或iand(ixor(i-1))結(jié)論1、節(jié)點i的父親節(jié)點為i+lowbit(i)2、節(jié)點i的最近不相交前驅(qū)為i-lowbit(i)3、若需改變a[i]，則c[i]、c[i+lowbit(i)]、c[i+lowbit(i)+lowbit(i+lowbit(i)]……一直加到上限，就是需要改變的c數(shù)組中的元素。

4、若需查詢s[i]，則c[i]、c[i-lowbit(i)]、c[i-lowbit(i)-lowbit(i-lowbit(i))]……就是需要累加的c數(shù)組中的元素。

5、以上的修改和查詢都是log2(n)級別的。Procedureadd(k,delt);Beginwhilek<=limitdobegin

C[k]:=C[k]+delta;k:=k+lowbit(k);End;End;由此我們可以得出修改與查詢操作voidadd(k,delt){

while(k<=limit){

c[k]+=delt;k+=lowbit(k);}}Functiongetsum(k:integer):integer;Var

t:integer;Begint:=0;whilek>0dobegint:=t+c[k];k:=k-lowbit(k);end;

getsum:=t;End;當要查詢a[i..j]累加和時，可以先求出a[1..j],a[1..i-1]，然后相減int

getsum(intk){

intt=0;while(k>0){t+=c[k];k-=lowbit[k];}returnt;}在實際應用中，通常不需要保存原數(shù)組a，只保存數(shù)組c即可。因此，樹狀數(shù)組幾乎不需要附加空間。通過上面的學習可以看出：樹狀數(shù)組所能支持的操作是修改點值、查詢區(qū)間和。與線段樹和其他數(shù)據(jù)結(jié)構(gòu)相比，樹狀數(shù)組代碼簡單，常數(shù)小，在其能解決范圍內(nèi)或經(jīng)過轉(zhuǎn)化使用樹狀數(shù)組，可以極大的降低編程復雜度，使代碼清晰，簡潔優(yōu)秀的數(shù)據(jù)結(jié)構(gòu)！例題、Stars(ural1028)題目大意平面中有N個點，對于每個點(x,y)，要求輸出在其左下方（包括正左正下）點的個數(shù)。N<=100000;x,y<=maxlongint枚舉？代碼簡單，時間復雜度達到O(n2)有沒有代碼簡單、時間復雜度低的方法？此題有效的算法很多，樹狀數(shù)組可以簡潔快速的解決此問題。如何構(gòu)建樹狀數(shù)組？如何處理巨大的(x,y)？如何處理“左下方”？首先，離散化y坐標，然后按x坐標從小到大排序，x相同則y坐標由小到大，從左到右掃描每個點，這樣可以保證已經(jīng)插入樹狀數(shù)組的點都在左側(cè)或正下側(cè)。我們只需尋找有多少點位于當前點下方，很容易想到樹狀數(shù)組。處理完當前點后，將其按y坐標插入樹狀數(shù)組，即讓a[y]加1此題是樹狀數(shù)組的經(jīng)典應用首先離散化坐標使數(shù)據(jù)范圍減小，為使用樹狀數(shù)組創(chuàng)造了條件按橫坐標排序，使得原題中“左下方”兩個條件限制轉(zhuǎn)化為“下方”這一單一限制可以輕松運用樹狀數(shù)組解決現(xiàn)在，我們將樹狀數(shù)組推廣到二維

先看一道神奇的題目2、Superbrother打鼴鼠(vijos1512)題目大意給定一個n*n的正方形區(qū)域，左上角為(0,0),右下角為(n-1,n-1)，初始所有整點權(quán)值為0。任意時刻有兩種操作：1、在一個整點處權(quán)值加K2、詢問一個矩形內(nèi)整點權(quán)值和N<=1024這道題目是神牛Superbrother原創(chuàng)，很難！此題可以用二維線段樹或二維樹狀數(shù)組解決。二維樹狀數(shù)組的代碼與一維及其相似。Functiongetsum(x,y):integer;(求出矩陣(1,1)~(x,y)點值和)Var

z,t:longint;Begint:=0;whilex>0dobeginz:=y;whilez>0dobegint:=t+c[x,z];z:=z-lowbit(z);end;x:=x-lowbit(x);end;

getsum:=t;End;

對于詢問(x1,y1)-(x2,y2)，

ans=getsum(x2,y2)-getsum(x2,y1-1)-getsum(x1-1,y2)+getsum(x1-1,x2-1);注意!樹狀數(shù)組下標必須從1開始Superbrother神牛到此，我們已經(jīng)學習完樹狀數(shù)組的基本內(nèi)容。樹狀數(shù)組的應用非常廣泛，變形極多，靈活性強，很多題目經(jīng)過一系列轉(zhuǎn)化后可以使用樹狀數(shù)組解決。下面，我將通過其他幾個例題介紹如何通過有效的轉(zhuǎn)化使用樹狀數(shù)組解題。3、Cows(pku2481)題目大意有n頭牛，每頭牛喜歡吃[s[i],e[i]]這個區(qū)間的草。如果對于i、j兩頭牛，s[i]<=s[j]且e[j]<=s[i]且等號最多成立一個，那么i比j強。輸出每頭牛比多少頭牛強。N,s,e<=10^5樣例輸入樣例輸出

3100120334此題條件簡單，但并不直觀將區(qū)間坐標化，我們發(fā)現(xiàn)，對于每頭牛，要求的就是其左上方的牛的個數(shù)。同stars，注意判斷點重合的情況4、逆序?qū)︻}目大意給定一個序列a[1]..a[n]，對于任意i,j,如果i<j并且a[i]>a[j]，我們說這是一個逆序?qū)?。你的任務是輸出逆序?qū)Φ膫€數(shù)N<=100000a[i]<=maxlongint此題直接枚舉同樣需要n2的時間此題同樣解法較多，可以使用分治法類似歸并排序，也可以使用樹狀數(shù)組。此題和stars同樣有兩個限制:“i<j并且a[i]>a[j]”應用同一思路，順序掃描，將其轉(zhuǎn)化為一個限制——a[i]>a[j]。首先對a數(shù)組離散化按順序掃描，只需找到有多少比a[i]大的數(shù)已經(jīng)出現(xiàn)過。這可以用樹狀數(shù)組維護。初始時，數(shù)組全為0。每次掃描到a[i]，用樹狀數(shù)組求出a[i]+1～max中出現(xiàn)過多少個數(shù)，然后將a[i]插入樹狀數(shù)組。例如n=5,輸入1006723首先離散化，輸入變?yōu)?3412順序掃描i12345100000例如n=5,輸入1006723首先離散化，輸入變?yōu)?3412順序掃描i12345200001例如n=5,輸入1006723首先離散化，輸入變?yōu)?3412順序掃描i12345300101例如n=5,輸入1006723首先離散化，輸入變?yōu)?3412順序掃描i12345400111例如n=5,輸入1006723首先離散化，輸入變?yōu)?3412順序掃描i12345510111小結(jié)以上幾道例題比較簡單，屬于樹狀數(shù)組的基礎用法，主要起到數(shù)據(jù)結(jié)構(gòu)的作用，用來對數(shù)據(jù)進行快速的存儲和處理。樹狀數(shù)組與其他數(shù)據(jù)結(jié)構(gòu)相比，最大的特點就是代碼簡單，常數(shù)小，從而得到廣泛的應用。樹狀數(shù)組的基本操作就是兩個，修改某個元素的值，求區(qū)間累加和。括號括號表示法是運用樹狀數(shù)組解題的重要方法之一。應用括號表示，可以將一部分修改區(qū)間、查詢點值的題目轉(zhuǎn)化為修改點值、查詢區(qū)間，從而可以使用樹狀數(shù)組。5、Superbrother種樹實驗中學東校坐落在濟南市郭店鎮(zhèn)。為了迎全運，樹新風，需要在一條長為n的道路上種若干種樹。道路表示為[0,n]，共n+1個點。由于經(jīng)費緊張，教導處將這個重任交給了信息組頭號神牛Superbrother，希望他合理分配樹木，使道路更加漂亮。Superbrother經(jīng)過研究，制定了一套詳細的計劃。計劃可以描述為若干個操作，每個操作在[l,r]中所有點種一棵顏色特殊的樹。教導處隨時都會檢查，方式為給定一個點，要求他回答這個點一共種過多少種不同的樹。輸入第一行為n,m

以下m行，可能是一次種樹，也可能是一次詢問。此題與前面幾題不同，要求修改一段區(qū)間的值，詢問一個點的值。使用線段樹可以輕松處理。有沒有更簡單、快速的方法？利用括號，轉(zhuǎn)化為樹狀數(shù)組＜＞要將修改區(qū)間操作轉(zhuǎn)化為修改點的操作，只有在區(qū)間端點做文章。每次修改區(qū)間，便在區(qū)間兩端加括號。這樣，每次詢問時只需要輸出從0～這個點中左括號數(shù)-右括號數(shù)。＜＞＜＜＜＞＞＞具體的，對于每個修改操作[l,r]，將樹狀數(shù)組中c[l]+1,c[r+1]-1。對于詢問操作t，輸出getsum(t)。時間復雜度O(mlgn)＜＞＜＜＜＞＞＞6、Matrix(pku2155)題目大意給定一個n*n的01矩陣，初始全部為0。要求維護兩個操作：1、Cx1y1x2y2，子矩陣(x1,y1)~(x2,y2)中數(shù)值全部取反2、Qxy，詢問點(x,y)的值樣例輸入樣例輸出

2101C21220Q220C21211Q11C1121C1212C1122Q11C1121Q21此題是區(qū)間求反問題，而樹狀數(shù)組所維護的是區(qū)間和問題。如何轉(zhuǎn)化？注意到所求為一個點的值，而點值只與求反操作次數(shù)有關(guān)首先考慮一維情況原問題變?yōu)椋簩τ谝粋€數(shù)列，每次對一段區(qū)間取反，詢問一個點的值。由于一個點的值只與取反次數(shù)有關(guān)，所以我們記錄每個點的取反次數(shù)。樹狀數(shù)組支持的操作是修改一個點的值，查詢一段區(qū)間的和。而此題恰恰相反。如何改變樹狀數(shù)組的意義？

括號每次對一段區(qū)間(a,b)取反，可以看成加了一對括號。每次詢問只需求出從1到k中左括號-右括號,即為點k修改的次數(shù)數(shù)組c[i]記錄1~i中左括號-右括號的值。每次修改(a,b),c[a]加1，c[b+1]減1。這樣，每次詢問求出c[k]，判斷奇偶即可。如何推廣到二維？查詢操作不變，對于每次修改操作(x1,y1)-(x2,y2)，我們仿照一維情形加“括號”。具體的c[x1,y1]+1,c[x2+1,y2+1]+1c[x1,y2+1]-1,c[x2+1,y1]-17、密碼機題目大意有一個初始為空的序列。維護三種命令：1、ADD<Number>把Number加到數(shù)列最后2、REMOVE<Number>在數(shù)列中找到等于<Number>的數(shù)，刪除3、xorbetween<Number1>and<Number2>對于數(shù)列中所有在[Number1,Number2]中的數(shù)異或并輸出結(jié)果加入的數(shù)不超過20000，詢問次數(shù)<=60000算法一：直接處理對于Add操作，直接將Number添加到數(shù)組尾端。O(1)對于Remove操作，直接查詢并刪除。O(n)對于Xor操作，枚舉每一個元素。O(n)時間復雜度O(T*n)小優(yōu)化Xor操作即按位異或.1xor1=0.1xor0=1.0xor0=1.對于delete操作，我們其實可以將其視為Add操作。因為axora=0.axor0=a，所以delete(Number)將相當于add(Number)這樣Delete操作復雜度降到(1)算法的瓶頸在于詢問操作由于詢問操作可能達到O(n)，所以如果要降低時間復雜度，就不能枚舉全部符合條件的數(shù)然后異或，只能利用某些方法一起計算。觀察輸入，我們發(fā)現(xiàn)加入的數(shù)不超過20000，如何利用這個條件？樹狀數(shù)組!算法二：樹狀數(shù)組將Add操作和Delete操作看成Add，把樹狀數(shù)組操作中加法改成xor。可以證明，這種方法可以得到正確的結(jié)果。對于詢問[l,r]，因為axora=0,axor0=a，可以直接輸出get(r)xorget(l-1)每個操作復雜度均為logn，總時間復雜度為O(Tlogn)8、Jason911追MMSsfz神牛頗多，但最會追MM的當屬Jason911。這一天jason911發(fā)現(xiàn)n個MM，jason911非常高興，很想讓她們?nèi)斪约篏F。但是她發(fā)現(xiàn)如果如果找太多GF會讓她們很不滿意，于是他決定只找5個MM當GF。MM們按順序排成1～n，各有一個魅力值。Jason911決定，他要使找到GF的魅力值嚴格遞增，這樣才能心情愉快。他想知道一共有多少種選法例如有7個MM，魅力值分別為{2,1,3,4,5,7,6}。合法的取法有4種，分別為{1,3,4,5,6},{2,3,4,5,6},{1,3,4,5,7}和{2,3,4,5,7}。MM最多有50000個對于一般的LIS，可以使用動態(tài)規(guī)劃，運用二分可以達到(nlogn)。本題要求方案數(shù)，樸素的DP可以另維護一個數(shù)組g[i,j]表示表示以i為結(jié)尾、長度為j的上升子序列的種數(shù)。能否仍用二分，同時求出方案數(shù)？比較困難考慮使用樹狀數(shù)組記錄次數(shù)和長度此題要求LIS長度為5，即可分為5個階段。分別為1～5，各開一個樹狀數(shù)組，記錄方案數(shù)。具體的，掃描到每個MM時，首先將其加入到第一個樹狀數(shù)組，然后j從1循環(huán)到4，判斷能夠找到多少魅力值小于她的MM，并加入到下一個樹狀數(shù)組。長度12345671+123452,1,3,4,5,7,6ij長度12345671+1123452,1,3,4,5,7,6ij長度1234567111+12+23452,1,3,4,5,7,6ij長度12345671111+122+33452,1,3,4,5,7,6ij長度1234567111112233+2452,1,3,4,5,7,6ij長度123456711111+1223+432452,1,3,4,5,7,6ij長度1234567111111223432+5452,1,3,4,5,7,6ij長度123456711111122343254+252,1,3,4,5,7,6ij長度1234567111111+12234+53254252,1,3,4,5,7,6ij長度1234567111111122345325+94252,1,3,4,5,7,6ij長度1234567111111122345325942+752,1,3,4,5,7,6ij長度123456711111112234532594275+22,1,3,4,5,7,6ij長度1234567111111+112234+553259427522,1,3,4,5,7,6ij長度123456711111111223455325+99427522,1,3,4,5,7,6ij長度1234567111111112234553259942+77522,1,3,4,5,7,6ij長度1234567111111112234553259942775+222,1,3,4,5,7,6ij長度1234567111111112234553259942775222,1,3,4,5,7,6ij答案是4小結(jié)利用括號的思想，樹狀數(shù)組可以在一定程度上解決修改區(qū)間、查詢點值的功能。對于一些狀態(tài)階段、要求統(tǒng)計方案數(shù)的題目，常使用多棵樹狀數(shù)組分階段記錄，并在階段之間轉(zhuǎn)移。9、Japan(pku3067)題目大意給定一個二分圖，左邊M個點，右邊N個點，從上倒下分別為1,2,3……中間有一些邊連接兩端的點，任意三條邊不共點。求出總交點個數(shù)M,N<=1000,k<=100000樣例輸入

344(n,m,k)14233231樣例輸出5如何運用點的有序性？相交的實質(zhì)？(x1,y1),(x2,y2)兩邊相交的條件:x1<x2,y1>y2應用同樣的思路，轉(zhuǎn)化為一個條件！按左端點對邊排序（如果相同則右端點小的在前）。掃描每一條邊，這樣保證了已經(jīng)加入邊的左端點在當前邊上方。這樣只需查找有多少條已經(jīng)掃描過的邊的右端點在當前邊下方。如圖，當掃描到紅色邊時，我們需要查找的區(qū)域即為3,4，各有一條邊形成相交由此，問題變成了改變點的值，詢問一個區(qū)間內(nèi)點值和

樹狀數(shù)組！

樹狀數(shù)組求最值問：樹狀數(shù)組能求最值么？前ｉ項的最值是可以求的。只要把求和改成ｍａｘ就可以了。但是求［ｌｅｆｔ，ｒｉｇｈｔ］之間的最值能求么？思考一下！好像無從下手。我們先討論先構(gòu)造，只查詢，不修改的那種模式。修改值還是和求和一樣的voidInit(intn){

for(inti=1;i<=n;i++)

for(intj=i;j<=n;j+=Lowbit(j))

c[j]=MAX(c[j],num[i]);

}這種方法在每次調(diào)用該函數(shù)前都必須對數(shù)組進行初始化，這樣對于數(shù)據(jù)范圍比較大的時候不是很優(yōu)美,這樣我們可以改為：voidInit(intn){

for(inti=1;i<=n;i++){

c[i]=num[i];

for(intj=1;j<Lowbit(i);j<<=1)

c[i]=MAX(c[i],c[i-j]