树状数组维护区间和的模型及其拓广的简单总结

谁借莪１个温暖的怀抱￠ 2021-11-15 11:14 128阅读 0赞

by wyl8899

树状数组的基本知识已经被讲到烂了，我就不多说了，下面直接给出基本操作的代码。

假定原数组为a\[1..n\]，树状数组b\[1..n\]，考虑灵活性的需要，代码使用int \*a传数组。

#define lowbit(x) ((x)&(-(x)))
    
    int sum(int *a,int x){
    
      int s=0;
    
      for(;x;x-=lowbit(x))s+=a[x];
    
      return s;
    
    }
    
    void update(int *a,int x,int w){
    
      for(;x<=n;x+=lowbit(x))a[x]+=w;
    
    }

sum(x)返回原数组\[1,x\]的区间和，update(x,w)将原数组下标为x的数加上w。

这两个函数使用O(操作数\*logn)的时间和O(n)的空间完成单点加减，区间求和的功能。

接下来做一些升级，让树状数组完成区间加减，单点查询的功能。

直接做的话很困难，需要对问题做一些转化。

考虑将原数组差分，即令d\[i\]=a\[i\]-a\[i-1\]，特别地，d\[1\]=a\[1\]。

此时a\[i\]=d\[1\]+..+d\[i\]，所以单点查询a\[i\]实际上就是在求d数组的\[1..i\]区间和。

而区间\[l,r\]整体加上k的操作，可以简单地使用d\[l\]+=k和d\[r+1\]-=k来完成。

于是，我们用树状数组来维护d\[\]，就可以解决问题了。

下面再升级一次，完成区间加减，区间求和的功能。

仍然沿用d数组，考虑a数组\[1,x\]区间和的计算。d\[1\]被累加了x次，d\[2\]被累加了x-1次，...，d\[x\]被累加了1次。

因此得到

sigma(a\[i\])

=sigma\{d\[i\]\*(x-i+1)\}

=sigma\{  d\[i\]\*(x+1) \- d\[i\]\*i \}

=(x+1)\*sigma(d\[i\])-sigma(d\[i\]\*i)

所以我们再用树状数组维护一个数组d2\[i\]=d\[i\]\*i，即可完成任务。

POJ 3468就是这个功能的裸题，下面给出代码。

\[请注意我们上面的讨论都假定了a\[\]初始全是0。如果不是这样呢?下面的程序里给出了一个相对简便的处理办法。\]

// POJ 3468   Using BIT
    
    
    
    #include <cstdio>
    
    
    
    const int maxn=100010;
    
    __int64 a[maxn],b[maxn],c[maxn];
    
    int n,m;
    
    
    
      inline int lowbit(const int &x){
    
        return x&(-x);
    
      }
    
    
    
      __int64 query(__int64 *a,int x){
    
        __int64 sum=0;
    
        while(x){sum+=a[x];x-=lowbit(x);}
    
        return sum;
    
      }
    
     
    
      void update(__int64 *a,int x,__int64 w){
    
        while(x<=n){a[x]+=w;x+=lowbit(x);}
    
      }
    
     
    
    int main(){
    
      int l,r,i;
    
      __int64 ans,w;
    
      char ch;
    
      scanf("%d%d",&n,&m);
    
      a[0]=0;
    
      for(i=1;i<=n;++i){
    
        scanf("%I64d",&a[i]);
    
        a[i]+=a[i-1];
    
      }
    
      while(m--){
    
        scanf("%c",&ch);
    
        while(ch!='Q' && ch!='C')scanf("%c",&ch);
    
        if(ch=='Q'){
    
          scanf("%d%d",&l,&r);
    
          ans=a[r]-a[l-1]+(r+1)*query(b,r)-l*query(b,l-1)-query(c,r)+query(c,l-1);
    
          printf("%I64d\n",ans);
    
        }else{
    
          scanf("%d%d%I64d",&l,&r,&w);
    
          update(b,l,w);
    
          update(b,r+1,-w);
    
          update(c,l,w*l);
    
          update(c,r+1,-(r+1)*w);
    
        }
    
      }
    
      return 0;
    
    }

\[当a\[\]初始不全0的时候，我们就只维护后来加上去的部分，查询区间和的时候再补上初始的时候这一段的区间和就可以了。\]

======================一维到二维的分割线=========================

接下来到二维树状数组。

先看看sum和update变成什么样子了吧。

inline int gs(int a[maxn][maxn],int x,int y){
    
      int s=0,t;
    
      for(;x;x-=lowbit(x))
    
        for(t=y;t;t-=lowbit(t))
    
          s+=a[x][t];
    
      return s;
    
    }
    
    inline void gp(int a[maxn][maxn],int x,int y,int w){
    
      int t;
    
      for(;x<=n;x+=lowbit(x))
    
        for(t=y;t<=m;t+=lowbit(t))
    
          a[x][t]+=w;
    
    }

gs就是sum，gp就是update，由于需要多次调用的缘故，改成了更短的名字。

单点加减，矩形求和并不难，直接用上面的两段就行了。

