一种支持单点修改、区间查询非可减性信息的树状数组

· · 算法·理论

0 引入

注意到树状数组可以支持单点加、区间求和，但其做法是转化为前缀和的差。

如果遇到求区间最大值、区间 GCD 这类非可减性信息时，普通树状数组就很难胜任。

这时，人们往往会直接考虑线段树这个几乎万能的 DS。

而考虑到线段树的 4 倍空间、递归调用、大码量（好吧在现在还算好的），人们也尝试过对其进行一些优化，如著名的 zkw 线段树。

但是树状数组真的不能求区间最值吗？

1 尝试

其实已经有过 O(\log^2{n}) 的做法了：树状数组进阶。

但研究一下就会发现，这实际上就是分成 \log 段子区间后分别查询，且每段都是 O(\log{n}) 的时间，特别暴力。

有感觉这并不是树状树组的极限。

2 改进

2.1 分析

看一张借来的图@逆流之时：

其中实线为树状数组所维护的区间，虚线为剩下的区间。

Wow！这张图简直就是线段树（n=2^k 时）！

而我们知道，线段树是支持 O(\log{n}) 的区间最值的。

那我们把剩下的补出来不就好了吗？

将剩下的一些区间拎出来看看：

[2,2],[3,4],[5,8],[7,8],[9,16],[19,20]\dots

看着是有什么规律，但说不出来……

话说树状数组的构建与 lowbit 有关，那它的互补部分呢？

我们把它们写成左开右闭的形式：

(1,2],(2,4],(4,8],(6,8],(8,16],(18,20]\dots

发现了吧，互补区间 (l,r] 中 r=l+lowbit(l)。

这是和原区间 (l,r] 中 l=r-lowbit(r) 很相似的（好吧本来就是对称的）。

真是妙哉！

ps：其实互补区间和求后缀的树状数组就只有 \pm1 的差别。

2.2 构建

对于单点修改

我们直接上代码：

inline void upd(int x, const int &v) {
    //其中L是互补区间，R是原区间
    for (int l = x - 1; l; l -= lowbit(l)) cmax(L[l], v);
    //因为互补区间是(l,r]，所以l得是x-1
    for (int r = x; r < N; r += lowbit(r)) cmax(R[r], v);
}

简直和原来的代码一模一样。

证明：直接用对称性或看图易证 qwq。

对于区间最值

有一个很简单的想法：

这样能保证统计的区间都是合法的，但如何才能不重不漏呢？

考虑到原区间和互补区间都是左开右闭的，所以当 l=r 时刚好统计完全。

但如何保证操作过程中一定存在某个时刻 l=r 呢？

证明：考虑 l 和 r 二进制下最高的不相同位（公共前缀后一位），显然如果 l \ne r 则 l 的这位为 0，r 的这位为 1；

  1. 若 l 后面的位都为 0：则 r 会减到和 l 相等。
  2. 否则：r 会减到这位后面都为 0，l 会加到这位变为 1。

综上：一定存在某个时刻达到 l=r。

由此，给出代码：

inline int query(int l, int r) {
    int res = 0;
    if (--l) for (; l + lowbit(l) <= r; l += lowbit(l)) cmax(res, L[l]);
    //l==0时特判
    for (; l ^ r; r -= lowbit(r)) cmax(res, R[r]);
    //直到l==r
    return res;
}

3 完整实现

namespace BIT {
    int L[N], R[N];
#define lowbit(x) ((x) & -(x))
    inline void upd(int x, const int &v) {
        for (int l = x - 1; l; l -= lowbit(l)) cmax(L[l], v);
        for (int r = x; r < N; r += lowbit(r)) cmax(R[r], v);
    }
    inline int query(int l, int r) {
        int res = 0;
        if (--l) for (; l + lowbit(l) <= r; l += lowbit(l)) cmax(res, L[l]);
        for (; l ^ r; r -= lowbit(r)) cmax(res, R[r]);
        return res;
    }
}
using namespace BIT;

显然这是很短的。

4 与 zkw 线段树的比较

4.1 从结构上看

这种树状数组同样是自底向上构建的。

这样构建出的节点是与 zkw 线段树完全一样的。

两者的区别在于不同的标号方式。

构建 zkw 线段树时一般会将 n 补齐至 2 的整数幂，以形成完全二叉树的树型，而树的右半边显然有部分节点是冗余的。

而得益于树状数组独特的标号方式，我们可以只用恰好 2n 的节点，去掉了不必要的部分。

但注意到：《学习如何使用线段树》中有写法是不用补全的，这样两者就效果完全一样了。

4.2 从时间上看

由于上文提到，两者的结构是完全一样的。

考虑到两者使用时都没有冗余操作，因此两者的时间复杂度一定是相等的。

即修改 x 时花费 \log_2(x) 次操作。

4.3 综上

这个结构对 zkw 线段树并没有较大的优势，在线 \% zkw 线段树。

实测也证实了两者在常数上并没有大的区别。

然而 zkw 线段树还有许多更高级的使用，在这方面树状数组又受到其特殊标号方式的影响，较难做出拓展（至少目前没有）。

5 后记

这个算法被我用来优化 [NOIP2024T4] 树上查询，效果不错（至少没挂）。

话说有好多 \log^2 过的 qwq。

另：对于此结构的更多想法（如区间 tag 修改上的推广），欢迎交流！

感谢@ppip，@YamadaRyou的交流（\% 金勾）。

感谢审核，辛苦 : ) 。