304. Range Sum Query 2D Immutable - jiejackyzhang/leetcode-note GitHub Wiki

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
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12

Note:

1. You may assume that the matrix does not change.
2. There are many calls to sumRegion function.
3. You may assume that row1 ≤ row2 and col1 ≤ col2.

解题思路为Dynamic Programming。

由于数组不变，可以在初始化时将以matrix[0][0]为左上角，matrix[i][j]为右下角的2D的matrix的和保存起来。

public class NumMatrix {
    
    private int[][] sum;

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

    public int sumRegion(int row1, int col1, int row2, int col2) {
        if(sum == null) return 0;
        return sum[row2+1][col2+1] - sum[row2+1][col1] - sum[row1][col2+1] + sum[row1][col1];
    }
}


// Your NumMatrix object will be instantiated and called as such:
// NumMatrix numMatrix = new NumMatrix(matrix);
// numMatrix.sumRegion(0, 1, 2, 3);
// numMatrix.sumRegion(1, 2, 3, 4);

follow up: 如果数组是mutable的，即其中元素会update。

可令sum[i][j]存matrix[i][0]到matrix[i][j]的和，这样每次update之后，只需更新sum[i][j]这一行在第j列后面的值。 在求range sum时，外层循环为row1 to row2，里层为sum[i][col2]-sum[i][col1-1]。 因此update和sumRange都是O(n)。