树状数组合集

zzx0102 · 2023-11-19 13:08:54 · 算法·理论

声明一下：这里没有可持久化树状数组是因为我太菜，而不是做不了，想看的可以去看最后一篇参考资料。

我永远喜欢树状数组。

前置知识：线段树。

1. 基础树状数组：

引入问题：P3374 【模板】树状数组 1

显然如果直接暴力一定会 T，考虑优化。

考虑将这些区间拆分成更少的区间数，再对区间暴力求和，就可以起到优化的作用。

于是考虑任何一个数 x 在二进制下均只有 \mathcal{O}(\log x) 位为 1。

于是，我们考虑将 [1,x] 这个区间拆分成 \mathcal{O}(\log x) 个区间的和。

令 x=2^{d_1}+2^{d_2}+\cdots +2^{d_k}，且 \forall i\in[2,k],d_i>d_{i-1}，设 s_i=s_{i-1}+2^{d_i},s_0=0，则 [1,x] 被我们拆分成了 \bigcup\limits_{i=1}^k(s_{i-1},s_i]。

例：当 x=15 时，x=(1111)_2，即 [1,x]=(0,8]\cup(9,12]\cup(12,14]\cup(14,15]。

我们用 \operatorname{lbt}(x) 表示 \operatorname{lowbit}(x)，指 x 在二进制中最低位的 1 的值，即当 x=2^{d_1}+2^{d_2}+\cdots 2^{d_k} 时，\operatorname{lbt}(x)=2^{\min\limits_{i=1}^k d_i}。

所以一般的树状数组大致长这样：

考虑这样分有一个性质：对于每一个区间的右端点 r，都只对应一个 l。

首先，根据我们的拆分规则，r=l+2^x，并且 x=\log_2\operatorname{lbt}(r)，所以 l=r-\operatorname{lbt}(r)。

所以一共有 n 个不同的子区间。

接下来快速维护 n 个子区间。

由于 n 个区间的右端点各不相同，所以每个区间的区间和可以标记在右端点的位置上。考虑建立一个数组 tr，则 tr_x 表示以 x 为右端点的子区间的和。即

其中 a_x 表示单点值。

接下来考虑如何修改和查询。

查询显然直接每次将 x 减去 \operatorname{lbt}(x)，每次累加 tr_x，直至 0 就完事了，复杂度 \mathcal{O(\log x)}。

考虑如何修改。

修改其实也不难，考虑修改 x 即将所有包含 x 的区间都求出来。

考虑 tr_{x+\operatorname{lbt}(x)} 这个区间包含 x。

然后 tr_{x+\operatorname{lbt}(x)+\operatorname{lbt}(x+\operatorname{lbt}(x))} 包含 x+\operatorname{lbt}(x)，也包含 x。

所以每次将 x 加上 \operatorname{lbt}(x)，一直到 n 即可。

到了这里，已经可以写出修改和查询的代码了。

void chg(int x, int k) {for(; x <= n; x += lbt(x)) tr[x] += k;}
int ask(int x) {int sum = 0; for(; x; x -= lbt(x)) sum += tr[x]; return sum;}

这里有一个常数优化，可以使树状数组查询常数变小。

考虑查 [l,r] 的区间和，那么可以用前缀和的方式去求，这当中会有一些重复计算。忽略这些重复计算即可优化。

int ask(int l, int r){
    l--; int sum = 0;
    while(r > l) sum += a[r], r -= lbt(r);
    while(l > r) sum -= a[l], l -= lbt(l);
    return sum;
}

大约快了一倍。

于是考虑如何求 \operatorname{lbt}(x)。

这个总不能 \mathcal{O}(\log n) 枚举，不然复杂度会多一个 \log。

当然您可以考虑预处理 \forall i\in[1,n],\operatorname{lbt}(i)，不过这样就显得有些没有技术含量，而且会使树状数组常数增大。

计算机用补码存储和表示数值。考虑 -x（x > 0）的补码，它等于 x 的反码 +1。设 \mathrm{lbt}(x) = 2 ^ k，我们发现 -x 的补码在低 k - 1 位（第 0\sim k - 1 位）都是 0；在第 k 位和 x 相同，均为 1；在高于 k 的位和 x 相反。

例如，对于二进制数 (0\cdots 010100)_2，其 \operatorname{lowbit} 值为 4，其反码为 (1\cdots 101011)_2，相反数的补码为 (1\cdots 101100)_2。又因为正数的补码就是它本身，所以一个数的 \operatorname{lowbit} 值就等于它和它的相反数的按位与，即 x & -x。

