Part 1 我學它干啥？

樹狀數組，Binary Indexed Tree（簡稱BIT），是由Peter M. Fenwick在1994年發明的名字十分高大上，那么它是干什么的呢？

求和

求和是樹狀數組中的一個應用，并不是只能求和，本文使用求和作為例子。

現在有一個數組a，我們需要求很多次數組中不同區間的和，而且多次對a中隨意一項進行更改。

比如說a = {0， 1， 5， 3， 2， 4}

第一次求［1， 3］，得到1 + 5 + 3 = 9

第二次求［2， 4］，得到5 + 3 + 2 = 10

第三次，這時候我把a［2］ += 2

第四次求［1， 5］，得到1 + 7 + 3 + 2 + 4 = 17

［l， r］表示從下標l開始，到r結束的區間，包含l和r。

l： left

r： right

這時候很多同學想到的第一個方法，就是直接挨個加起來不就好了嗎？

可此題暗藏玄機，我們要進行多次求和啊，每一次都重新計算太慢，能不能提前加好一些區域，反復使用呢？

這就要請出我們的主角了——樹狀數組

Part 2 lowbit

樹狀數組的結構十分精妙，其中離不開一個基本運算——lowbit

lowbit（i） 可以解釋為：i中最低位的1以及后面的0；或者你可以把它理解成i能被n整除，n還可以寫成2k

一種lowbit的實現方式為lowbit（x） = x & -x

long long lowbit（long long x） {

return x & -x;

}

還是拿172舉例子，化成二進制后我們發現除了尾部的100相同之外，其他位都不同，使用按位與能得到lowbit的值

Part 3 樹狀數組

既然名字叫樹狀數組，那它必然是個數組，可外表下藏著二叉樹的結構。

精巧的結構與lowbit密不可分，真是妙極了。

以下內容中，我們在這里管原始的數組叫做a，樹狀數組（經過處理）叫做bit，三個圖中的數字均為下標，不是值！

結構

bit中存放了多個數的和，那么具體存了幾個，在哪里呢？

我們規定，bit［i］中存從右往左數lowbit（i）個數。

bit［i］ = 在數組a中從 i - lowbit（i） + 1 到 i 求和

更改單個數值

首先，更改數據可以轉換成加法，我們這里討論加法，和更改是一樣的。

挨個加起來時，更改a［i］只需要動它一個就可以了。

可是在樹狀數組中，可能有好幾項，都包括這個a［i］。

拿a［3］來舉例子吧。

bit［3］ 對應 a的［3， 3］ 的和

bit［4］ 對應 a的［1， 4］ 的和

bit［8］ 對應 a的［1， 8］ 的和

bit［16］ 對應 a的［1， 16］ 的和

以上四個bit中的值都需要更改

在圖中，我們可以看出，4在3頭上，8在4頭上，16在8頭上。我們只需要找到一種方式，得到一個塊 頭上的塊，然后使用循環能推出整串。

如何找到自己頭上的數呢？

圖中的6和橘色沒關系，是第二組例子

我們發現，在當前塊的位置加上當前塊的長度之后能跳到頭上。

我是這么理解的：加上一個當前塊后會把局部的空缺補上，合并成了一塊，而這塊也許也補了更大的空缺，這樣就一次跳了好幾級

上文定義規定了第i個塊長度 = lowbit（i），拿來用即可。

c++實現：

void add（int index， long long value） {

while （index 《= n） { // 更新直到最大的塊

node［index］ += value; // 更新當前的塊

index += lowbit（index）; // 加上一個自己的長度，補上空缺，得到下一個塊

}

}

區間求和

先考慮［1， r］的求和

從右往左取塊，將塊代表的數值加起來即可

圖中的例子：

第一次取到13，長度為lowbit（13） = 1

第二次13取完了從12開始取，長度為4，一次性將［9， 12］取完

第三次［9， 13］取完了從8開始，長度為8，取走［1， 8］，到此［1， 13］全部取走c++實現

long long sum（int index） {

long long sum = 0;

while （index 》 0） {

sum += node［index］;

index -= lowbit（index）;

}

return sum;

}

那如果求和左端點不在1處呢？

對［l， r］求和，可以寫成sum（r） - sum（l - 1）

先把大區域［1， r］求出來，然后扣掉［1， l - 1］的部分，不就是［l， r］嗎？

構造

以上的“幻想”只是存在于樹已經有了之后，如何根據數組a（原始數組），來構造一棵樹呢？

一個簡單的方法：

把數組bit全初始化為0

遍歷整個數組a

對于每一個數組a［i］，都對bit進行add（i， a［i］）每一次add之后都能保證樹狀數組是正確的，全加一遍后自然構建出一整棵樹。

時間復雜度對比

下面的暴力指的是開頭提到的挨個相加。

求和

暴力：O（n）（挨個相加，加n次）

樹狀數組：O（log n）（結構與二叉樹相仿）更改

暴力：O（1）（改一次即可）

樹狀數組：O（log n）（需要改一串，但結構與二叉樹相仿）構造

暴力：O（n）（當做是讀入的復雜度）

樹狀數組：O（n log n）（做n次加法，每次加法為log n）樹狀數組適合在：多次求和，多次修改，數據量大的場景下使用。

如果無需支持修改，建議使用前綴和，構造O（n），求和O（1）

代碼

下面給出的是C++代碼。

BITMain為樹狀數組的使用案例，對應洛谷 樹狀數組https://www.luogu.com.cn/problem/P3374。

//

// Created by Cat-shao on 2021/2/9.

//

#include 《cstdio》

#include 《cstring》

using namespace std;

const long long MAX_N = 5000100;

long long lowbit（long long x） {

return x & -x;

}

class BIT {

public：

long long node［MAX_N］， n;

BIT（int _n） {

memset（node， 0， sizeof（node））;

n = _n;

}

long long sum（int index） {

long long sum = 0;

while （index 》 0） {

sum += node［index］;

index -= lowbit（index）;

}

return sum;

}

void add（int index， long long value） {

while （index 《= n） {

node［index］ += value;

index += lowbit（index）;

}

}

};

int BITMain（）

{

// https://www.luogu.com.cn/problem/P3374

int n， m， op， x， y;

long long value;

scanf（“%d%d”， &n， &m）;

BIT tree = BIT（n）;

for （int i = 1; i 《= n; ++i） {

scanf（“%lld”， &value）;

tree.add（i， value）;

}

for （int i = 0; i 《 m; ++i） {

scanf（“%d%d%d”， &op， &x， &y）;

if （op == 1） {

tree.add（x， y）;

} else if （op == 2） {

printf（“%lld

”， （tree.sum（y） - tree.sum（x - 1）））;

}

}

return 0;

}

int main（）

{

BITMain（）;

}

文章來源： 程序員小灰

圖片來源：編程的最初夢想
責任編輯：lq6