IOI '01 P1 - Mobile Phones

#include <iostream>
#include <vector>

using namespace std;

// 2D Fenwick Tree
void update(vector<vector<int>> &fenwick, int x, int y, int val) {
    for (; x < (int)fenwick.size(); x += x & -x) {
        for (int yy=y; yy < (int)fenwick[0].size(); yy += yy & -yy) {
            fenwick[x][yy] += val;
        }
    }
}

int getSum(vector<vector<int>> &fenwick, int x, int y) {
    int sum = 0;
    for (; x; x -= x & -x) {
        for (int yy = y; yy; yy -= yy & -yy) {
            sum += fenwick[x][yy];
        }
    }
    return sum;
}

inline int rangeSum(vector<vector<int>> &fenwick, int x1, int x2, int y1, int y2) {
    return getSum(fenwick, x2, y2) - getSum(fenwick, x1-1, y2)
    - getSum(fenwick, x2, y1-1) + getSum(fenwick, x1-1, y1-1);
}

int main() {
    int t, n;
    cin >> t >> n;
    vector<vector<int>> fenwick(1+n, vector<int>(1+n));
    while (cin >> t && t != 3) {
        if (t == 1) {
            int x, y, a; cin >> x >> y >> a;
            update(fenwick, x+1, y+1, a);
        } else {
            int l, d, r, u; cin >> l >> d >> r >> u;
            cout << rangeSum(fenwick, l+1, r+1, d+1, u+1) << endl;
        }
    }
    return 0;
}