浅谈树状数组

Lyzc0dr · 2025-09-28 18:41:59 · 算法·理论

Upd on 2025/10/11：删除了争议性前言。

Upd on 2025/10/13：删除末尾一些语句。

注：下文中的 c 数组即为树状数组，a 为原数组。

概念

完了有点忘了怎么办。

本质就是将一个长度为 n 的数组用特别的方法分成不超过 \log n 段区间，用这些区间的已知信息做合并来拼凑出询问的信息，大概长下面这个样子： 其中，被标成蓝色的点就是管辖了其子节点所有信息的点。

那么该怎么分每个节点管辖的信息呢？

这是被定义的，定义如下：

设 c_{k} 是树状数组中下标为 k 的节点，那么它管辖的区间就是原数组中 [k-k^{\prime}+1,k] 内的元素的信息，其中，k^{\prime} 是 lowbit(k)，而 lowbit(k) 的意思是 k 在二进制表示中最低位的 1 及其后面的所有 0 所构成的数值，比如 lowbit(5) 的计算方法就是先将 5 转化为二进制，为 (110)_{2}，然后取出右边开始第一个 1 及其右侧的所有 0 组成的数值，即 (10)_{2}，转化为十进制就是 2，在代码中，lowbit(x) 函数被实现为 x 与 -x 做 & 运算，具体为什么在此不多赘述，可以自行查询位运算相关知识。

基本用法

终于到了激动人心的基本用法讲解！

写在前面

首先，你要了解树状数组查询区间信息的本质——差分。

因此，普通的树状数组不能维护区间最大值等等不可差分的信息！

区间求和

注意：树状数组每次只能查询形如下标在 1 到 k 的区间前缀和，所以真正的区间和需要运用前缀和知识进行拼凑。

假设我们要查询区间 1 到 k 的前缀和（下文中设 lowbit(k) 为 p，且 p^{\prime} 等表述意为 k 在减去先前一个 p 之后的数做 lowbit 运算的值）。

首先，我们已经有了 c_{k}=\sum_{i = k-p+1}^{k}a_i，那么，为了继续找到我们所求答案的下一个部分，我们需要继续查询 \sum_{i=k-p-p^{\prime}+1}^{k-p} a_{i} 的值并累加到答案中，注意到这个值就是 c_{k-p}，那么以此类推，每次都用上述一样的思想就可以得出查询的方法是将 c_{k},c_{k-p},c_{k-p-p^{\prime}},c_{k-p-p^{\prime}-p^{\prime\prime}} 一直到 c_{1} 这些值全部相加，就拼凑了原数组中下标在 1 到 k 的和。

之后，在求出了 1 到 l-1 的和 s_{l-1} 与 1 到 r 的和 s_{r} 后，就可以根据前缀和的知识得知 l 到 r 的和为 s_{r}-s_{l-1}。

代码：

int Query(int x) {
    int ret=0;
    for(; x; x-=lb(x)) {
        ret+=c[x];
    }
    return ret;
}

单点修改

如果要修改 a_{x} 的值，那么就需要在 c 数组中更新所有管辖了 a_{x} 值的节点。

观察最初的图，可以发现 x 号有色节点的父节点编号是 x+p（p 为 lowbitx(x)），那么就可以通过不断从 x 往上“跳”，每次都跳到当前节点的父节点，更新跳到的每个节点即可。

代码：

void Modify(int x,int v) {
    for(; x<=m; x+=lb(x)) {
        c[x]+=v;
    }
}

Tips

注意，一般情况下，树状数组中的初值就是在原数组对应的位置存上对应的值！

练习

现在，你学习了树状数组的基本用法，那么，你就可以完成 P3374 了！

小进阶

1. 区间修改，单点查询

结合普通的差分数组，我们就可以实现区间修改，单点查询！

实现：

1. 求出原序列的查分数组 b，并将其按照下标作为键值存入树状数组。
2. 利用原本树状数组“单点修改”的特性与差分性质，修改 b_{l} 与 b_{r+1} 即可实现“区间修改”。
3. 利用原本树状数组“区间查询”的特征与差分性质——对差分数组求前缀和就可以获得原序列可得，查询的第 x 个数的值相当于求出 1 到 x 在树状数组上的和。

代码（存储初值）：

b[i] = a[i] - a[i - 1];
Modify(i, b[i]);

代码（修改）：

Modify(l, k);
Modify(r + 1, -k);

代码（查询）：

printf("%d\n", Query(x));

练习 2

