Range Sum Query 2D - Immutable

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).

Range Sum Query 2D
The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

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:
You may assume that the matrix does not change.
There are many calls to sumRegion function.
You may assume that row1 ≤ row2 and col1 ≤ col2.

Analysis

• 新建一个sumMatrix，每个格子(i, j)代表sumRegion(0,0,i,j)，只用算一次
• 算的时候通过DP减少重复计算 sumMatrix(i,j) = sumMatrix(i,j-1)+sumMatrix(i-1,j)-sumMatrix(i-1,j-1)+matrix(i,j)
• 每次call sumRegion(row1,col1,row2,col2)，利用已经算好的sumMatrix,sumMatrix(row2,col2)+sumMatrix(row1,col1)-sumMatrix(row1,col2)-sumMatrix(row2,col1)，3个数加减就可以了，比较快

Code

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

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

    public int sumRegion(int row1, int col1, int row2, int col2) {
        assert(row1 <= row2 && col1 <= col2);
        if (row1==0 && col1==0) {return sumMatrix[row2][col2];}
        else if (row1==0) {return sumMatrix[row2][col2]-sumMatrix[row2][col1-1];}
        else if (col1==0) {return sumMatrix[row2][col2]-sumMatrix[row1-1][col2];}
        else return sumMatrix[row2][col2]+sumMatrix[row1-1][col1-1]-sumMatrix[row1-1][col2]-sumMatrix[row2][col1-1];
    }
}


// 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);

Note

• 注意sumRegion有三种边界情况要注意。由于general的情况用到row1-1和col1-1，那么就要考虑row1==0 && col1==0; row1==0 && col1!=0; row1!=0 && col1==0 三种特殊情况。