树状数组

_RainCappuccino_ · 2023-04-28 13:52:14 · 个人记录

树状数组的用处

快速求和+快速修改，可以理解为动态前缀和

建立

这就是树状数组能快速求解信息的原因：我们总能将一段前缀 [1, n] 拆成 不多于 \boldsymbol{\log n} 段区间，使得这 \log n 段区间的信息是 已知的。

于是，我们只需合并这 \log n 段区间的信息，就可以得到答案。相比于原来直接合并 n 个信息，效率有了很大的提高。

不难发现信息必须满足结合律，否则就不能像上面这样合并了。

树状数组的工作原理

对于树状数组每一个元素c_i

以下式子成立：

int lowbit(int x){
    return x&(-x);
}

查询

从 c[x] 开始往前跳，有 c[x] 管辖 a[x-\operatorname{lowbit}(x)+1 \ldots x]； 令 x \gets x - \operatorname{lowbit}(x)，如果 x = 0 说明已经跳到尽头了，终止循环；否则回到第一步。 将跳到的 c_x 合并,即为[1,x]的区间和。

int getsum(int x){
    int sum=0;
    for(int i=x;i>0;i-=lowbit(i)) sum+=c[i];
    return sum;
}

修改

管辖 a[x] 的 c[y] 一定包含 c[x]，所以 y 在树状数组树形态上是 x 的祖先。因此我们从 x 开始不断跳父亲，直到跳得超过了原数组长度为止。

设 n 表示 a 的大小，不难写出单点修改 a[x] 的过程：

初始令 x' = x。 修改 c[x']。 令 x' \gets x' + \operatorname{lowbit}(x')，如果 x' > n 说明已经跳到尽头了，终止循环；否则回到第二步。

实现

void modify(int x,int d){
    for(int i=x;i<=n;i+=lowbit(i)){
        c[i]+=d;
    }
}

例题

P3374 【模板】树状数组 1

P3368 【模板】树状数组 2(维护差分)