接下来，完成 P3368 吧！

2. 区间修改，区间查询

其实当我们掌握了基本方法，做任意理论上可以实现的查询都可以通过“推式子”得出。

由上个部分的差分数组做考虑组合出答案。

首先，a_{i}=\sum_{j=1}^{i}b_{j}，那么：

那么这个式子可以分别维护左半部分和右半部分，开两个树状数组即可，一个存储普通的数值，一个存储 (i-1)\times b_{i}。

代码（存储）：

t1.add(i,b[i]);
t2.add(i,(i-1)*b[i]);

代码（修改）：

t1.add(x,k);
t1.add(y+1,-k);
t2.add(x,k*(x-1));
t2.add(y+1,-k*y);

代码（查询）：

ans+=y*t1.q(y);
ans-=(x-1)*t1.q(x-1);
ans-=t2.q(y);
ans+=t2.q(x-1);

练习 3

使用树状数组完成 P3372。

正经进阶

来点进阶的！

1. 权值树状数组

本质上，权值树状数组就是将原本用下标作为键值的树状数组改为了用一个数值作为下标！

他有什么用呢？

他可以相当于将树状数组变成一个“数轴”，因为使用值域作为下标，那么原本在一个位置加上一个数的操作就相当于在一条数轴上标记一个点。

值得注意的是，这种方法受空间限制（总不能开 10^{9} 大小的数组吧），所以通常搭配离散化来进行操作！

如果我们要统计一个数组中 a_{i} \leq a_{j} 的数量，我们该怎么做？

根据上文的描述，我们可以将这些值全部作为点存进“数轴中”，假设为下图。

其中，红色数字代表树状数组中的“下标”，蓝色的数字表示这个数字出现的次数，那么，如果我们想要统计比 6 小的元素有多少个，那么我们只需要求得“下标”在 [1,5] 间所有蓝色数的和即可，对应到树状数组上就是查询区间 [1,5] 的和，也就是 Query(5)，如果要查询比某个数大的元素个数，也只需要求得这个数右侧的下标对应的蓝色数的和即可。

代码（加点，其中求 rk 的部分是离散化后的结果）:

int rk=lower_bound(b+1,b+m+1)-b;
Modify(rk,1);

练习 4

好了，再结合离散化，你就可以完成：

1. SP32899（通常情况下，“加点”操作都要按照顺序一个一个来，不能一次性全部加进去，因为这样会导致对下标的要求混乱，比如你要求所有的 sum_{l} \leq sum_{r} 为了保证 l,r 的关系，你需要按照顺序加点）。
2. P1908（本题中因为逆序对也要求了下标的顺序，注意控制“加点”的顺序与查询的细节）。

2. 全局第 k 大值。

再次考虑权值树状数组。

问题相当于：在权值树状数组上找到一个 x，满足 1 到 x 的前缀和 \lt k，1 到 x+1 的前缀和 \geq k，那么，x+1 就是第 k 大值。

二分 x 结合权值树状数组查询即可，复杂度 O(\log^{2} n)，慢了。

考虑更高效的“跳”来找到 x。

想到倍增，从大到小枚举一个 i，记录一个变量 x 初始为 0，每次跳 2^{i} 步，尝试将 [x+1,x+2^{i}] 的前缀和加入一个初始为 0 的数 S 中，如果加入后 S \lt k，那么说明可以继续往后跳，将 x 更新为 x+2^{i}，依次类推，最后会找到最大的 x 使 S \lt k，那么 x+1 就是答案。

由于 [x+1,x+2^{i}] 的和其实就是 c_{x+2^{i}}，可以每次 O(1) 查询，于是这种方法的复杂度降至了 O(\log n)，优秀。

其次，修改操作只要在权值树状数组对应的映射上进行加减操作即可。

3. 二维树状数组

顾名思义，二维树状数组就是对一个矩阵进行操作的数据结构。

先给个代码感受下：

void add(int x, int y, int v) {
    for (int i=x; i <= n; i += lowbit(i)) {
        for (int j=y; j<=n; j += lowbit(j)) {
            c[i][j] += v;
        }
    }
}
int sum(int x,int y) {
    int ret=0;
    for(int i=x; i; i-=lowbit(i)) {
        for(int j=y; j; j-=lowbit(j)) {
            ret+=c[i][j];
        }
    }
    return ret;
}

具体讲解可以看作者的这篇题解。

习题 5

1. SP1029。
2. P4514。

后记

希望这篇专栏可以让你知道不一样的东西！