漫畫：什么是樹狀數(shù)組？
我們學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的目的在于將我們的算法變得更快。由 Peter M. Fenwick 提出的樹狀數(shù)組 BIT 結(jié)構(gòu)就是一個(gè)優(yōu)秀的數(shù)據(jù)結(jié)構(gòu)，BIT 全稱 Binary Indexed Trees 結(jié)構(gòu)，而不是所說的比特奧。Peter M. Fenwick 首次使用此結(jié)構(gòu)進(jìn)行數(shù)據(jù)壓縮。在算法競賽中，通常用于存儲頻率和處理累積頻率表。
首先考慮一個(gè)簡單的問題。
給定一個(gè)數(shù)組 arr[0 ... n-1] ，如何實(shí)現(xiàn)下面兩個(gè)操作：
計(jì)算前 i 個(gè)元素的累加和； 將數(shù)組中下標(biāo)為 i 的元素的值更新為 x， arr[i] = x，其中0 <= i <= n-1
一個(gè)簡單的方法就是遍歷 0 到 i - 1 的元素并計(jì)算出累加和即可 ；然后更新操作 arr[i] = x 就可以直接進(jìn)行，也就說可以對數(shù)組 arr[] 直接進(jìn)行修改.
//?計(jì)算前?i?個(gè)元素的累加和
public?int?getSum(int?arr[],?int?i){
????int?sum?=?0;
????for(int?j?=?0;?j?????????sum?+=?arr[j];
????}
????return?sum;
}
這種方式第一個(gè)操作，也就是計(jì)算累加和的時(shí)間復(fù)雜度為 ，更新操作的時(shí)間復(fù)雜度為 ;
另外一種方式就是創(chuàng)建一個(gè)大小為 n 的新數(shù)組，并且在新數(shù)組的第 i 個(gè)位置保存前 i 個(gè)元素的累加和。此時(shí)查找給定范圍內(nèi)的累加和就可以在 的時(shí)間內(nèi)完成，但是更新操作將花費(fèi) 的時(shí)間，這對于大量的查詢操作，而更新操作比較少的問題很實(shí)用。
//?更新數(shù)組?arr[i]?=?x?之后
//?需要對存儲累加和的數(shù)組 new_arr 進(jìn)行的修改。
void?updateSum(int?arr[],?int?i,?int?x){
????arr[i]?=?x;
????for(int?j?=?i;?j?????????new_arr[j]?=?new_arr[j-1]?+?arr[j];
????}
}
也就說，要實(shí)現(xiàn)上面提到的兩個(gè)操作，要么查找為 ，更新操作為 ；要么使用額外的空間，將查找操作降為 ，但是更新操作變?yōu)榱? .
樹狀數(shù)組
那么是否可以將查找和更新操作同時(shí)降低到 呢？
一個(gè)就是以后會講到的線段樹（Segment Tree），另外一個(gè)就是樹狀數(shù)組 （Binary Indexed Tree），兩者均可以將上面所提到的查找和更新操作的時(shí)間復(fù)雜度降到 。但是與線段樹相比，樹狀數(shù)組的效率更高，并且易于實(shí)現(xiàn)。
樹狀數(shù)組表示為 BITree[]；樹狀數(shù)組的每個(gè)節(jié)點(diǎn)存儲輸入數(shù)組中某些元素的和；樹狀數(shù)組的大小等于輸入數(shù)組的大小，記作 n 。為了便于實(shí)現(xiàn)，BITree[] 使用 n+1 的大小。
首先，我們給出一個(gè)數(shù)組 arr[] :
然后直接直觀地看一下針對這個(gè)數(shù)組 arr[] 的樹狀數(shù)組：
事實(shí)上這棵樹并不存在，樹狀數(shù)組依然只是下面的一個(gè)數(shù)組而已：
現(xiàn)在的問題是如何從原始數(shù)組 arr[] 得出樹狀數(shù)組 BITree[] 呢？
答案很簡單：
首先將樹狀數(shù)組 BITree[]的所有元素初始化為 0；調(diào)用 updateBITree()函數(shù)更新BITree[]數(shù)組即可。
所以關(guān)鍵就是實(shí)現(xiàn) ?updateBITree() 函數(shù)啦！
實(shí)現(xiàn)（敲代碼）不是關(guān)鍵，重要的是理解為什么！
我們先來細(xì)致地看一趟 ? updateBITree() 函數(shù)的執(zhí)行過程：
第一步：index = 1 ，將 BITree[1] = BITree[1] + arr[0] :
第二步：更新 index = index + index & (-index) = 1 + 1 = 2 ，這里你可能一頭霧水，沒關(guān)系，這篇文章最后沒有讓你徹底明白樹狀數(shù)組，你大可噴我！我暫且不解釋它的含義和作用，我們僅僅解釋一下 index & (-index) 表示什么。index & (-index) 表示將 index 所代表的值轉(zhuǎn)化為二進(jìn)制之后，從右向左數(shù)，第一個(gè) 1 的位置，例如 6 & (-6) ，6 的二進(jìn)制為 110 ，從右向左數(shù)，第一個(gè) 1 的位置是 2 ，那么 6 & (-6) = 2 。當(dāng)然這是二進(jìn)制運(yùn)算之中取最后一個(gè) 1 的小訣竅，下面是的，以一個(gè)32位的機(jī)器為例：
這里如果有問題，大家可以看一下 劍指 offer 面試題精選圖解 15 . 二進(jìn)制中1的個(gè)數(shù) 這篇文章，然后復(fù)習(xí)一下原碼、反碼和補(bǔ)碼接著看。
第三步：index = 2 ，將 BITree[2] = BITree[2] + arr[0] :
第四步：更新 index = index + index & (-index) = 2 + 2 = 4
第五步：index = 4 ，將 BITree[4] = BITree[4] + arr[0] :
第六步：更新 index = index + index & (-index) = 4 + 4 = 8
第七步：index = 8 ，將 BITree[8] = BITree[8] + arr[0] :
第八步：更新 index = index + index & (-index) = 8 + 8 = 16 ，16 > 12 ，已經(jīng)超出了樹狀數(shù)組 BITree[] 的下標(biāo)，一趟 ?updateBITree() 函數(shù)的執(zhí)行結(jié)束啦！知道你沒啥感覺更是沒有體會到樹狀數(shù)組的妙用（我剛開始也是，說實(shí)話，笨笨的大禹看了好幾天）。
但是當(dāng)你將所有的步驟都都走完之后，你就會感覺不一樣啦！
圖中沒有填充的單元格都表示 0，第 1 趟 ?updateBITree() 函數(shù)確定了 BITree[1] 的值，第 2 趟 updateBITree() 函數(shù)確定了 BITree[2] 的值，以此類推，第 12 趟 ?updateBITree() 函數(shù)確定了 BITree[12] 的值，也就是結(jié)果 12 （12就是數(shù)組 arr[] 的大?。┨烁?，我們得到了我們的主角 BITree[] 樹狀數(shù)組：
也就是，我們完成了從數(shù)組 ?arr[] ?到 BITree[] 的過渡。
下面我要告訴你的才是樹狀數(shù)組的關(guān)鍵和核心奧！
樹狀數(shù)組的關(guān)鍵不是 BITree[] ，而是 下標(biāo) 。
假設(shè)現(xiàn)在的原始數(shù)組 arr[] 的大小 n = 16 ，我們看下標(biāo) 1 到 16 到底如何成為樹狀數(shù)組的關(guān)鍵所在的。
對于上面的每一個(gè) index , 均計(jì)算 index & (-index) 的值，比如 10，可以計(jì)算得到 10 & (-10) = 2 ，實(shí)在不會也沒關(guān)系，就把 10 轉(zhuǎn)化為二進(jìn)制 1010 ，然后從右向左數(shù)數(shù)，碰到的第一個(gè) 1 的位置就是 2 （其他數(shù)字的計(jì)算都是一樣的過程，就不過多說明）。
而這個(gè) ?index & (-index) 所對應(yīng)的值有何意義呢？
答案，index & (-index) 表示一個(gè)范圍，千篇一律的叫法叫做 Lowbit(index)。
以 index & (-index) 中的第一個(gè) 1 為例，它表示將數(shù)組 arr[] 中當(dāng)前位置向前累加 1 個(gè)數(shù)字，作為 ?BITree[index] 的值，即 BITree[1] = 2 .
那么 BITree[] 數(shù)組中的值 30 的由來就更好解釋了，就是從當(dāng)前元素 9 向前累加 4 個(gè)元素（包含自身），即 9 + 8 + 7 + 6 = 30
對于 index & (-index) 中的其他元素的解釋是同樣的道理。但是 index & (-index) 所表示的數(shù)組你以為就這樣簡單嗎？若真是如此，估計(jì)我就不講了。
就一棵樹而言，必定有父子之分，那么樹狀數(shù)組是如何體現(xiàn)父子關(guān)系的呢？
BITree[y]是BITree[x]的父結(jié)點(diǎn)，當(dāng)且僅當(dāng) y 可以通過從 x 的二進(jìn)制表示中刪除最后一個(gè)位置的 1 （也就是從右向左第一個(gè)） 來獲得，即y = x - (x & (-x))
有了這樣的父子關(guān)系，僅使用 ?index & (-index) 就可以直觀地構(gòu)建出我們期待已久的樹狀數(shù)組中所謂的樹。
已知 index 和 ? index & (-index) ，計(jì)算兩者之差簡直輕而易舉：
那么構(gòu)建一顆樹還難嗎？一點(diǎn)兒都不。
比如 y 等于 0 ，視線向上找到對應(yīng)的 index，分別為 1、2，4、8、16，也就是說，0是 1、2、4、8、16 的父結(jié)點(diǎn)；
同理，2 是 3 的父結(jié)點(diǎn)、4 是 5 和 6 的父結(jié)點(diǎn)、6 是 7 的父結(jié)點(diǎn)、8 是 9 和 10 的父結(jié)點(diǎn)，10 是 11 和12 的父結(jié)點(diǎn)、12 是 13 和 14 的父結(jié)點(diǎn)，14 是 15 的父結(jié)點(diǎn)。
就得到了下圖：
這棵樹的得出與原數(shù)組 arr[] 本身沒有關(guān)系，而僅僅與下標(biāo) index 有關(guān)。而我們最開始所看到的樹同樣如此（只不過樹中結(jié)點(diǎn)的真正的值是我們所計(jì)算出的 BITree[index] ：
樹狀數(shù)組的幾大特點(diǎn)：
BITree[0] 是一個(gè)虛擬結(jié)點(diǎn)，同時(shí)也是我們所看到的根結(jié)點(diǎn) BITree[y]是BITree[x]的父結(jié)點(diǎn)，當(dāng)且僅當(dāng) y 可以通過從 x 的二進(jìn)制表示中刪除最后一個(gè)位置的 1 （也就是從右向左第一個(gè)） 來獲得，即y = x - (x & (-x))BITree[y]的孩子結(jié)點(diǎn)BITree[x]存儲的是數(shù)組arr[]中下標(biāo)從 y (包含) 到 x (不包含) 的累加和，即arr[y,...,x),注意括號是不包含 x；
關(guān)于這個(gè)第三條可能需要稍微解釋一下：
BITree[8] 的孩子結(jié)點(diǎn) BITree[12] 的值等于 30 ，表示數(shù)組 arr[] 中下標(biāo)從 8 到 12（不包含 12）的元素的累加和，即 ?BITree[12] = 30 = arr[8,...,12) = 6 + 7 + 8 + 9 。
其實(shí)這里就和之前我們介紹的 ?index & (-index) 所表示含義不謀而合。
是不是有點(diǎn)兒清晰呢？很快你就會看到一句話概括上面所講的所有內(nèi)容。
回到我們最開始的兩個(gè)問題。
如何根據(jù) BITree[] ?樹狀數(shù)組，獲取數(shù)組 arr[] 中前 i 個(gè)元素的累加和？
這里更關(guān)鍵奧?。?！
我們都知道，任何一個(gè)正整數(shù)都可以被表示為 2 的次冪和，比如 11 可以表示為 8 + 2 + 1. BITree的每個(gè)節(jié)點(diǎn)都存儲 n 個(gè)元素的總和，其中 n 是 2 的次冪。比如前 11 個(gè)元素的累加和可以通過對原數(shù)組 arr[] 中最后 1 個(gè)元素（第11個(gè)元素）、向前兩個(gè)元素（第 9 和 10 號元素）和 前 8 個(gè)元素 （從 1 到 8 的）的元素之和求得。
對照上圖，來理解文字描述就更清晰了，我們求前 11 個(gè)元素的累加和，可以將其分解為 2 的次冪之和，即 8 + 2 + 1，也就是前 8 個(gè)元素的累加和（1 到 8），緊挨著的 2 個(gè)元素（9 和 10），和最后 1個(gè)元素 （11）三者的和。
如果從樹狀數(shù)組的角度來看，BITree[8] = 21 ?表示前 8 個(gè)元素的累加和，BITree[10] = 13 ?表示 6 和 7 的和（這里解釋一下， 表示的就是兩個(gè)數(shù)的和）， BITree[11] = 8 ?表示一個(gè) 8 （，表示 1 個(gè)數(shù)的和） 。所以前 11 個(gè)元素的累加和等于 BITree[8] + BITree[10] + BITree[11] = 21 + 13 + 8 = 42 。
如果再從更直觀的樹上看，計(jì)算前 11 個(gè)元素的累加和，從葉子結(jié)點(diǎn) 11 開始，找到 11 的父結(jié)點(diǎn) 10，然后找到 10 的父結(jié)點(diǎn) 8 ，8 的父結(jié)點(diǎn)為 0 ，然后將路徑上的值都加起來，就是前 11 個(gè)元素的累加和。
不難寫出下面計(jì)算累加和的代碼：
int?getSum(int?index)?
{?
????int?sum?=?0;?//?累加和
????//?BITree[]?的下標(biāo)比?arr[]?大?1
????index?=?index?+?1;?
????//?遍歷?BITree[index]?的祖先結(jié)點(diǎn)
????while(index>0)?
????{?
????????//?將當(dāng)前?BITree?的值加到?sum
????????sum?+=?BITree[index];?
????????//?將 index 指向 index 的父結(jié)點(diǎn)
????????index?=?index?-?index?&?(-index);?
????}?
????return?sum;?
}?
代碼很清晰，就是從給定的 index 遍歷 index 的所有的祖先結(jié)點(diǎn)，并將遍歷到的 BITree[index] ?的值加起來即可。
如何將數(shù)組中下標(biāo)為 i 的元素的值更新為 x，且在 O(logn) 的時(shí)間內(nèi)更新樹狀數(shù)組 BITree[] ?
雖然關(guān)于這個(gè)問題在最開始的時(shí)候已有闡述，但我們再以一個(gè)例子介紹一遍！
現(xiàn)在將 arr[3] = arr[3] + 6 ，時(shí)間復(fù)雜度為 :
然后更新樹狀數(shù)組 BITree[] ，時(shí)間復(fù)雜度為 :
index = 4 ，將 BITree[index] += val ，即 BITree[4] = 7 + 6 = 13 .
更新 index ，index = index + index & (-index) = 4 + 4 = 8 ;
更新 BITree[index] ，即 BITree[8] = 21 + 6 = 27 :
更新 index ，index = index + index & (-index) = 8 + 8 = 16 > 12 ，更新過程結(jié)束。
代碼也相當(dāng)簡單：
public?static?void?updateBIT(int?n,?int?index,?int?val)?
{?
????//?BITree[]?的下標(biāo)比?arr[]?大?1
????index?=?index?+?1;?
????//?遍歷所有的祖先，并加上?'val'
????while(index?<=?n)?
????{?
????????//?BIT?Tree?的當(dāng)前結(jié)點(diǎn)加上?'val'
????????BITree[index]?+=?val;?
????????//?更新?index
????????index?+=?index?&?(-index);?
????}?
}
能否將樹狀數(shù)組擴(kuò)展到以 的時(shí)間復(fù)雜度計(jì)算區(qū)間和呢？
答案是肯定的，rangSum(l,r) = getSum(r) - getSum(l - 1) .
復(fù)雜度分析
任何一個(gè)正整數(shù) n 的二進(jìn)制表示中置位數(shù)的個(gè)數(shù)為 量級，置位數(shù)就是一個(gè)整數(shù)二進(jìn)制表示中 1 的數(shù)目。因此，getSum() ?和 updateBIT() 兩個(gè)操作至多遍歷 個(gè)結(jié)點(diǎn)。
初始構(gòu)造樹狀數(shù)組 BITree[] 的時(shí)間復(fù)雜度為 ，構(gòu)造 BITree[] 樹狀數(shù)組會調(diào)用 updateBIT() 函數(shù) n 次。
完整的實(shí)現(xiàn)代碼
import?java.util.*;?
import?java.lang.*;?
import?java.io.*;?
class?BinaryIndexedTree?
{?
????final?static?int?MAX?=?100;??
????static?int?BITree[]?=?new?int[MAX];?
?
????int?getSum(int?index)?
????{?
????????int?sum?=?0;
??????index?=?index?+?1;?
?
??????while(index>0)?
??????{?
?????????sum?+=?BITree[index];?
?????????index?-=?index?&?(-index);?
??????}?
??????return?sum;?
???}?
???public?static?void?updateBIT(int?n,?int?index,?
??????????int?val)?
???{?
??????index?=?index?+?1;?
?
??????while(index?<=?n)?
??????{?
?????????BITree[index]?+=?val;?
?????????index?+=?index?&?(-index);?
??????}?
??
???}?
????void?printBITree(int?arr[],?int?n)?{
????????for(int?i?=?0;?i??????????System.out.print(arr[i]?+?"?");
??????}
??????System.out.println();
???}
???void?constructBITree(int?arr[],?int?n)?
???{?
??????for(int?i=1;?i<=n;?i++)?
?????????BITree[i]?=?0;?
??????for(int?i?=?0;?i??????????updateBIT(n,?i,?arr[i]);?
?????????printBITree(BITree,n+1);
??????}
???}?
???public?static?void?main(String?args[])?
???{?
??????int?arr[]?=?{2,?1,?1,?3,?2,?3,?4,?5,?6,?7,?8,?9};?
??????int?n?=?arr.length;?
??????BinaryIndexedTree?tree?=?new?BinaryIndexedTree();?
??????//?從給定的數(shù)組?arr[],?構(gòu)造?BITree[]
??????tree.constructBITree(arr,?n);?
??????System.out.println("arr[0..5]?=?"?+?tree.getSum(5));?
??
??????//?測試更新操作
??????arr[3]?+=?6;?
??
??????//?arr[3]?的改變，更新?BITree[]
??????updateBIT(n,?3,?6);??
????????
????????System.out.println("arr[0..5]?=?"?+?tree.getSum(5));?
???}?
}?
來個(gè)直擊靈魂的三連！