【題解】TIOJ 1869 . 堆石子遊戲

#include <iostream>
using namespace std;

const int maxn = 1030;
int n, bit[maxn][maxn], x, y, z, x1, y1, x2, y2, ans, num;

void update(int x, int y, int z){
    while (x < maxn){
        int ty = y;
        while (ty < maxn){
            bit[x][ty] += z;
            ty += ty & (-ty);
        }
        x += x & (-x);
    }
}

int query(int x, int y){
    int ret = 0;
    while (x>0){
        int ty = y;
        while (ty>0){
            ret += bit[x][ty];
            ty -= ty & (-ty);
        }
        x -= x & (-x);
    }
    return ret;
}

int main() {
    cin >> n;
    while (cin >> num){
        if (num == 1){
            cin >> x >> y >> z;
            update(x+1, y+1, z);
        }else{
            cin >> x1 >> y1 >> x2 >> y2;
            ans = 0;
            ans += query(x2+1, y2+1);
            ans -= query(x1, y2+1);
            ans -= query(x2+1, y1);
            ans += query(x1, y1);
            cout << ans << "\n";
        }
    }
}