并查集樹狀數組

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

2、 + + ai，k為i在二進制下末尾0的個數。K的計算可以這樣: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表示的是哪個區(qū)域的和,只要求出2k(lowbit);樹狀數組之所以高效簡潔的原因就是能夠利用位運算直接求出i對應的lowbitint lowbit(int i) return i & ( -i );解釋:假設i為 則-i的 :1) 取反 2)+1 =求和Sum知道每個變量表示哪段的區(qū)間和之后就可以很快的求出前綴

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

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

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