需要注意的是矩形的求和怎么求。上面的代码返回的是(1,1)-(x,y)矩形的和。

那么(x1,y1)-(x2,y2)的矩形和由下式给出：

sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1)

画个图就很好理解了。

对于涉及矩形加减的情形，我们发现一维中的差分的办法在二维的情况用不出来，所以要改一下。思考一下一维中的差分的另外一个含义：d\[i\]同时也表示d\[i..n\]的整体增量，d\[i\]+=k就意味着把d\[i\]..d\[n\]全部加上了k。理解了之后就发现这个意义上可以推广到二维，仍假设原矩形初始全为0，以便接下来的叙述。

令a\[x,y\]表示(x,y)-(n,m)矩形的整体增量，其中(n,m)是边界。

那么(x1,y1)-(x2,y2)矩形整体加k的代码就是

gp(a,x1,y1,w); gp(a,x2+1,y1,-w);gp(a,x1,y2+1,-w); gp(a,x2+1,y2+1,w);

仍然是建议画个图来帮助理解。

至此，矩形加减，单点查询的问题得到了解决。

重头戏在这里，矩形加减，矩形求和。

求原矩形(1,1)-(x,y)的和，结果由下式给出

sigma(i=1..x,j=1..y) a\[i,j\]\*(x-i+1)\*(y-j+1)

很好理解吧? 但是这个式子并不是那么容易求和的，展开一下求和的部分得到

a\[i,j\]\* ( (x+1)(y+1) \- (x+1)\*j \- (y+1)\*x \+ i\*j )

整个式子就是

(x+1)(y+1)sigma(a\[i,j\]) \- (x+1)sigma(a\[i,j\]\*j) \- (y+1)sigma(a\[i,j\]\*i) \+ sigma(a\[i,j\]\*i\*j)

知道怎么处理了吧？如果没有请回去复习一维的处理方法。

令b\[i,j\]=a\[i,j\]\*i c\[i,j\]=a\[i,j\]\*j d\[i,j\]=a\[i,j\]\*i\*j

维护a,b,c,d一共四个二维树状数组，问题得到解决。

tyvj p1716就是实现这两个功能的裸题，下面给出完整代码。

// tyvj p1716  using 2D BIT
    
    #include<cstdio>
    
    #include<cstring>
    
    #define lowbit(x) ((x)&(-(x)))
    
    const int maxn=2049;
    
    int a[maxn][maxn],b[maxn][maxn],c[maxn][maxn],d[maxn][maxn];
    
    int n,m;
    
    
    
      inline int gs(int a[maxn][maxn],int x,int y){
    
        int s=0,t;
    
        for(;x;x-=lowbit(x))
    
          for(t=y;t;t-=lowbit(t))
    
            s+=a[x][t];
    
        return s;
    
      }
    
      inline void gp(int a[maxn][maxn],int x,int y,int w){
    
        int t;
    
        for(;x<=n;x+=lowbit(x))
    
          for(t=y;t<=m;t+=lowbit(t))
    
            a[x][t]+=w;
    
      }
    
      inline int sum(int x,int y){
    
        return (x+1)*(y+1)*gs(a,x,y)-(y+1)*gs(b,x,y)-(x+1)*gs(c,x,y)+gs(d,x,y);
    
      }
    
      inline void update(int x1,int y1,int x2,int y2,int w){
    
        gp(a,x1,y1,w); gp(a,x2+1,y1,-w);
    
        gp(a,x1,y2+1,-w); gp(a,x2+1,y2+1,w);
    
        gp(b,x1,y1,w*x1); gp(b,x2+1,y1,-w*(x2+1));
    
        gp(b,x1,y2+1,-w*x1); gp(b,x2+1,y2+1,w*(x2+1));
    
        gp(c,x1,y1,w*y1); gp(c,x2+1,y1,-w*y1);
    
        gp(c,x1,y2+1,-w*(y2+1)); gp(c,x2+1,y2+1,w*(y2+1));
    
        gp(d,x1,y1,w*x1*y1); gp(d,x2+1,y1,-w*(x2+1)*y1);
    
        gp(d,x1,y2+1,-w*x1*(y2+1)); gp(d,x2+1,y2+1,w*(x2+1)*(y2+1));
    
      }
    
    
    
    int main(){
    
      int x1,y1,x2,y2,w;
    
      char ch;
    
      scanf("%c",&ch);
    
      while(ch!='X')scanf("%c",&ch);
    
      scanf("%d%d\n",&n,&m);
    
      memset(a,0,sizeof(a));
    
      memset(b,0,sizeof(b));
    
      memset(c,0,sizeof(c));
    
      memset(d,0,sizeof(d));
    
      while(scanf("%c",&ch)!=EOF){
    
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    
        if(ch=='L'){
    
          scanf("%d\n",&w);
    
          update(x1,y1,x2,y2,w);
    
        }else{
    
          scanf("\n");
    
          printf("%d\n",sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1));
    
        }
    
      }
    
      return 0;
    
    }

wy18899

没原文链接，只能写个原创，但是不是我写的