二维树状数组 1：单点修改，区间查询 LibreOJ 133

这是一道模板题。

给出一个 n×mn×m 的零矩阵 AA，你需要完成如下操作：

• 1 x y k：表示元素 Ax,yAx,y 自增 kk；
• 2 a b c d：表示询问左上角为 (a,b)(a,b)，右下角为 (c,d)(c,d) 的子矩阵内所有数的和。

Input

输入的第一行有两个正整数 n,mn,m； 
接下来若干行，每行一个操作，直到文件结束。

Output

对于每个 2 操作，输出一个整数，表示对于这个操作的回答。

Example

样例输入

2 2
1 1 1 3
1 2 2 4
2 1 1 2 2

样例输出

7

Hint

对于 10%10% 的数据，n=1n=1； 
对于另 10%10% 的数据，m=1m=1； 
对于全部数据，1≤n,m≤212,1≤x,a,c≤n,1≤y,b,d≤m,|k|≤1051≤n,m≤212,1≤x,a,c≤n,1≤y,b,d≤m,|k|≤105，保证操作数目不超过 3×1053×105，且询问的子矩阵存在。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m;
ll a[5010][5010];
ll lowbit(ll x){
    return (x&-x);
}
void add(ll x,ll y,ll k){
    for(ll i=x;i<=n;i+=lowbit(i)){
        for(ll j=y;j<=m;j+=lowbit(j)){
            a[i][j]+=k;
        }
    }
}
ll getsum(ll x,ll y){
    ll sum=0;
    for(ll i=x;i>0;i-=lowbit(i)){
        for(ll j=y;j>0;j-=lowbit(j)){
            sum+=a[i][j];
        }
    }
    return sum;
}
int main(){
    scanf("%lld%lld",&n,&m);
    ll type;
    while(scanf("%lld",&type)!=EOF){
        if(type==1){
            ll x,y,k;
            scanf("%lld%lld%lld",&x,&y,&k);
            add(x,y,k);
        }
        if(type==2){
            ll x1,y1,x2,y2;
            scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
            printf("%lld\n",getsum(x2,y2)-getsum(x2,y1-1)-getsum(x1-1,y2)+getsum(x1-1,y1-1));
        }
    }
    return 0;
}