树状数组

树状数组用于维护和查询区间前缀和

二进制编码

树状数组时利用数的二进制特征进行检索的一种树状的结构

我们发现，圈里带数字的节点我们定义为 $t[x]$ ，一个节点上的 $t[x]$ 定义为其树下直练的子节点的和，例如 $t[8]=t[4]+t[6]+t[7]+a_8$

这样子我们就能把前缀和的查询控制在 $O(\log n)$ 了

考虑维护，我们发现当有一个 $a_i$ 改变时，需要改变的 $t[x]$ 就是 $a_i$ 的祖先节点，也就是 $O(\log n)$ 的复杂度

观察发现，查询操作实际上是每次去掉二进制下的最后一个 $1$，例如：$sum(7)=t[7]+t[6]+t[4]$，也就是 $sum((111)_2)=t[(111)_2]+t[(110)_2]+t[(100)_2]$

维护操作是每次在二进制的最后的 $1$ 加上 $1$

例如如果修改了 $a_3$，那么需要修改 $t[3],t[4],t[8]$，也就是 $t[(11)_2],t[(100)_2],t[(1000)_2]$

所以，树状数组的关键就是如何找到一个数的二进制的最后一个 $1$

我们利用负数的补码表示，可以得到二进制下的最后一个 $1$，也就是 $lowbit(x)=x\&-x$

例如 $6=(00000110)_2,\textnormal{-}6=(11111010)_2,6\&\textnormal{-}6=(00000010)_2=2$

惊奇的发现，$t[x]$ 数组所包括的元素个数与 $lowbit(x)$ 相等，也就是说，$t[x]$ 记录了 $(x-lowbit(x),x]$ 的元素之和

这样子利用了数的二进制下的一些特性就可以把查询优化到 $\log n$ 级别了

算法实现

单点修改+区间查询

我们很容易就能写出来

struct tree{
    int n;
    vector<int> c;
    tree(int n){this->n=n;c.assign(n+1,0);}
    void add(int x,int val){
        for(;x<=n;x+=x&-x)c[x]+=val;
    }
    int sum(int x){
        int ret=0;
        for(;x;x-=x&-x)ret+=c[x];
        return ret;
    }
}

区间修改+单点查询

我们利用前缀和的思想，如果想要在 $[L,R]$ 加上 $val$ 就在 $t[L]+=val,t[R+1]-=val$ ，然后求前缀和就是答案

区间修改+区间查询

这里只用一个树状数组是做不到了，我们需要差分数组+树状数组的深度结合

求区间和 $s(L,R)=s(1,R)-s(1,L-1)$ 问题转化为如何求 $s(1,k)$

定义 $D[x]$ 是 $a[x]$ 的差分数组，可得

$\begin{aligned} & a_1+a_2+\cdots +a_k\\ & =D_1+(D_1+D_2)+\cdots +(D_1+D_2+\cdots+D_k)\\ & =k D_1+(k-1)D_2+\cdots+(k-(k-1)) D_k\\ & =k(D_1+D_2+\cdots+D_k)-(0\cdot D_1+1D_2+2D_3+\cdots+(k-1)D_k)\\ &=k\sum\limits_{i=1}^k D_i+\sum\limits_{i=1}^k(i-1)\cdot D_i \end{aligned}$

就化简成了两个和式的形式，就可以用树状数组来处理了，一个实现 $D_i$ 一个实现 $(i-1)D_i$

tree t1(n),t2(n);
    vector<int> a(n+1,0);
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        int d=a[i]-a[i-1];
        t1.add_x(i,d);
        t2.add_x(i,(i-1)*d);
    }
    while(m--){
        int op;cin>>op;
        if(op==1){
            int L,R,d;cin>>L>>R>>d;
            t1.add_x(L,d);t1.add_x(R+1,-d);
            t2.add_x(L,(L-1)*d);t2.add_x(R+1,-(R+1-1)*d);
        }
        else{
            int L,R;cin>>L>>R;
            cout<<R*t1.get(R)-t2.get(R)-((L-1)*t1.get(L-1)-t2.get(L-1))<<'\n';
        }
    }

二维区间修改+区间查询

二维其实是一维的拓展，也是考虑构造差分数组 $D[i,j]=a[i,j]-a[i-1,j]-a[i,j-1]+a[i-1,j-1]$

然后需要查询 $\sum\limits_{i=a}^c \sum\limits_{i=b}^d a[i][j] =\sum\limits_{i=1}^c \sum\limits_{i=1}^d a[i][j]-\sum\limits_{i=1}^c \sum\limits_{i=1}^{b-1} a[i][j]-\sum\limits_{i=1}^{a-1} \sum\limits_{i=1}^d a[i][j]+\sum\limits_{i=1}^{a-1} \sum\limits_{i=1}^{b-1} a[i][j]$

所以问题就转化为如何求 $\sum\limits_{i=1}^n \sum\limits_{i=1}^m a[i][j]$，利用差分数组可得

$\begin{aligned} & \sum\limits_{i=1}^n \sum\limits_{i=1}^m a[i][j] \\ =& \sum\limits_{i=1}^n \sum\limits_{i=1}^m \sum\limits_{k=1}^i \sum\limits_{l=1}^j D[k][l]\\ =& \sum\limits_{i=1}^n \sum\limits_{i=1}^m D[i]j]\times(n-i+1)\times(m-j+1)\\ =& (n+1)(m+1)\sum\limits_{i=1}^n \sum\limits_{i=1}^m D[i][j] -(m+1) \sum\limits_{i=1}^n \sum\limits_{i=1}^m D[i][j]\times i-(n+1)\sum\limits_{i=1}^n \sum\limits_{i=1}^m D[i][j]\times j +\sum\limits_{i=1}^n \sum\limits_{i=1}^m D[i][j]\times i \times j \end{aligned}$

所以，我们只需要构造四个树状数组来维护 $D[i][j],D[i][j]\times i,D[i][j]\times j,D[i][j]\times i\times j$ 就好了

查询和求和的复杂度都为 $O(\log n \log m)$ 但缺点是占用空间大

区间最值

其实树状数组也可以解决区间最值问题

回到这个图，前缀和树状数组中，$t[x]$ 中存放的是 $(x-lowbit(x),x]$ 中每个数的和，那么在求最值的树状数组中就是记录的最大值

单点修改：$update(x,val)$ 我们需要修改 $t[x]$ 以及 $x$ 的祖先节点

如何修改，对于祖先节点，重新求一次 $max$ ，也就是扫一遍每个直接的儿子节点

void update(int x,int val){
        while(x<=n){
            c[x]=val;
            for(int i=1;i<lowbit(x);i<<=1)
                c[x]=max(c[x],c[x-i]);
            x+=lowbit(x);
        }
    }

区间最值查询：$query(L,R)$

• 如果 $R-L \ge lowbit(R)$ 那么 $[L,R]$ 区间包含了 $t[R]$ 所包含的所有结点，还多出来一块 $[L,R-lowbit(R)]$ 则 $query(L,R)=\max(t[R],query(L,R-lowbit(R))$

• 如果 $R-L \le lowbit(R)$ 那么 $[L,R]$ 区间在 $t[R]$ 所包含的区间内，则往前递推 $query(L,R)=\max(a[R],query(L,R-1))$

可以写成递推的形式

int query(int L,int R){
        int ans=0;
        while(L<=R){
            ans=max(ans,a[R]);R--;
            while(R-L>=lowbit(R)){
                ans=max(ans,c[R]);
                R-=lowbit(R);
            }
        }
        return ans;
    }

更新和查询的时间复杂度都为 $O((\log n)^2)$