?LeetCode刷題實戰(zhàn)308：二維區(qū)域和檢索 - 可變

示例：
給定 matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]
sumRegion(2, 1, 4, 3) -> 8
update(3, 2, 2)
sumRegion(2, 1, 4, 3) -> 10
 
注意:
矩陣 matrix 的值只能通過 update 函數(shù)來進(jìn)行修改
你可以默認(rèn) update 函數(shù)和 sumRegion 函數(shù)的調(diào)用次數(shù)是均勻分布的
你可以默認(rèn) row1 ≤ row2，col1 ≤ col2

class NumMatrix {
public:
    void add(int val, int x, int y)
    {
        while(y < sum[x].size())
        {
            sum[x][y] += val;
            y += (y&-y);
        }
    }
    
    int getSum(int x, int y)
    {
        int ans = 0;
        while(y > 0)
        {
            ans += sum[x][y];
            y -= (y&-y);
        }
        return ans;
    }
 
    NumMatrix(vector<vector<int>> &matrix):vec(matrix) {
        if(matrix.size()==0) return;
        int m = matrix.size(), n = matrix[0].size();
        sum.resize(m, vector<int>(n+1, 0));
        for(int i =0; i < m; i++)
            for(int j =1; j <= n; j++)
                add(matrix[i][j-1], i, j);
    }
 
    void update(int row, int col, int val) {
        int d = val - vec[row][col];
        vec[row][col] = val;
        add(d, row, col+1);
    }
 
    int sumRegion(int row1, int col1, int row2, int col2) {
        int ans = 0;
        for(int i = row1; i <= row2; i++)
            ans += (getSum(i, col2+1) - getSum(i, col1));
        return ans;
    }
private:
    vector<vector<int>> sum;
    vector<vector<int>> &vec;
};