前言：
最近在刷leetcode的最後30題了，馬上就要刷完，然後再來一遍2刷提高熟練度。在最後這些題目裡，遇上了樹狀數組這個新的資料結構。問題都是簡單的數組統計問題，但是O(N)的解都不能滿足要求，需要使用O(lgn)才行。樹狀數組不太容易了解，找了好幾篇部落格才測定明白，這裡貼出來。
我的github：
leetcode馬上就要做完了，我做題的時候貼上了詳細的思考記錄以及解題求助到的部落格等。對自己幫助很大，希望也能幫組到大家。
https://github.com/YinWenAtBIT
引用請注明出處：http://blog.csdn.net/int64ago/article/details/7429868
寫下這個标題，其實心裡還是沒底的，與其說是寫博帖，不如說是做總結。第一個接觸樹狀數組還是兩年前，用什麼語言來形容當時的感覺呢？……太神奇了！真的，無法表達出那種感覺，她是那麼的優雅，10行不到的代碼，卻把事情幹的如此出色！沒有了解她原理的前提下即使把代碼倒背如流也了解不了！其中，我就是一直沒搞懂地在使用她。時隔兩年，又無意遇到了她，可能是兩年的代碼經驗的積累，有了些新的認識，可以自信的說了解了吧！下面我争取用自己的方式讓更多人明白她，而不是背誦她。為了更友善的說明，文章裡會自己強加一些概念，隻是為了更好的了解，不是什麼專業術語之類的。
一、樹狀數組是幹什麼的？
平常我們會遇到一些對數組進行維護查詢的操作，比較常見的如，修改某點的值、求某個區間的和，而這兩種恰恰是樹狀數組的強項！當然，資料規模不大的時候，對于修改某點的值是非常容易的，複雜度是O(1)，但是對于求一個區間的和就要掃一遍了，複雜度是O(N)，如果實時的對數組進行M次修改或求和，最壞的情況下複雜度是O(M*N)，當規模增大後這是劃不來的！而樹狀數組幹同樣的事複雜度卻是O(M*lgN)，别小看這個lg，很大的數一lg就很小了，這個學過數學的都知道吧，不需要我說了。申明一下，看下面的文章一定不要急，隻需要看懂每一步最後自然就懂了。
二、樹狀數組怎麼幹的？
先看兩幅圖（網上找的，如果雷同，不要大驚小怪～），下面的說明都是基于這兩幅圖的，左邊的叫A圖吧，右邊的叫B圖：
是不是很像一顆樹？對，這就是為什麼叫樹狀數組了～先看A圖，a數組就是我們要維護和查詢的數組，但是其實我們整個過程中根本用不到a數組，你可以把它當作一個擺設！c數組才是我們全程關心和操縱的重心。先由圖來看看c數組的規則，其中c8 = c4+c6+c7+a8，c6 = c5+a6……先不必糾結怎麼做到的，我們隻要知道c數組的大緻規則即可，很容易知道c8表示a1～a8的和，但是c6卻是表示a5～a6的和，為什麼會産生這樣的差別的呢？或者說發明她的人為什麼這樣差別對待呢？答案是，這樣會使操作更簡單！看到這相信有些人就有些感覺了，為什麼複雜度被lg了呢？可以看到，c8可以看作a1～a8的左半邊和+右半邊和，而其中左半邊和是确定的c4，右半邊其實也是同樣的規則把a5～a8一分為二……繼續下去都是一分為二直到不能分，可以看看B圖。怎麼樣？是不是有點二分的味道了？對，說白了樹狀數組就是巧妙的利用了二分，她并不神秘，關鍵是她的巧妙！
她又是怎樣做到不斷的一分為二呢？說這個之前我先說個叫lowbit的東西，lowbit(k)就是把k的二進制的高位1全部清空，隻留下最低位的1,比如10的二進制是1010,則lowbit(k)=lowbit(1010)=0010(2進制)，介于這個lowbit在下面會經常用到，這裡給一個非常友善的實作方式，比較普遍的方法lowbit(k)=k&-k，這是位運算，我們知道一個數加一個負号是把這個數的二進制取反+1，如-10的二進制就是-1010=0101+1=0110，然後用1010&0110，答案就是0010了！明白了求解lowbit的方法就可以了，繼續下面。介于下面讨論十進制已經沒有意義（這個世界本來就是二進制的，人非要主觀的建構一個十進制），下面所有的數沒有特别說明都當作二進制。
上面那麼多文字說lowbit，還沒說它的用處呢，它就是為了聯系a數組和c數組的！ck表示從ak開始往左連續求lowbit(k)個數的和，比如c[0110]=a[0110]+a[0101]，就是從110開始計算了0010個數的和，因為lowbit(0110)=0010，可以看到其實隻有低位的1起作用，因為很顯然可以寫出c[0010]=a[0010]+a[0001]，這就為什麼我們任何數都隻關心它的lowbit，因為高位不起作用（基于我們的二分規則它必須如此！），除非除了高位其餘位都是0，這時本身就是lowbit。
既然關系建立好了，看看如何實作a某一個位置資料跟改的，她不會直接改的（開始就說了，a根本不存在），她每次改其實都要維護c數組應有的性質，因為後面求和要用到。而維護也很簡單，比如更改了a[0011]，我們接着要修改c[0011],c[0100],c[1000]，這是很容易從圖上看出來的，但是你可能會問，他們之間有申明必然聯系嗎？每次求解總不能總要拿圖來看吧？其實從0011——>0100——>1000的變化都是進行“去尾”操作，又是自己造的詞--''，我來解釋下，就是把尾部應該去掉的1都去掉轉而換到更高位的1,記住每次變換都要有一個高位的1産生，是以0100是不能變換到0101的，因為沒有新的高位1産生，這個變換過程恰好是可以借助我們的lowbit進行的，k +=lowbit(k)。
好吧，現在更新的次序都有了，可能又會産生新的疑問了：為什麼它非要是這種關系啊？這就要追究到之前我們說c8可以看作a1～a8的左半邊和+右半邊和……的内容了，為什麼c[0011]會影響到c[0100]而不會影響到c[0101]，這就是之前說的c[0100]的求解實際上是這樣分段的區間 c[0001]~c[0001] 和區間c[0011]~c[0011]的和，數字太小，可能這樣不太了解，在比如c[0100]會影響c[1000]，為什麼呢？因為c[1000]可以看作0001～0100的和加上0101~1000的和，但是0101位置的數變化并會直接作用于c[1000]，因為它的尾部1不能一下在跳兩級在産生兩次高位1,是通過c[0110]間接影響的，但是，c[0100]卻可以跳一級産生一次高位1。
可能上面說的你比較繞了，那麼此時你隻需注意：c的構成性質（其實是分組性質）決定了c[0011]隻會直接影響c[0100]，而c[0100]隻會直接影響[1000]，而下表之間的關系恰好是也必須是k +=lowbit(k)。此時我們就是寫出跟新維護樹的代碼：
[cpp] view plain copy print ?
- void add(int k,int num)
- {
- while(k<=n)
- {
- tree[k]+=num;
- k+=k&-k;
- }
- }
有了上面的基礎，說求和就比較簡單了。比如求0001～0110的和就直接c[0100]+c[0110]，分析方法與上面的恰好逆過來，而且寫法也是逆過來的，具體就不累述了：
[cpp] view plain copy print ?
- int read(int k)//1~k的區間和
- {
- int sum=0;
- while(k)
- {
- sum+=tree[k];
- k-=k&-k;
- }
- return sum;
- }
三、總結一下吧
首先，明白樹狀數組所白了是按照二分對數組進行分組；維護和查詢都是O(lgn)的複雜度，複雜度取決于最壞的情況，也是O(lgn);lowbit這裡隻是一個技巧，關鍵在于明白c數組的構成規律;分析的過程二進制一定要深入人心，當作心目中的十進制。
第二篇部落格：
樹的結構圖
讓我們來看看圖：橫坐标是x, 縱坐标是lowbit(x)
對于節點x，
- 為左子結點，則父結點的編号是x+lowbit(x)，
- 為右子結點，則父結點的編号是x-lowbit(x)
設C[i] 為以i結尾的水準長條内的元素之和，如c[6]=a5+a6。
- 順着結點I往左走，邊走邊往上爬，沿途經過的c[i]所對應的長條不重複不遺漏的包含了所有需要累加的元素。
- 如sum(6) = c[6] + c[4]
- 如果修改了一個a[i] ,那麼從c[i]往右走，邊走邊網上爬，沿途修改所有結點對應的c[i]即可。
- 如a[1] + 1 那麼 c[1] + 1, c[2]+1,c[4]+1………一直到最大值。
總結：
第一篇部落格裡講訴了樹狀數組的一些特性，但是對于圖的解釋不清，這裡貼上第二篇部落格加上了對圖的解釋，基本上能對這個加深了解了。