学习笔记——树状数组（整合修改版）

一维树状数组

我学习的版本是这样的

区间修改：

我们假设sigma(r，i)表示r数组的前i项和，调用一次的复杂度是log2(i)

设原数组是a[n]，差分数组c[n]，c[i]=a[i]-a[i-1]，那么明显地a[i]=sigma(c,i)，如果想要修改a[i]到a[j](比如+v)，只需令c[i]+=v,c[j+1]-=v

区间查询：

在基于树状数组的基础操作：单点修改、区间查询上，我们可以这样操作

首先观察

a[1]+a[2]+...+a[n]

= (c[1]) + (c[1]+c[2]) + ... + (c[1]+c[2]+...+c[n])

= n*c[1] + (n-1)*c[2] +... +c[n]

= n * (c[1]+c[2]+...+c[n]) - (0*c[1]+1*c[2]+...+(n-1)*c[n]) (式子①)

那么我们就维护一个数组c2[n]，其中c2[i] = (i-1)*c[i]

每当修改c的时候，就同步修改一下c2，这样复杂度就不会改变

那么

式子①

=n*sigma(c,n) - sigma(c2,n)

于是我们做到了在O(logN)的时间内完成一次区间和查询

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#define N 3010
using namespace std;
int n,q,num[N],c1[N],c2[N];
inline int lowbit(int x){
    return (x&-x);
}
inline int add(int *r,int u,int del){
    for(int i=u;i<=n;i+=lowbit(i))
        r[i]+=del;
}
inline int sum_(int *r,int v){
    int sum=0;
    for(int i=v;i;i-=lowbit(i))    sum+=r[i];
    return sum;
        
}
inline void Jimmy(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%d",&num[i]);
        add(c1,i,num[i]-num[i-1]);
        add(c2,i,(i-1)*(num[i]-num[i-1]));
    }
    for(int i=1,type;i<=q;i++){
        scanf("%d",&type);
        if(type==1){
            int u,v;
            scanf("%d%d%d",&u,&v,&w);
            add(c1,u,w);add(c1,v+1,-w);
            add(c2,u,(u-1)*w);add(c2,v+1,v*(-w));
        }
        if(type==2){
            int u,v;
            scanf("%d%d",&u,&v);
            int sum1=(u-1)*sum_(c1,u-1)-sum_(c2,u-1); //sigma(u-1)
            int sum2=v*sum_(c1,v)-sum_(c2,v);    //sigma(v)
            printf("%d
",sum2-sum1);
        }
    }
}
int main(){
    Jimmy();
    return 0;
}

区间修改 区间查询

一维树状数组区间修改区间查询（1）

学完本来高高兴兴

然后一看二维树状数组

那我二维怎么把一个点差分成一个2维的i*j啊

然后就懵逼了

所以这种办法虽然是正确的，但是不利于推广

所以接下来介绍一下另一种可以推广的姿势的树状数组区间修改+区间查询的办法

然后，转载一篇dalao的博客 http://aireenye.leanote.com/post/BIT

orzAireen ，这种树状数组理解完一维就可以轻松推广到二维

#include<iostream>
#include<csdtlib>
#include<cstdio>
#include<algorithm>
#define N 3010
using namespace std;
struct Bit{
    int s[N];
    inline int lowbit(int x){
        return x&-x;
    }
    inline void add(int x,int del){
        if(!i) return;
        for(int i=x;i<=n;i+=lowbit(i))
            s[i]+=del;
    }
    inline int sum(int x){
        int ret=0;
        for(int i=x;i;i-=lowbit(i))
            ret+=s[i];
        return ret;
    }
};
struct bit{
    Bit a,ai;int s[N];
    inline void init(){
        for(int i=1;i<=n;i++)
            scanf("%d",&s[i]);
        for(int i=1;i<=n;i++)
            s[i]+=s[i-1];
    }
    inline void add(int l,int r,int del){
        a.add(l,del);a.add(r+1,-del);
        ai.add(l,del*l);ai.add(r+1,-del*(r+1));
    }
    inline void sum(int l,int r){
        return s[r]+a.sum(r)*(r+1)-ai.sum(r)-(s[l-1]+a.sum(l-1)*l-ai.sum(l-1));
    }
};
inline void Jimmy(){
}
int main(){
    Jimmy();
    return 0;
}

一维树状数组正确姿势

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
using namespace std;
struct Bit_2D{
    int s[N][N];
    inline int lowbit(int x){
        return x&-x;
    }
    inline void add(int x,int y,int del){
        for(int i=x;i<=n;i+=lowbit(x))
            for(int j=y;j<=n;j+=lowbit(x))
                s[i][j]+=del;
    }
    inline int sum(int x,int y,int del){
        int ret=0;
        for(int i=x;i;i-=lowbit(i))
            for(int j=y;j;j-=lowbit(j))
                ret+=s[i][j];
        return ret;
    }
}s;
struct bit_2D{
    Bit_2D a,ai,aj,aij;int s[N][N];
    inline void init(){
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                scanf("%d",&s[i][j]);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                s[i][j]+=s[i][j-1];
        for(int i=1;i<=n;i++)    
            for(int j=1;j<=n;j++)
                s[i][j]+=s[i-1][j];        
    }
    inline void Add(int x,int y,int del){
        a.add(x,y,del);ai.add(x,y,del*x);aj.add(x,y,del*y);aij.add(x,y,del*x*y);
    }
    inline void add(int x,int y,int del){
        Add(x,y,del);Add(x,y+1,-del);Add(x+1,y,-del);Add(x+1,y+1,del);
    }
    inline int Sum(int x,int y){
        return s[x][y]+a.sum(x,y)*(x+1)*(y+1)-ai.sum(x,y)*(y+1)-aj.sum(x,y)*(x+1)+aij.sum(x,y)*x*y;
    }
    inline int sum(int a,int b,int c,int d){
        return Sum(c,d)-Sum(a-1,d)-Sum(c,b-1)+Sum(a-1,b-1);
    } 
}s;
inline void Jimmy(){
}
int main(){
    Jimmy();
    return 0;
}

二维树状数组正确姿势

$Δ_{x}$ 表示区间 $[x, n]$ 的共同增量.
利用的差分的思想,对于区间 $[l, r]$ ,每次修改 $Δ_{l}, Δ_{r + 1}$ 即可.
这就解决了区间加的问题.

考虑求和, $a_{x} = a_{i}^{'} + \sum_{i = 1}^{x} Δ_{i}$
$\begin{aligned} s_{x} & = \sum_{i = 1}^{x} a_{i} \\ = \sum_{i = 1}^{x} a_{i}^{'} + \sum_{i = 1}^{x} (x - i + 1) Δ_{i} \\ = \sum_{i = 1}^{x} a_{i}^{'} + \sum_{i = 1}^{x} Δ_{i} \times (x + 1) - \sum_{i = 1}^{x} Δ_{i} \times i \end{aligned}$
所以只需维护 $Δ_{i}, Δ_{i} \times i$ 的前缀和即可.