二维树状数组

BZOJ3132

#include <cstdio>
#include <iostream>
#define LL int
using namespace std;
 
  int n,m;
  LL tr1[2052][2052],tr2[2052][2052],tr3[2052][2052],tr4[2052][2052];
  char st[11];
 
  int lowbit(int x){
    return(x&(-x));
  }
 
  void ed(LL tr[][2052],int x,int y,LL num){
    for (int i=x;i<=n+1;i+=lowbit(i))
      for (int j=y;j<=n+1;j+=lowbit(j))
        tr[i][j]+=num;
  }
   
  LL que(LL tr[][2052],int x,int y){
    LL ret=0;
    for (int i=x;i;i-=lowbit(i))
      for (int j=y;j;j-=lowbit(j))
        ret+=tr[i][j];
    return(ret);
  }
 
  void edi(LL x,LL y,LL num){
    ed(tr1,x,y,num);
    ed(tr2,x,y,x*num);
    ed(tr3,x,y,y*num);
    ed(tr4,x,y,x*y*num);
  }
   
  LL query(LL x,LL y){
    LL ret=0;
    ret+=(x+1)*(y+1)*que(tr1,x,y);
    ret-=(y+1)*que(tr2,x,y);
    ret-=(x+1)*que(tr3,x,y);
    ret+=que(tr4,x,y);
    return(ret);
  }
 
  int main(){   
    scanf("%*s%d%d",&n,&m);
    int t1,t2,t3,t4,t5,x1,x2,y1,y2;
    while (scanf("%s",&st)!=EOF){
      if (st[0]=='L'){
        scanf("%d%d%d%d%d",&t1,&t2,&t3,&t4,&t5);
        x1=t1;y1=t2;x2=t3;y2=t4;
        edi(x1,y1,t5);
        edi(x1,y2+1,-t5);
        edi(x2+1,y1,-t5);
        edi(x2+1,y2+1,t5);  
      }else{
        scanf("%d%d%d%d",&t1,&t2,&t3,&t4);
        x1=t1;y1=t2;x2=t3;y2=t4;
        LL ans=0;
        ans+=query(x2,y2);
        ans-=query(x1-1,y2);
        ans-=query(x2,y1-1);
        ans+=query(x1-1,y1-1);
        printf("%d
",ans);
      } 
    }
  }