class NumMatrix {
private:
    long tree[10005][10005];
    int n, m;
    vector<vector<int>> matrix;

public:
    int lowbit(int x) {
        return x & -x;
    }

    void modify(int x0, int y0, int val) {
        for (int x = x0; x <= m; x += lowbit(x)) {
            for (int y = y0; y <= n; y += lowbit(y)) {
                tree[x][y] += val;
            }
        }
    }

    long query(int row, int col) {
        long ret = 0;
        for (int x = row; x > 0; x -= lowbit(x)) {
            for (int y = col; y > 0; y -= lowbit(y)) {
                ret += tree[x][y];
            }
        }

        return ret;
    }

    NumMatrix(vector<vector<int>>& matrix) {
        m = matrix.size();
        if (m)
            n = matrix[0].size(); 

        this->matrix = matrix;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                modify(i + 1, j + 1, matrix[i][j]);
            }
        }
    }

    void update(int row, int col, int val) {
        int pre = matrix[row][col];
        modify(row + 1, col + 1, val - pre);
        matrix[row][col] = val;
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        long d = query(row2 + 1, col2 + 1);
        long a = query(row1, col1);
        long b = query(row2 + 1, col1);
        long c = query(row1, col2 + 1);

        return d - b - c + a;
    }
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix* obj = new NumMatrix(matrix);
 * obj->update(row,col,val);
 * int param_2 = obj->sumRegion(row1,col1,row2,col2);
 */