漫畫：什么是樹狀數(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ù)壓縮。在算法競賽中，通常用于存儲(chǔ)頻率和處理累積頻率表。

首先考慮一個(gè)簡單的問題。

給定一個(gè)數(shù)組 arr[0 ... n-1] ，如何實(shí)現(xiàn)下面兩個(gè)操作：

1. 計(jì)算前 i 個(gè)元素的累加和；
2. 將數(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?之后
//?需要對存儲(chǔ)累加和的數(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è)就是以后會(huì)講到的線段樹（Segment Tree），另外一個(gè)就是樹狀數(shù)組 （Binary Indexed Tree），兩者均可以將上面所提到的查找和更新操作的時(shí)間復(fù)雜度降到 。但是與線段樹相比，樹狀數(shù)組的效率更高，并且易于實(shí)現(xiàn)。

樹狀數(shù)組表示為 BITree[]；樹狀數(shù)組的每個(gè)節(jié)點(diǎn)存儲(chǔ)輸入數(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[] 呢？

答案很簡單：

1. 首先將樹狀數(shù)組 BITree[] 的所有元素初始化為 0；
2. 調(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é)束啦！知道你沒啥感覺更是沒有體會(huì)到樹狀數(shù)組的妙用（我剛開始也是，說實(shí)話，笨笨的大禹看了好幾天）。

但是當(dāng)你將所有的步驟都都走完之后，你就會(huì)感覺不一樣啦！

圖中沒有填充的單元格都表示 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í)在不會(huì)也沒關(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)：

1. BITree[0] 是一個(gè)虛擬結(jié)點(diǎn)，同時(shí)也是我們所看到的根結(jié)點(diǎn)
2. BITree[y] 是 BITree[x] 的父結(jié)點(diǎn)，當(dāng)且僅當(dāng) y 可以通過從 x 的二進(jìn)制表示中刪除最后一個(gè)位置的 1 （也就是從右向左第一個(gè)） 來獲得，即 y = x - (x & (-x))
3. BITree[y] 的孩子結(jié)點(diǎn) BITree[x] 存儲(chǔ)的是數(shù)組 arr[] 中下標(biāo)從 y (包含) 到 x (不包含) 的累加和，即 arr[y,...,x) ,注意括號(hào)是不包含 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)兒清晰呢？很快你就會(huì)看到一句話概括上面所講的所有內(nèi)容。

回到我們最開始的兩個(gè)問題。

如何根據(jù) BITree[] ?樹狀數(shù)組，獲取數(shù)組 arr[] 中前 i 個(gè)元素的累加和？

這里更關(guān)鍵奧！！！

我們都知道，任何一個(gè)正整數(shù)都可以被表示為 2 的次冪和，比如 11 可以表示為 8 + 2 + 1. BITree的每個(gè)節(jié)點(diǎn)都存儲(chǔ) n 個(gè)元素的總和，其中 n 是 2 的次冪。比如前 11 個(gè)元素的累加和可以通過對原數(shù)組 arr[] 中最后 1 個(gè)元素（第11個(gè)元素）、向前兩個(gè)元素（第 9 和 10 號(hào)元素）和 前 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ù)為 量級(jí)，置位數(shù)就是一個(gè)整數(shù)二進(jìn)制表示中 1 的數(shù)目。因此，getSum() ?和 updateBIT() 兩個(gè)操作至多遍歷 個(gè)結(jié)點(diǎn)。

初始構(gòu)造樹狀數(shù)組 BITree[] 的時(shí)間復(fù)雜度為 ，構(gòu)造 BITree[] 樹狀數(shù)組會(huì)調(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));?
???}?
}?