308. Range Sum Query 2D - Mutable

求二维range sum。求range sum会不断改变值但不会改变总size，用BIT或线段树。BIT返回的是index和Index前所有元素的和，利用presum思想，求[i, j]之间的就是query(j) - query(i)。又因为是二维，相当于维护M个BIT，每个BIT存的是对应行的presum。

class BIT {
public: 
    BIT(const int M, const int N): sums(M, vector<int>(N + 1, 0)) {}

    void update(int i, int j, int delta) {
        while (i < sums.size()) {
            while (j < sums[0].size()) {
                sums[i][j] += delta;
                j += lowbit(j);
            }
            i += lowbit(i); 
        }
    }

    int query(int i, int j) const {
        int sum = 0;
        while (i > 0) {
            while (j > 0) {
                sum += sums[i][j];
                j -= lowbit(j);
            }
            i -= lowbit(i);
        }
        return sum;
    }
    static inline int lowbit(int x) {return x & (-x);}
    vector<vector<int>> sums;
};

class NumMatrix {
public:
    vector<vector<int>> *mat;
    BIT *t;
    NumMatrix(vector<vector<int>> &matrix) {
        const int M = matrix.size(), N = M == 0 ? 0 : matrix[0].size();
        t = new BIT(M, N);
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                tree.update(i, j, matrix[i][j]);
            }
        }
        mat = &matrix;
    }

    void update(int row, int col, int val) {
        int diff = val - (*mat)[row + 1][col + 1];
        (*t).update(row, col, diff);
    }

    int sumRange(int row1, int col1, int row2, int col2) {
        int res = 0;
        for (int i = row1; i <= row2; ++i) {
            res += (*t).query(i, col2) - (*t).query(i, col1);
        }
        return res;
    }
};