- ChungZH 的博客
树状数组笔记
- 2022-8-20 10:26:28 @
欢迎访问我的博客:blog.chungzh.cn
早就学习过线段树了,但惭愧的是更简单的树状数组却一直没有深入理解过,仅仅停留在背代码的层级。今天认真学习一下树状数组。
引入
树状数组(Binary Index Tree, BIT / Fenwick Tree)支持单点修改和区间查询两种简单操作,时间复杂度均为 。它的实现比线段树简单,速度更快,但功能稍逊一筹。
原理
我们用 来表示 数组的一段区间,定义 的二进制表示中,最低位的 的位置为 ,那么用 代表 数组的下标区间 。举个例子,,$100_{(2)}-\operatorname{lowbit}(100_{(2)})+1_{(2)}=1_{(2)}=1_{(10)}$,那么 代表的区间就是 。通过这样的设计,树状数组将结点数压缩到与数组长度相同,不像线段树一样需要 个结点。
之所以会有这个特点,是因为对于位置 ,其对应的结点所在的高度就是 的位数。第一层结点为全体 ,即所有 的数字;第二层结点为全体 ,即所有 的数字;第三层结点为全体 ,即所有 的数字;以此类推。也就是说,对于位置 ,在这个位置往上垂直追溯,能追溯的层数就是 的二进制表示的末尾 数量。而结点高度又决定了其子树的大小,于是它所代表的信息区间大小也就一定是 。
*来源于参考资料 1
实现
如何计算呢?我们有这样一条公式:。在计算机中,有符号数采用补码表示。在补码表示下, 的相反数 -x = ~x + 1
,也就是按位非再加一。例如 的最后一个 的位置附近是 ,按位非之后是 ,加一再变成 ;而前面每一位都与原来相反。这时我们再把它和 按位与,得到的结果为 即 。
单点修改
修改操作类似于向上爬树的过程。例如我们要修改第三个元素,那么依次要修改 ,用二进制表示就是 ,发现下标 每次都要 ,直到到达顶部。
int add(int x, int y) {
while (x <= n) {
tree[x] += y;
x += lowbit(x);
}
}
区间查询(前缀和)
例如查询第六个元素的前缀和,即 这一区间。首先 表示的区间是 ,然后跳到 ,代表的区间是 ,加起来就 OK 了。从 到 是怎么跳的呢?实际上是 。所以下标 每次都要 ,直到 。
int query(int x) {
int sum = 0;
while (x) {
sum += tree[x];
x -= lowbit(x);
}
return sum;
}
至于求 这一区间的和,只需要分别求 和 再相减即可。
建树
暴力的建树方法是进行 次单点修改,时间复杂度为 。
有两种方法可以实现 建树。
前缀和
前面讲到 表示的区间是 ,那么我们可以先预处理一个 前缀和数组,再计算 数组。
void init() {
for (int i = 1; i <= n; ++i) {
C[i] = sum[i]-sum[i-lowbit(i)];
}
}
倒着贡献
我们很容易知道当前点 的父亲是 ,所以用自己的值更新父亲即可。
void init() {
for (int i = 1; i <= n; ++i) {
C[i] += a[i];
int j = i + lowbit(i);
if (j <= n) C[j] += C[i];
}
}