1、樹狀數(shù)組 先看一個(gè)例題:數(shù)列操作: 給定一個(gè)初始值都為0的序列,動(dòng)態(tài)地修改一些位置上的數(shù)字,加上一個(gè)數(shù),減去一個(gè)數(shù), 然后動(dòng)態(tài)地提出問題,問題的形式是求出一段數(shù)字的和.如果直接做的話,修改的復(fù)雜度是O(1),詢問的復(fù)雜度是O(N),M次詢問的復(fù)雜度是M*N.M,N的范圍可以有100000以上用樹狀數(shù)組!怎么辦下圖中的C數(shù)組就是樹狀數(shù)組,a數(shù)組是原數(shù)組可以發(fā)現(xiàn)這些規(guī)律C1=a1C2=a1+a2C3=a3C4=a1+a2+a3+a4C5=a5C6=a5+a6C8=a1+a2+a3+a4+a5+a6+a7+a8C2n=a1+a2+.+a2n對(duì)于序列a，我們?cè)O(shè)一個(gè)數(shù)組C定義Ci = ai 2k + 1

2、 + + ai，k為i在二進(jìn)制下末尾0的個(gè)數(shù)。K的計(jì)算可以這樣:2k=x and (x xor (x-1) 以6為例 (6)10=(0110)2xor 6-1=(5)10=(0101)2 (0011)2and (6)10=(0110)2 (0010)22K(lowbit)求法要想知道ci表示的是哪個(gè)區(qū)域的和,只要求出2k(lowbit);樹狀數(shù)組之所以高效簡潔的原因就是能夠利用位運(yùn)算直接求出i對(duì)應(yīng)的lowbitint lowbit(int i) return i & ( -i );解釋:假設(shè)i為 則-i的 :1) 取反 2)+1 =求和Sum知道每個(gè)變量表示哪段的區(qū)間和之后就可以很快的求出前綴

3、和了;要求sum(i) = a1+.+ai;ci表示ai-lowbit(i)+1+.+ai;還需要求a1+.+ai-lowbit(i);于是可以直接用一個(gè)循環(huán)求得sum,時(shí)間復(fù)雜度為O(logN)int getSum(int x)int sum= 0;for (int i = x; i 0; i -= lowbit(i)sum += ci;return sum;轉(zhuǎn)化為子問題了!循環(huán)的次數(shù)為x的二進(jìn)制表示中1的個(gè)數(shù)修改modify修改了某個(gè)ai,就需改動(dòng)所有包含ai的cj;從上圖看就是要更改從改葉子節(jié)點(diǎn)到根節(jié)點(diǎn)路徑上的所有cj但是怎么求一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)呢?Thinking.找父節(jié)點(diǎn)增加虛構(gòu)點(diǎn),變

4、成滿二叉樹!每個(gè)節(jié)點(diǎn)的父親就跟其右兄弟一樣了;而左右兄弟的管轄區(qū)域是一樣的;所以:i的父節(jié)點(diǎn)就是i+lowb(i);修改modifyvoid modify(int x,int delta)for(int i = x; i=n; i+=lowbit(i)ci += delta;/*其中n為數(shù)組的長度時(shí)間復(fù)雜度同樣是O(logN)的*/樹狀數(shù)組的運(yùn)用對(duì)于剛才的一題,每次修改與詢問都是對(duì)C數(shù)組做處理.空間復(fù)雜度為N,時(shí)間效率也有提高.編程復(fù)雜度更是降了不少.優(yōu)秀的算法！樹狀數(shù)組的運(yùn)用Poj2352 Star 天空中有一些星星，這些星星都在不同的位置，每個(gè)星星有個(gè)坐標(biāo)。如果一個(gè)星星的左下方（包含正左和

5、正下)有k顆星星，就說這顆星星是k級(jí)的.比如，在下面的例圖中，星星5是3級(jí)的（1，2，4在它左下）。星星2，4是1級(jí)的。例圖中有1個(gè)0級(jí)，2個(gè)1級(jí)，1個(gè)2級(jí)，1個(gè)3級(jí)的星。求出各個(gè)級(jí)別的星星的個(gè)數(shù)題目分析：算法有很多種,最實(shí)用的是樹狀數(shù)組由于本題的數(shù)據(jù)輸入是以y坐標(biāo)的升序輸入，所以，只需要比較x坐標(biāo)即可樹狀數(shù)組存儲(chǔ)的是某一段范圍內(nèi)有多少個(gè)點(diǎn)，即求和.小結(jié)在很多的情況下,線段樹都可以用樹狀數(shù)組實(shí)現(xiàn).凡是能用樹狀數(shù)組的一定能用線段樹.當(dāng)題目不滿足減法原則的時(shí)候,就只能用線段樹,不能用樹狀數(shù)組.例如數(shù)列操作如果讓我們求出一段數(shù)字中最大或者最小的數(shù)字,就不能用樹狀數(shù)組了.樹狀數(shù)組的每個(gè)操作都是0(log(n)的復(fù)雜度.Thanks. .Just do it:簡單:POJ 2299 Ultra-QuickSortPOJ 2352 StarsPOJ 1195 Mobile phones 中