304. Range Sum Query 2D - Immutable

Question:

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.

Thinking:

  • Method 1:
    • 参考303. Range Sum Query - Immutable
    • 将每一行都类似303储存，当要计算矩阵的和时，我们对于每一行都按照303的计算方法，最后算和。
class NumMatrix {
    private int[][] dp;
    public NumMatrix(int[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return;
        int height = matrix.length, width = matrix[0].length;
        dp = new int[height][width + 1];
        for(int i = 0; i < height; i++)
            dp[i][0] = 0;
        for(int i = 0; i < height; i++)
            for(int j = 0; j < width; j++)
                dp[i][j + 1] = dp[i][j] + matrix[i][j];
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        for(; row1 <= row2; row1++)
            sum += this.dp[row1][col2 + 1] - dp[row1][col1];
        return sum;
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */
  • Method 2:
    • 仍然是dp，但是每个位置都存储从matrix[0][0]加到当前的值。
      • dp[a][b] = dp[a - 1][b] + dp[a][b - 1] - dp[a - 1][b - 1] (若果存在的话)
      • 第一行和第一列的值递加。
    • 查找时
      • 减去左下角左边的值，减去右上角上面的值，再加上左上角的左上角的值。
class NumMatrix {
    private int[][] dp;
    public NumMatrix(int[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return;
        int height = matrix.length, width = matrix[0].length;
        dp = new int[height][width];dp[0][0] = matrix[0][0];
        for(int i = 1; i < width; i++)
            dp[0][i] = dp[0][i - 1] + matrix[0][i];
        for(int i = 1; i < height; i++)
            dp[i][0] = dp[i - 1][0] + matrix[i][0];
        for(int i = 1; i < height; i++){
            for(int j = 1; j < width; j++){
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + matrix[i][j];
            }
        }
    }
    public int sumRegion(int row1, int col1, int row2, int col2) {
        int result = dp[row2][col2];
        if(col1 > 0)
            result -= dp[row2][col1 - 1];
        if(row1 > 0)
            result -= dp[row1 - 1][col2];
        if(row1 > 0 && col1 > 0)
            result += dp[row1 - 1][col1 - 1];
        return result;
    }
}
/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */

Second time

  1. Use a 2-D array to save the rectangle sum from (0, 0) to current point. 
    class NumMatrix {
 private int[][] dp;
 public NumMatrix(int[][] matrix) {
     if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
         dp = new int[0][0];
         return;
     }
     int height = matrix.length, width = matrix[0].length;
     dp = new int[height][width];
     for(int i = 0; i < height; i++){
         for(int j = 0; j < width; j++){
             int cur = 0;
             for(int p = 0; p <= i; p++){
                 cur += matrix[p][j];
             }
             dp[i][j] = (j > 0 ? dp[i][j - 1]: 0) + cur;
         }
     }
 }    
 public int sumRegion(int row1, int col1, int row2, int col2) {
     return dp[row2][col2] - (col1 > 0 ? dp[row2][col1 - 1]: 0)
         - (row1 > 0 ? dp[row1 - 1][col2]: 0)
         + (col1 > 0 && row1 > 0 ? dp[row1 - 1][col1 - 1]: 0);
 }
}
/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */