思路 $O(nlog(n))$

二维树状数组：
1. 某个位置相加一个元素 add(x, y)
2. 某个查询一个区间 (a, b, x, y) ask(x,y)-ask(x,b-1)-ask(a-1,y)+ask(a-1,b-1)

时间复杂度

C++ 代码

#include<iostream>
using namespace std;
#define lowbit(x) x&-x
const int N=1040;
int c[N][N], n;

void add(int x, int y, int k){
    for(int i=x; i<=n; i+=lowbit(i)){
        for(int j=y; j<=n; j+=lowbit(j)){
            c[i][j] += k;
        }
    }
}
int ask(int x, int y){
    int sum = 0;
    for(int i=x; i>=1; i-=lowbit(i))
        for(int j=y; j>=1; j-=lowbit(j))
            sum += c[i][j];
    return sum;
}
int main(){
    cin>>n;
    int xx, yy, x, y, k, op;
    while(cin>>op, op!=3){
        if(op==1){
            cin>>x>>y>>k;
            add(x+1, y+1, k);
        }else{
            cin>>x>>y>>xx>>yy;
            xx++, yy++;
            cout<<ask(xx,yy)-ask(xx,y)-ask(x,yy)+ask(x,y)<<endl;
        }
    }
}