树状数组

Vision271 · 2022-07-11 22:33:52 · 个人记录

概述

• 树状数组通过对原数组进行一定的基于二进制拆分求和的变换，高效地处理差分性问题。

操作

• 树状数组支持修改（ins）和查询前缀和（getsum）。

复杂度分析

• 单次操作复杂度 O(\log_2 n)，实际使用中可以认为是常数极小的 \log 级数据结构。

• 另外，从这里开始我们要讨论一点空间复杂度了（因为前面的数据结构都是线性数据结构）。不过树状数组的空间复杂度非常优秀，是 O(n) 的。

实现原理

• 定义 lowbit(x) 为 x 在二进制拆分下拆出的最小数，或者说其二进制表示下的最右边那个 1 的位权。

• 根据简单的原反补码知识，我们可以得到 lowbit(x)=x\And (-x)（取反后 +1 恰好与原数补码的 lowbit 相同，在补码意义同时也是二进制意义下的，不考虑正负）。

• 定义 former,a 分别为原数组和树状数组，则a_i=\sum\limits_{j=i-lowbit(i)+1}^i former_j。

• 即，a_i 等于从 i 开始（含）向左的长度为 lowbit(i) 的一段的和。

• 似乎这是到目前为止最不显然的一个结构。我们放一张图看看。为了作图方便，把 former 简写成 f。

• 不妨以 getsum(7) 为例。（参考下面的代码）能够看到，我们求的实际上是\sum a_4,a_6,a_7，是一种“斜向右下”的顺序。而其对应的原理实则是将 7 二进制拆分，一段一段地跳，每跳一段就把对应段的值加上。

• 这比普通前缀和有什么好处呢？查询复杂度不是反而升高了吗？想想数据结构的目的。前缀和是查询 O(1)，修改 O(n)；显然复杂度瓶颈在修改上。

• 我们考察一下树状数组的修改。尽管这个图是没有上界的，但是 n 是有限的。考虑修改 f_3处，可以看到，依赖 f_3 的只有 a[3],a[4],a[8]。好像不太妙啊，对不对？但在 n 很大的时候，我们可以把整个 add(pos) 分为两个阶段：

• 为什么有这么优秀的性质呢？其实上面的图就给出了答案。a 数组本质上是一棵根在右边的完全二叉树，至多有 \log_2 n 层，每次都会向上一层，自然是 O(\log)，且实际使用中往往是 ppc(k)，常数也很小。

• 类似地，getsum 操作也可以这样理解，每跳一次要加的区间都翻了倍，翻倍次数最多 O(\log)。

• 综上所述，树状数组正是以查询 O(\log_2 n) 为代价，换来了修改 O(\log_2 n)，均摊复杂度极大减小。

• 那为什么还要有线段树呢？因为它有一个绝对的缺陷——无法处理不可差分的问题。我们注意到，getsum 只能求前缀和！如果想要某一段的和，必须自己手动差分出来。从而，各种不满足差分性的操作，如区间求 max/min，第 k 大/小值等等都是不支持的。

• 那为什么还要有树状数组呢？

  • 1.快，快得不讲道理。虽然谈不上近线性时间，但也比别的 \log 级数据结构（点名线段树）快多了。用 build 来建的时候因为下标连续性速度还能进一步提高（这就是为什么不用 add 建树，虽然也就只能爽这一下了）。

  • 2.好写。满共 5 行，其中 build 还不必须。

  • 3.好调。这个的管辖范围是固定的，而线段树...很不友好。

• 另外一种理解是，将线段树每一层的相邻的左节点和右节点合并，然后定死按二进制的划分方式。

• 总之，这里给出示范代码。

il int lowbit(int x){return x&(-x);}
struct tree_array{
    int sum[maxn];
    il void ins(int k,int v){for(;k<=n;k+=lowbit(k)) sum[k]+=v; return;}
    il int get(int k){static int ret; ret=0; for(;k;k-=lowbit(k)) ret+=sum[k]; return ret;}
};

扩展

• 树状数组是可持久化的。但其实现原理是主席树，不实用。

• 树状数组可以参与树套树。

  • 二维树状数组：

    • 其本质是树状数组套树状数组（直接推广到二维，在两维上同时跑这种奇怪的二进制拆分的话，我推了一会发现好像不可行）。

    • 本质上还是贪常数和空间的东西，其实在这里一般空间更为重要，毕竟卡树套树的空间比卡它的时间容易不少（真被卡时了一般可以离线 CDQ 吧）。

  • 树状数组套主席树：

    • 参看“树套树”一节。

    • 这里的树状数组其实还是小常数...但不全是，因为树状数组的空间结构，可以少开很多棵主席树。

• 有些时候我们比较贪 ta 的小常数，希望用它来实现一些 sgt 的操作。

区间加，单点查

• 用树状数组维护差分数组。

前缀 min/max，单点查

• 这个东西挺吊诡的...它要把正常 ta 的操作反过来：插入时向前插入，查找时向后查找。

• 这个插入是字面意思的前缀 min/max，容易证明其恰好控制这个前缀区间。

• 查找的话，实质上是向后找所有包含我的地方打过什么前缀 min/max 的 tag。

例题

P4309 [TJOI2013] 最长上升子序列

• 题意略。我们拿这道题来谈一谈树状数组上二分。

• 首先显然有平衡树做法。令下标满足 bst 性，于是每次找到位置的过程也就知道了前缀 dp 最大值（把线段树维护 LIS 的从小到大插入法照搬过来），可以在线解决。

• 但是没事谁写平衡树啊。考虑离线它，显然可以 rope 或 vector，但是我们知道这俩玩意的复杂度是玄学...所以考虑一个正经一点的。

• 维护一个树状数组，一开始全都是 1。这不是说树状数组的每一位都是 1，是指对应的原数列是全 1，即进行 n 次 ins(i,1)。

• 接下来我们倒序考虑每一个插入操作。对每个操作，在树状数组上二分（倍增？），一开始 now=0，用倍增二分的方式试探着向右走，找够要在我前面的数字个数。把它插入到下一个位置上，并将对应位改成 0。

• 即，当我插入的时候，我插入到的是我的真实位置，因为以后插入到我前面的那些数，我都以为不存在，于是我总是相当于是最后一个插入的，故容易找到插入位置。

• 之后就再用一个树状数组跑一下 LIS 啦。