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

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

一刷：
题解: dp[i][j]等于从坐标matrix[0][0]到matrix[i - 1][j - 1]中所有元素的和

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

    public NumMatrix(int[][] matrix) {
        if(matrix == null || matrix.length == 0) return;
        int n = matrix.length, m = matrix[0].length;
        dp = new int[n+1][m+1];//outside
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
               dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + matrix[i-1][j-1]; 
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return dp[row2+1][col2+1] - dp[row1][col2+1] - dp[row2+1][col1] + dp[row1][col1];
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */

二刷，最好在sum的matrix外面还包一层，即dp = new int[n+1][m+1];，不然会出现很多out of boundary，或者要写更多的if条件。

class NumMatrix {
    int[][] sum;
    int m;
    int n;
    public NumMatrix(int[][] matrix) {
        m = matrix.length;
        n = matrix[0].length;
        sum = new int[m+1][n+1];
        sum[0][0] = matrix[0][0];
        for(int i=1; i<=m; i++){
            for(int j=1; j<=n; j++){
                sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + matrix[i-1][j-1];
            }
        }
        
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return sum[row2+1][col2+1] - sum[row1][col2+1] - sum[row2+1][col1] + sum[row1][col1];
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */