InTheBloodHorse

数据结构与算法(7) 树状数组

字数统计: 846阅读时长: 3 min
2018/10/04 Share

什么是树状数组

树状数组(Binary Indexed Tree)——解决动态前缀和问题的数据结构。看到这个英文名就能知道他其中的奥秘了,Binary,思想就在于二进制。

前缀和询问 a[1] + a[2] + a[3] + a[4] + …… + a[n]
对于修改 a[i] 为O(1),查询为O(n)

原理

先看图:
树状数组.jpg
我们用 a代表原始数组,用t代表树状数组。

1
2
t[6] = a[5] + a[6]
110(二进制下) 2^1=2

1
2
t[8] = a[1] + a[2] + …… + a[8]
1000(二进制下) 2^3=8

同理我们就可以得到如下的算式(来自百度百科)
公式.jpg

这样可能有点太生硬,下面举个例子。

查询

现在我们要查找 14 的前缀和,暴力的话就是 从a[1]累加到a[14]。但是我们现在有了树状数组,我们的需要的答案就是t[14] + t[12] + t[8] ,这样复杂度就减少为 O(logn)了。或者再换一个例子我们要查找 11 的前缀和的话,只需要计算我们的 t[11] + t[10] + t[8]就可以了。
树状数组的实质在于二进制拆分,从最低位开始,遇到的1,记录数字,并抹掉这个1,直到所有的1都没了。
拿上面的 14 当做例子

1
2
3
111014) t[14] 管辖 2^1
110014) t[12] 2^2
100014) t[8] 2^3

修改

对于每一次修改,都要重新维护树状数组。
例如我们要修改 6 的值。我们也要修改覆盖6的值,比如t[8],t[16]。其实这就是一个查询倒过来的过程。

lowbit

用来返回二进制数最后一个1所在的位置

1
2
3
int lowbit(int x) {
return x & (-x);
}

lowbit是真的妙。因为计算机存储一个负数的时候,是用补码来表示的。
例如 在有位数的二进制中 -12(1 1100)的补码是(1 0100)然后对 1100 & 0100 得到 0100,然后原码(1100)-补码(0100) = 下一次查询的节点(1000)也就是8,然后对照图,12查询完了就是查询8了。
至于为什么 x & (-x)就可以得到最后一个1所在的位置,我们先忽略符号位。
例如 原码 10100 取反得到 01011,这样 & 运算,肯定得不到结果,因为每一位都是不同的,结果肯定是0,但是我们补码是在取反后 +1的,因为最后一个1的后面全是0,所以取反之后就是全是1,全是1 再+1,每次都进位,直到遇到0(这个0就是由原码里面最后一个1得到的,原码里面的1与我们进位后得到的1,结果是1,而后面的不受影响,因为都是不同的,所以这样我们就可以得到结果了)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;
int a[100005];//原数组
int t[100005];//树状数组
int n;
int lowbit(int x) {
return x & (-x);
}

// 查询 x的前缀和
int query(int x)
{
int ans=0;
while(x){
ans+=t[x];
x-=lowbit(x);
}
return ans;
}

// 在x位上加num
void add(int x,int num){
while(x<=n){
t[x]+=num;
x+=lowbit(x);
}
}
int main()
{
cin >> n;
for(int i=1;i<=n;i++){
cin >> a[i];
add(i,a[i]);
}
for(int i=1;i<=n;i++){
cout << query(i) << endl;
}
}

CATALOG
  1. 1. 什么是树状数组
  2. 2. 原理
    1. 2.1. 查询
    2. 2.2. 修改
    3. 2.3. lowbit