树状数组
用于以logn的时间内得到维护前缀和(区间和)
序列累和可以用一组子序列累和来表示,利用二进制拆分的思想
首先定义一些关键的数组符号:
f[i]
:原数组第i位的值
tree[i]
:树状数组定义的子序列和,这里代表某一序列的和
c[i]
: 代表从1到i的f[i]的和值(前缀和)
二进制拆分
给定一个整数如num=13,其二进制表示为1101
整数13的含义可以看做有一个长度为13的数组
如果我们希望得到c[13]的值,利用二进制拆分的思想,可以利用c[13]=(f[1]+...f[8]) + (f[9]+...+f[12]) + (f[13])
其中三个()内是被拆分后的子序列的和值
分别用二进制表示三个()内f数组的下标:
[0000+1,0000+1000]
[1000+1,1000+0100]
[1100+1,1100+0001]
设c[i]
某下标i的二进制表示为xxx1xxx
(x为1或0),1为当前需要考虑的位置(某位置为1则考虑,否则不考虑)
则其表示的子序列范围为:
[xxx0000+1,xxx0000+0001000]
或者说,c[i]
被分为的子序列有如下性质:
1. 子序列的基准量base = xxx0000
2. 子序列的偏移量offset = 0001000
3. 子序列的下界为 lower = base + 1
4. 子序列的上界为 upper = base + offset
5. 子序列包含的元素个数为 offset
现在逆序看待num=13(1101),从右往左数
第1位:被分出的子序列下标范围是[1100+1,1100+0001],二进制下:num-1
第3位:被分出的子序列下标范围是[1000+1,1000+0100],二进制下:num-100
第4位:被分出的子序列下标范围是[0000+1,0000+1000],二进制下:num-1000
上述过程结束后,num值为0,处理结束
上述过程中,每次取最右一位1可以这样表示 lowbit(x) = x&(-x)
tree数组的生成
通过上一章节可以看出如果逆序处理num=13这个数字,可以把c[13]分成三个子序列,其中每一个子序列范围都由lowbit()控制
现将lowbit()控制的范围转移到tree[]上
上述观察不难发现
lowbit(13) = 1, 13-1 = 12
lowbit(12) = 4, 12-4 = 8
lowbit(8) = 8, 8-8 = 0
直到13归零,无需再操作,因此c[13]
分成的三个子序列可以分别表示为tree[13]
,tree[12]
,tree[8]
换言之,tree[i]
表示的范围是f[i-lowbit(i)+1]+...+f[i]
这样 c[13] = tree[13] + tree[12] + tree[8]
由此完成了lowbit控制范围具体表现到tree中的值
在表示c[i]的时候,就可以直接用对应的tree[]来表示而不是f[],大大缩短了计算时间
在代码实现中
可以先求f[]
的初始前缀和,然后利用公式f[i-lowbit(i)+1]+...+f[i]
来计算tree[i]
的值
时间复杂度是O(N)
for(int i=1;i<=n;i++){
f[i] += f[i - 1];
tree[i] = f[i] - f[i - lowbit(i)];
}
查询
这里的查询指查询c[i]
如:c[i] = tree[i] + tree[i-lowbit(i)] + tree[i-lowbit(i)-lowbit(lowbit(i))]+...
上述过程可以用一个循环来表示
int sum(int i) {//表示求c[i]的值
int res = 0;
while (i > 0) {
res += tree[i];
i -= lowbit(i);
}
return res;
}
更新
这里的更新指更新f[i]
的值(将f[i]
加上或减去某个数),观察tree[]
数组的变化
更新可以看做查询的逆过程,简单来说,改变f[i]
,则要将tree[]
从i
下标开始一直更新到下标的上界n
原因:tree[i]
管辖[i-lowbit(i)+1,i]
这些位置,因此tree[i]
是第一个管辖f[i]
的元素,由此不断更新其他管辖上界的元素即可
代码如下:
void add(int i,int k) {//更新f[i]
while (i <= n) {
tree[i] += k;
i += lowbit(i);
}
}
文章参考
原文有图解,更容易理解,此篇文章单纯作为学习记录使用