308 Range Sum Query 2D - Mutable

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Example:

Given 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

Note:

The matrix is only modifiable by the update function. You may assume the number of calls to update and sumRegion function is distributed evenly. You may assume that row1 ≤ row2 and col1 ≤ col2.

分析

之前做过的g家面经。

就是比起存原矩阵，把矩阵转换成每行储存该行到此位置的和

比如原来的一行是，1,2,3,4，那么现在的矩阵就是1,3,6,10。

于是每次update需要把从第row行col列开始到这行结束的位置都更新，是O(n)

每次sumRegion是每行col2-col1的差的和，也是O(n)

int[][] sum;

public NumMatrix(int[][] matrix) {
    if(!(matrix.length == 0 || matrix[0].length == 0)) {
        int row = matrix.length;
        int col = matrix[0].length;
        sum = new int[row][col];
        for(int i = 0; i < row; i++) {
            sum[i][0] = matrix[i][0]; 
            for(int j = 1; j < col; j++) {
                sum[i][j] = sum[i][j - 1] + matrix[i][j];
            }
        }
    }
}

public void update(int row, int col, int val) {
    int dif = (col == 0? sum[row][0] : sum[row][col] - sum[row][col - 1]) - val;
    for(int i = col; i < sum[0].length; i++) {
        sum[row][i] -= dif;
    }
}

public int sumRegion(int row1, int col1, int row2, int col2) {
    int res = 0;
    for(int i = row1; i <= row2; i++) {
        int left = (col1 == 0)? 0: sum[i][col1 - 1];
        res += sum[i][col2] - left;
    }
    return res;
}