模板 - 二维树状数组 （单点修改，区间查询）

#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++)
#define per(i,j,k) for(int i = (int)j;i >= (int)k;i --)
#define debug(x) cerr<<#x<<" = "<<(x)<<endl
#define mmm(a,b) memset(a,b,sizeof(a))
#define pb push_back

typedef double db;
typedef long long ll;
const int MAXN = (int)4e3+100;
const int INF = (int)0x3f3f3f3f;

inline int read() { int c = 0, f = 1;char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1;ch = getchar();}
    while (ch >= '0' && ch <= '9') {c = c * 10 + ch - '0';ch = getchar();}
    return c * f;
}

int A[MAXN][MAXN];
int N,M;

void update(int x,int y,ll val) {
    for (int i = x;i <= N;i += i&(-i)) {
        for (int j = y;j <= M;j += j&(-j)) {
            A[i][j] += val;
        }
    }
}

ll getsum(int x,int y) {
    ll sum = 0;
    for (int i = x;i > 0;i -= i&(-i)) {
        for (int j = y;j > 0;j -= j&(-j)) {
            sum += A[i][j];
        }
    }
    return sum;
}

int main()
{
    N = read(),M = read();
    int op,x,y,a,b;
    while (~scanf("%d",&op)){
        if (op==1) {
            x = read(),y = read(),a = read();
            update(x,y,1LL*a);
        }else {
            x = read(),y = read(),a = read(),b = read();
            printf("%lld\n",getsum(a,b)+getsum(x-1,y-1)-getsum(a,y-1)-getsum(x-1,b));
        }
    }
}