P4514 上帝造题的七分钟 （二维树状数组）

题目链接
题目大意：

总体思路：
二维差分数组d[i][j]等于a[i][j]和a[i-1][j]+a[i][j-1]-a[i-1][j-1]的差=a[i][j]-(a[i-1][j]+a[i][j-1])+a[i-1][j-1](可以根据二维前缀和来理解）。
1、在二维矩阵进行修改操作，就是在二维差分数组上进行操作：
d[x1][y1] += c;
d[x1][y2+1] -=c;
d[x2+1][y1] -=c;
d[x2+1][y2+1] += c;
2、在二维矩阵进行查询操作
s[i][j]为二维差分数组的前缀和的前缀和（也就是矩阵的前缀和），求(x1,y1)和(x2,y2)的矩阵和=s[x2][y2]-s[x2][y1-1]-
s[x1-1][y2]+s[x1-1][y1-1]
求具体的s[x][y]=

于是我们就需要维护四个树状数组d[i][j],d[i][j]∗i,d[i][j]∗j,d[i][j]∗i∗j，从而实现区间查询。
推荐博客
下面代码就是二维树状数组的板子啦

#include<iostream>
using namespace std;
typedef long long ll;
int n,m;
char ch; 
int x,x1,y1,x2,y2;
int tr[4][2050][2050];
int lowbit(int i){
    return i&-i;
}
void vadd(int f,int x,int y,int d){
    for(int i=x;i<=n;){
        for(int j=y;j<=m;){
            tr[f][i][j]+=d;
            j+=lowbit(j);
        }
        i+=lowbit(i);
    }
    return ;
}
void add(int x,int y,int d){
    vadd(0,x,y,d);
    vadd(1,x,y,d*x);
    vadd(2,x,y,d*y);
    vadd(3,x,y,d*x*y);
    return ;
}
int vquery(int f,int x,int y){
    int s=0;
    for(int i=x;i>0;){
        for(int j=y;j>0;){
            s+=tr[f][i][j];
            j-=lowbit(j);
        }
        i-=lowbit(i);
    }
    return s;
}
int query(int x,int y){
    return vquery(0,x,y)*(x*y+x+y+1)-vquery(1,x,y)*(y+1)-vquery(2,x,y)*(x+1)+vquery(3,x,y);
}
int main(){
    scanf("X %d %d",&n,&m);
    while(~scanf(" %c",&ch)){
        scanf(" %d %d %d %d",&x1,&y1,&x2,&y2);
        if(ch=='L'){
            scanf(" %d",&x);
            add(x1,y1,x);
            add(x2+1,y1,-x);
            add(x1,y2+1,-x);
            add(x2+1,y2+1,x);
        }
        else{
            int ans=query(x2,y2)-query(x2,y1-1)-query(x1-1,y2)+query(x1-1,y1-1);
            printf("%d\n",ans);
        }
    }
    return 0;
}