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