论树状数组的正确食用方式
2024-09-15 17:24:49
发布于：上海
消灭线段树大常数暴政，世界属于树状数组。
挑战赛考虑出数据结构题吗？（
Part 0 基础知识
- 一点点的数学知识。
- 位运算知识： 表示 的二进制表示下最低位的一（与其后面的所有零构成的数）。
lowbit(x) = x & (-x)。
等价于 。
Part 1 基本用法
Part 1.0 介绍
树状数组是一种支持单点修改和区间查询的高效数据结构。事实上，也可以通过一些进阶用法实现区间修改和单点查询，或者区间修改和区间查询，且渐进时空复杂度不会改变。
令当前树状数组的大小为 ，则单次修改或查询时间复杂度均为 。空间复杂度则恒为 。
一般的树状数组要求维护的信息满足结合律且存在逆运算。例如加法，模意义下的乘法（需保证逆元存在）等就满足上述条件，而类似于 ， 等不存在逆运算，就无法直接维护。（事实上这一类存在结合律而不存在逆运算的也可以用树状数组维护，但是时间复杂度会退化为 ，劣于线段树的 ，所以不作讨论。）
发现树状数组使用的条件（结合律，逆运算）是使用线段树（结合律）的充分不必要条件，而二者的时空复杂度严格相等，看起来线段树还更全能一些，树状数组显得优势不大。但是树状数组的优势在于：
- 时间常数小。树状数组只需要用
while循环迭代，而线段树需要进行复杂的递归过程。zkw 线段树消去了递归过程，但常数仍然较大。 - 空间常数小。树状数组只需要一倍空间，而线段树需要至少二倍空间，极端情况可能会达到树状数组的数倍。
- 编程复杂度低。树状数组只需要几次简单的迭代，代码长度只有十几行甚至更少；而线段树一般都需要数十上百行。
所以学习树状数组还是很有用的。
Part 1.1 引入
一个简单的问题：假如我想知道 的和，怎么算？
显然可以直接累加，需要将 个数都加一遍。
那么假如我知道了 ，， 这三段分别的和，还可以怎么求？
显然直接把这三段的和加起来即可，只需要计算 个数的和。
这便是树状数组的核心思想：将求 的结果拆分成不超过 个子问题，使得这些子问题的答案是已知的。 这也是运算需要满足结合律的原因。
令 为树状数组以下标 结尾掌管的一个区间（区间大小在下面给出）的和。例如我们有 个元素，树状数组 的结构是长这样的：
Part 1.2 区间查询
观察上图。发现 是 的和， 是 的和， 是 的和。因此 的和就是 。那么这个式子是我们肉眼发现的，有没有一般性的方法得到要把哪几个元素加起来呢？
首先，先考虑每一个索引掌管区间的长度如何确定。观察下表：
| 区间长度 | ||
|---|---|---|
| 1 | 1 | (0001) |
| 2 | 2 | (0010) |
| 3 | 1 | (0011) |
| 4 | 4 | (0100) |
| 5 | 1 | (0101) |
| 6 | 2 | (0110) |
| 7 | 1 | (0111) |
| 8 | 8 | (1000) |
| 9 | 1 | (1001) |
| 10 | 2 | (1010) |
| 11 | 1 | (1011) |
发现 掌管的区间长度为 （定义在 Part 0 给出）。因此得到结论： 就是为 的和。
知道了区间长度，接下来考虑查询。例如查找 的和：
- 包含了 区间。加入答案，跳到左端点的前一个 ，也就是 。
- 包含了 区间。加入答案，跳到左端点的前一个 ，也就是 。
- 包含了 区间。加入答案，跳到左端点的前一个 ，也就是 。
- 不存在，结束过程。
图：
有了上述思路，很容易用迭代实现查询 的和：
int query(int k){
int sum=0;
while(k){
sum+=c[k];
k&=k-1; // 等价于 k-=lowbit(k);
}
return sum;
}
求 的和，使用前缀和的思想，结果显然为 query(y)-query(x-1)。
时间复杂度正确性：每一次对 的修改都会去除 二进制下的一个 1。 的位数为 ，因此时间复杂度为 。
Part 1.3 单点修改
设要更改 的值。为了保证效率，我们只需要更改 及其所有直接或间接祖先。由于 包含于 （证明见后文），所以我们可以这样做：每一次修改后将索引自增其 ，直到索引超过范围。一个实现：
void add(int k,int x){
while(k<=n){
c[k]+=x;
k+=lowbit(k);
}
}
下说明 包含 。
令 ，，。
则 ，同时 管辖的左边界为 。容易得知 。取最小值，此时 管辖的左边界为 ，简单推一下后可得 管辖的左边界小于等于 管辖的左边界。
因为 管辖的左边界 管辖的左边界 ，所以 （即 ）包含 。证毕。
Part 1.4 初始化
一个显然的方式是 次单点修改，时间复杂度 。
当然还能做得更好。因为父亲的下标总是严格大于自己的下标，而父亲的值就是其所有直接儿子的子树加上自己得到的。所以我们从左往右遍历，逐个修改自己和直接父亲，将其加上自己的子树和就行了，有点类似于线段树建树的思想。时间复杂度 。注意判断越界。
void build(){
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
c[i]+=x;
if(i+lowbit(i)<=n)
c[i+lowbit(i)]+=c[i];
}
}
例题：【模板】树状数组 1
Part 2 维护一个差分数组
可以通过维护一个差分数组实现区间修改，单点查询。
咕咕咕
例题：【模板】树状数组 2
Part 3 维护两个树状数组
可以通过维护两个树状数组实现区间修改，区间查询。
例题：【模板】线段树 1
咕咕咕
有帮助，赞一个