信息學-數(shù)據(jù)結(jié)構(gòu)樹狀數(shù)組

樹狀數(shù)組

樹狀數(shù)組的運用首先我們得知道一個問題,那就是線段樹得作用并不只是用來存儲線段的,也可以存儲點的值等等.對于靜態(tài)的線段樹,空間上需要的數(shù)組有:當前結(jié)點的數(shù)據(jù)值,左兒子編號,右兒子編號.至少這么三個數(shù)組.而在時間上雖然是NlogN的復(fù)雜度,但是系數(shù)很大.實現(xiàn)起來的時候編程復(fù)雜度大,空間復(fù)雜度大,時間效率也不是很理想.樹狀數(shù)組的運用那么是否有更好的解決方法呢?有!那就是樹狀數(shù)組!樹狀數(shù)組的運用先看一個例題:數(shù)列操作:給定一個初始值都為0的序列,動態(tài)地修改一些位置上的數(shù)字,加上一個數(shù),減去一個數(shù),或者乘上一個數(shù),然后動態(tài)地提出問題,問題的形式是求出一段數(shù)字的和.樹狀數(shù)組的運用如果直接做的話,修改的復(fù)雜度是O(1),詢問的復(fù)雜度是O(N),M次詢問的復(fù)雜度是M*N.M,N的范圍可以有100000以上樹狀數(shù)組的運用用線段樹可以這樣解:若要維護的序列范圍是0..5,先構(gòu)造下面的一棵線段樹:樹狀數(shù)組的運用可以看出,這棵樹的構(gòu)造用二分便可以實現(xiàn).復(fù)雜度是2*N.每個結(jié)點用數(shù)組a來表示該結(jié)點所表示范圍內(nèi)的數(shù)據(jù)之和.修改一個位置上數(shù)字的值,就是修改一個葉子結(jié)點的值,而當程序由葉子結(jié)點返回根節(jié)點的同時順便修改掉路徑上的結(jié)點的a數(shù)組的值.對于詢問的回答,可以直接查找i..j范圍內(nèi)的值,遇到分叉時就兵分兩路,最后在合起來.也可以先找出0..i-1的值和0..j的值,兩個值減一減就行了.后者的實際操作次數(shù)比前者小一些.這樣修改與維護的復(fù)雜度是logN.詢問的復(fù)雜度也是logN,對于M次詢問,復(fù)雜度是MlogN.樹狀數(shù)組的運用用樹狀數(shù)組!!!然而不難發(fā)現(xiàn),線段樹的編程復(fù)雜度大,空間復(fù)雜度大,時間效率也不高.怎么辦樹狀數(shù)組的運用下圖中的C數(shù)組就是樹狀數(shù)組,a數(shù)組是原數(shù)組先自己研究一下這個東西樹狀數(shù)組的運用可以發(fā)現(xiàn)這些規(guī)律C1=a1C2=a1+a2C3=a3C4=a1+a2+a3+a4C5=a5……C8=a1+a2+a3+a4+a5+a6+a7+a8……C2^n=a1+a2+….+a2^n樹狀數(shù)組的運用對于序列a，我們設(shè)一個數(shù)組C定義C[i]=a[i–2^k+1]+…+a[i]，k為i在二進制下末尾0的個數(shù)。K的計算可以這樣:2^k=xand(xxor(x-1))以6為例(6)10=(0110)2xor6-1=(5)10=(0101)2(0011)2and(6)10=(0110)2(0010)2樹狀數(shù)組的運用functionLowbit(x:Integer):Integer;beginLowbit:=xand(xxor(x–1));end;若要修改a[i]的值,則C數(shù)組的修改是:Procedurechange(k,delta:integer);Beginwhilek<=ndobeginC[k]:=C[k]+delta;k:=k+lowbit(k);End;End;樹狀數(shù)組的運用若要求I..j的元素和的值,則求出1..I-1的值和1..j的值.Functiongetsum(k:integer):integer;Vart:integer;Begint:=0;whilek>0dobegint:=t+c[k];k:=k-lowbit(k);end;getsum:=t;End;樹狀數(shù)組的運用對于剛才的一題,每次修改與詢問都是對C數(shù)組做處理.空間復(fù)雜度有3N降為N,時間效率也有所提高.編程復(fù)雜度更是降了不少.優(yōu)秀的算法！樹狀數(shù)組的運用密碼機(浙江2003省賽)算法:樹狀數(shù)組或者線段樹與上題相比,所有的加號變成了xor.由于xor滿足交換律,結(jié)合律,所以可以和加法一樣地做.又AxorA=0,Axor0=A.所以ADD和REMOVE是一樣的操作.樹狀數(shù)組的運用Ural1028Star

天空中有一些星星，這些星星都在不同的位置，每個星星有個坐標。

如果一個星星的左下方（包含正左和正下)有k顆星星，就說這顆星星是k級的.比如，在下面的例圖中，星星5是3級的（1，2，4在它左下）。

星星2，4是1級的。例圖中有1個0級，2個1級，1個2級，1個3級的星。求出各個級別的星星的個數(shù)樹狀數(shù)組的運用算法有很多種,最實用的是樹狀數(shù)組先對X排序,然后就是查找每個坐標前面的坐標種Y比他小的又多少個.這需要樹狀數(shù)組.樹狀數(shù)組存儲的是某一段范圍內(nèi)有多少個點.小結(jié)