专栏文章

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

ZZYLZPP
算法·理论参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miqwlfkr
此快照首次捕获于
2025/12/04 11:56
3 个月前
此快照最后确认于
2025/12/04 11:56
3 个月前
查看原文

0 引入

注意到树状数组可以支持单点加、区间求和，但其做法是转化为前缀和的差。
如果遇到求区间最大值、区间 GCD 这类非可减性信息时，普通树状数组就很难胜任。
这时，人们往往会直接考虑线段树这个几乎万能的 DS。
而考虑到线段树的 44 倍空间、递归调用、大码量（好吧在现在还算好的），人们也尝试过对其进行一些优化，如著名的 zkw 线段树。
但是树状数组真的不能求区间最值吗？

1 尝试

其实已经有过 O(log⁡2n)O(\log^2{n}) 的做法了：树状数组进阶。
但研究一下就会发现，这实际上就是分成 log⁡\log 段子区间后分别查询，且每段都是 O(log⁡n)O(\log{n}) 的时间，特别暴力。
有感觉这并不是树状树组的极限。

2 改进

2.1 分析

看一张借来的图@逆流之时：
BIT1
其中实线为树状数组所维护的区间，虚线为剩下的区间。
Wow！这张图简直就是线段树（n=2kn=2^k 时）！
而我们知道，线段树是支持 O(log⁡n)O(\log{n}) 的区间最值的。
那我们把剩下的补出来不就好了吗？
将剩下的一些区间拎出来看看：
[2,2],[3,4],[5,8],[7,8],[9,16],[19,20]…[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]…(1,2],(2,4],(4,8],(6,8],(8,16],(18,20]\dots
发现了吧，互补区间 (l,r](l,r] 中 r=l+lowbit(l)r=l+lowbit(l)。
这是和原区间 (l,r](l,r] 中 l=r−lowbit(r)l=r-lowbit(r) 很相似的（好吧本来就是对称的）。
真是妙哉！
ps：其实互补区间和求后缀的树状数组就只有 ±1\pm1 的差别。

2.2 构建

对于单点修改

我们直接上代码：
C
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);
}
简直和原来的代码一模一样。
证明：直接用对称性或看图易证 qwqqwq。

对于区间最值

有一个很简单的想法：
  • 首先 l−−l--。
  • ll 不断 +lowbit+lowbit，直到 l+lowbit(l)>rl+lowbit(l)>r。
  • rr 不断 −lowbit-lowbit，直到 r−lowbit(r)<lr-lowbit(r)<l。
这样能保证统计的区间都是合法的，但如何才能不重不漏呢？
考虑到原区间和互补区间都是左开右闭的，所以当 l=rl=r 时刚好统计完全。
但如何保证操作过程中一定存在某个时刻 l=rl=r 呢？
证明：考虑 ll 和 rr 二进制下最高的不相同位（公共前缀后一位），显然如果 l≠rl \ne r 则 ll 的这位为 00，rr 的这位为 11；
  1. 若 ll 后面的位都为 00：则 rr 会减到和 ll 相等。
  2. 否则：rr 会减到这位后面都为 00，ll 会加到这位变为 11。
综上：一定存在某个时刻达到 l=rl=r。
由此，给出代码：
C
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 完整实现

C
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 线段树时一般会将 nn 补齐至 22 的整数幂，以形成完全二叉树的树型，而树的右半边显然有部分节点是冗余的。
而得益于树状数组独特的标号方式，我们可以只用恰好 2n2n 的节点，去掉了不必要的部分。
但注意到：《学习如何使用线段树》中有写法是不用补全的，这样两者就效果完全一样了。

4.2 从时间上看

由于上文提到，两者的结构是完全一样的。
考虑到两者使用时都没有冗余操作，因此两者的时间复杂度一定是相等的。
即修改 xx 时花费 log⁡2(x)\log_2(x) 次操作。

4.3 综上

这个结构对 zkw 线段树并没有较大的优势，在线 %\% zkw 线段树。
实测也证实了两者在常数上并没有大的区别。
然而 zkw 线段树还有许多更高级的使用，在这方面树状数组又受到其特殊标号方式的影响，较难做出拓展（至少目前没有）。

5 后记

这个算法被我用来优化 [NOIP2024T4] 树上查询，效果不错（至少没挂）。
话说有好多 log⁡2\log^2 过的 qwqqwq。
另：对于此结构的更多想法（如区间 tag 修改上的推广），欢迎交流！
感谢@ppip，@YamadaRyou的交流（%\% 金勾）。
感谢审核，辛苦 : ) 。

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...