题解 | #打鼹鼠#

打鼹鼠

二维前缀和 ＋ 树状数组（二维）

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 5000;

ll tr[N][N];
int n,m;

int lowbit(int x){
    return x & -x;
}

void add(int x,int y,int v){
    for(int i=x;i<=n;i+=lowbit(i)) for(int j=y;j<=m;j+=lowbit(j)) tr[i][j]+=v;
}

ll sum(int x,int y){
    ll res=0;
    for(int i=x;i;i-=lowbit(i)) for(int j=y;j;j-=lowbit(j)) res+=tr[i][j];
    return res;
}

ll query(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);
}

int main(){
    scanf("%d%d",&n,&m);
    int op;
    while(scanf("%d",&op)!=EOF){
        if(op==1){
            int x,y,k;
            scanf("%d%d%d",&x,&y,&k); 
            add(x,y,k);
        }
        else{
            int a,b,c,d;
            scanf("%d%d%d%d",&a,&b,&c,&d);
            printf("%lld\n",query(a,b,c,d));
        }
    }

    return 0;
}