一文詳解什么是樹狀數(shù)組

Part 1 我學(xué)它干啥？

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

求和

求和是樹狀數(shù)組中的一個(gè)應(yīng)用，并不是只能求和，本文使用求和作為例子。

現(xiàn)在有一個(gè)數(shù)組a，我們需要求很多次數(shù)組中不同區(qū)間的和，而且多次對a中隨意一項(xiàng)進(jìn)行更改。

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

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

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

第三次，這時(shí)候我把a(bǔ)［2］ += 2

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

［l， r］表示從下標(biāo)l開始，到r結(jié)束的區(qū)間，包含l和r。

l： left

r： right

這時(shí)候很多同學(xué)想到的第一個(gè)方法，就是直接挨個(gè)加起來不就好了嗎？

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

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

Part 2 lowbit

樹狀數(shù)組的結(jié)構(gòu)十分精妙，其中離不開一個(gè)基本運(yùn)算——lowbit

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

一種lowbit的實(shí)現(xiàn)方式為lowbit（x） = x & -x

long long lowbit（long long x） {

return x & -x;

}

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

Part 3 樹狀數(shù)組

既然名字叫樹狀數(shù)組，那它必然是個(gè)數(shù)組，可外表下藏著二叉樹的結(jié)構(gòu)。

精巧的結(jié)構(gòu)與lowbit密不可分，真是妙極了。

以下內(nèi)容中，我們在這里管原始的數(shù)組叫做a，樹狀數(shù)組（經(jīng)過處理）叫做bit，三個(gè)圖中的數(shù)字均為下標(biāo)，不是值！

結(jié)構(gòu)

bit中存放了多個(gè)數(shù)的和，那么具體存了幾個(gè)，在哪里呢？

我們規(guī)定，bit［i］中存從右往左數(shù)lowbit（i）個(gè)數(shù)。

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

更改單個(gè)數(shù)值

首先，更改數(shù)據(jù)可以轉(zhuǎn)換成加法，我們這里討論加法，和更改是一樣的。

挨個(gè)加起來時(shí)，更改a［i］只需要?jiǎng)铀粋€(gè)就可以了。

可是在樹狀數(shù)組中，可能有好幾項(xiàng)，都包括這個(gè)a［i］。

拿a［3］來舉例子吧。

bit［3］ 對應(yīng) a的［3， 3］ 的和

bit［4］ 對應(yīng) a的［1， 4］ 的和

bit［8］ 對應(yīng) a的［1， 8］ 的和

bit［16］ 對應(yīng) a的［1， 16］ 的和

以上四個(gè)bit中的值都需要更改

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

如何找到自己頭上的數(shù)呢？

圖中的6和橘色沒關(guān)系，是第二組例子

我們發(fā)現(xiàn)，在當(dāng)前塊的位置加上當(dāng)前塊的長度之后能跳到頭上。

我是這么理解的：加上一個(gè)當(dāng)前塊后會(huì)把局部的空缺補(bǔ)上，合并成了一塊，而這塊也許也補(bǔ)了更大的空缺，這樣就一次跳了好幾級

上文定義規(guī)定了第i個(gè)塊長度 = lowbit（i），拿來用即可。

c++實(shí)現(xiàn)：

void add（int index， long long value） {

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

node［index］ += value; // 更新當(dāng)前的塊

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

}

}

區(qū)間求和

先考慮［1， r］的求和

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

圖中的例子：

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

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

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

long long sum（int index） {

long long sum = 0;

while （index 》 0） {

sum += node［index］;

index -= lowbit（index）;

}

return sum;

}

那如果求和左端點(diǎn)不在1處呢？

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

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

構(gòu)造

以上的“幻想”只是存在于樹已經(jīng)有了之后，如何根據(jù)數(shù)組a（原始數(shù)組），來構(gòu)造一棵樹呢？

一個(gè)簡單的方法：

把數(shù)組bit全初始化為0

遍歷整個(gè)數(shù)組a

對于每一個(gè)數(shù)組a［i］，都對bit進(jìn)行add（i， a［i］）每一次add之后都能保證樹狀數(shù)組是正確的，全加一遍后自然構(gòu)建出一整棵樹。

時(shí)間復(fù)雜度對比

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

求和

暴力：O（n）（挨個(gè)相加，加n次）

樹狀數(shù)組：O（log n）（結(jié)構(gòu)與二叉樹相仿）更改

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

樹狀數(shù)組：O（log n）（需要改一串，但結(jié)構(gòu)與二叉樹相仿）構(gòu)造

暴力：O（n）（當(dāng)做是讀入的復(fù)雜度）

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

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

代碼

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

BITMain為樹狀數(shù)組的使用案例，對應(yīng)洛谷 樹狀數(shù)組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（）;

}

文章來源： 程序員小灰

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