Basic Concept
树状数组可以用于高效计算数列的前缀和,区间和等等。
它可以支持在$O(logn)$的时间内得到任意前缀和,以及在$O(logn)$时间内支持对区间单点值的修改。空间复杂度为$O(n)$。
数组存储方式
如图所示。
$A[i]$代表原数组的元素,$C[i]$代表树状数组中的元素。
C[1]=A[1];
C[2]=A[1]+A[2];
C[3]=A[3];
C[4]=A[1]+A[2]+A[3]+A[4];
C[5]=A[5];
C[6]=A[5]+A[6];
C[7]=A[7];
C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];
而其索引的二进制表示如下:
C[1] = C[0001] = A[1];
C[2] = C[0010] = A[1]+A[2];
C[3] = C[0011] = A[3];
C[4] = C[0100] = A[1]+A[2]+A[3]+A[4];
C[5] = C[0101] = A[5];
C[6] = C[0110] = A[5]+A[6];
C[7] = C[0111] = A[7];
C[8] = C[1000] = A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];
我们可以找出规律,
也就是说,问题在于如何找出$i$的最低位$1$所代表的数值。
lowbit
这里我们可以引入lowbit
函数。
int lowbit (int x)
{
return x & (-x);
}
我们已经知道,对于整数表示,有
正数的补码是其本身;
负数的补码是在反码的基础上$+1$;
因此x & (-x)
就可以满足我们对于查找最低位$1$的需求。
举个例子:
- 二进制数 $11010$ (1)
其反码为 $00101$ (2)
加 $1$ 后为 $00110$ (3)
- 将(1)(3)两者相与便得到最低位的 $1$ 所表示的数值
树状数组的建立
上面准备工作都做好了,码就行了:(
#include <iostream>
#define MAXN 12
using namespace std;
int ft[MAXN+1] = {0};
int a[MAXN + 1] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
int lowbit(int x){
return x & (-x);
}
void generateTree(){
for (int i = 1; i <= MAXN; i++){
for (int k = i - lowbit(i) + 1; k <= i; k++)
ft[i] += a[k];
}
}
int main(){
generateTree();
return 0;
}
单点更新
再把这张图拿过来:
如果我们要更改$A[3]$的值,那么我们知道,$C[3], C[4], C[8]$ 的值都会受到影响。
- $3(011)$ =>
C[3] += temp;
- $lowbit(3) = 001$, $3 + lowbit(3)= 100 = 4(100)$ =>
C[4] += temp;
- $lowbit(4) = 100$, $4+lowbit(4)=1000=8(1000)$ =>
C[8] += temp;
- ……
因此,我们只需要对所要更新的数据不断使其自增lowbit后,
使树状数组的对应索引增加 temp 值即可。
void update(int index, int val){
for (int i = index; i <= MAXN; i = i + lowbit(i)){
ft[i] += val;
}
}
区间查询
假设现在我们要查询1~7的前缀和。
C[7] = C[0111] = A[7];
C[6] = C[0110] = A[5] + A[6];
C[4] = C[0100] = A[1] + A[2] + A[3] + A[4];
归纳可知,我们只需每次将索引减少i的lowbit,然后将对应的树状数组的值求和即可。
int getSum(int index){
int result = 0;
for (int k = index; k > 0; k-=lowbit(k)){
result += ft[k];
}
return result;
}