P3374 CODE

接下来，考虑如何用树状数组维护区间加区间和。

这里使用差分。设差分数组为 d，原数组为 a。则

区间查询即

考虑计算贡献，得原式为

考虑用两个树状数组维护 d_i 以及 d_i\times i 的前缀和，直接计算即可。

P3372 CODE

二维树状数组：

在以为数组上直接加一维即可。

注意这里加入和修改传入的第二维变量不能直接作为循环变量，否则第二次循环时这个变量被永久改变了，就只能修改第一行。

那么如何处理矩形加矩形和的问题呢？

考虑直接将上面的差分沿用过来即可，维护四个树状数组，分别表示 d_{i,j},d_{i,j}\times i,d_{i,j}\times j,d_{i,j}\times i\times j。

P4514 CODE

树状数组也可以 \mathcal{O}(n) 建树，就是利用类似于 DP 的思想刷新后面的。

for(int i = 1; i <= n; i++) if(i + lbt(i) <= n) tr[i + lbt(i)] += a[i];

2.权值树状数组及其进阶

考虑维护一个数据结构：

1. 插入 x 数
2. 删除 x 数（若有多个相同的数，应只删除一个）
3. 查询 x 数的排名（排名定义为比当前数小的数的个数 +1 )
4. 查询排名为 x 的数
5. 求 x 的前驱（前驱定义为小于 x，且最大的数）
6. 求 x 的后继（后继定义为大于 x，且最小的数）

离散化后值域为 [1,n]。

考虑维护一个树状数组去解决。

我们令这个桶叫作 t。

加入一个数：即 t_x\gets t_x+1。

删除一个数：即 t_x\gets t_x-1。

查询排名：\sum\limits_{i=1}^{x-1}t_i+1 即为答案。

查询排名为 x 的数：

令 x 的排名为 f(x)

考虑求 \max\limits_{f(k)\le x}k 即为所求答案，得

看上去可以二分，但是这样复杂度变成 \mathcal{O}(n\log^2 n)，不太行。

考虑在树状数组上倍增，令当前位置是 p，和是 s。

考虑不断将 p 往后跳，如果跳过去排名仍然小于 x 就直接跳，否则就啥都不干。

举个例子，比如目前加入了 8 个数 \{1,2,3,4,5,6,7,8\}，并且 p=0,s=0。

则树状数组 tr=\{1,2,1,4,1,2,1,8\}，查询排名为 5 的数。

考虑将 p 向后跳 2^3 到 p=8 处，则 s\gets s+tr_p=0+8>5，不行。

接下来将 p 向后跳 2^2 到 p=4 处，则 s\gets s+tr_p=0+4<5，可行，此时 p=4,s=4。

然后将 p 向后跳 2^1 到 p=6 处，则 s\gets s+tr_p=4+2>5，不可行。

最后将 p 向后跳 2^0 到 p=5 处，则 s\gets s+tr_p=4+1=5，不可行。

所以最后答案为 p+1=5。

前驱和后继可以用操作 1,2,3,4 组合一下求出。

总复杂度 \mathcal{O(n\log n)}。

P3369 CODE

您也可以用类似的方法实现 区间 MEX 问题。

考虑直接对整个序列像 HH 的项链那样直接扫描线，然后同样在树状数组上倍增。

不过这个树状数组不属于本文讲的权值树状数组。

练习：P3224 [HNOI2012] 永无乡

这里介绍一下树状数组合并。

考虑用 pbds 哈希表实现动态开点树状数组。

由于树状数组具有可以整体相加的性质，所以合并两棵树状数组时，直接将这两个哈希表启发式合并一下即可。

启发式合并是指合并两个数据结构时，把少的合并到多的上，考虑每一个元素，它每被合并一次，所在堆的大小至少是原来的两倍。

这里每个节点合并最多合并 \log n 次，总共 n\log w 个节点，所以复杂度 \mathcal{O(n\log w\log n)}，第 y 小可以使用权值树状数组解决。

P3224 CODE

习题：P9176 [COCI2022-2023#4] Vrsta

这种水题大家一定都会，这里不做介绍。

权值树状数组其实也是可以实现树套树的。

考虑我们已经写好了动态开点树状数组。

由于两棵树状数组满足整体加减的性质，所以将一般的权值线段树换成权值树状数组即可。复杂度 \mathcal{O}(n\log ^2 n)。

P3380 CODE

3. 树状数组维护不可差分信息