private int[][] dp;
public NumMatrix(int[][] matrix) {
if( matrix == null
 matrix.length == 0
 matrix[0].length == 0 ){
return;
}
int m = matrix.length;
int n = matrix[0].length;
dp = new int[m + 1][n + 1];
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; 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) {
int iMin = Math.min(row1, row2);
int iMax = Math.max(row1, row2);
int jMin = Math.min(col1, col2);
int jMax = Math.max(col1, col2);
return dp[iMax + 1][jMax + 1]  dp[iMax + 1][jMin]  dp[iMin][jMax + 1] + dp[iMin][jMin];
}
Clean and easy to understand java solution


Nice solution! One minor thing. Notice assumption 3: You may assume that
row1 ≤ row2
andcol1 ≤ col2
.
Anyway it's always nice to have theMath.min
step.int[][] dp; public NumMatrix(int[][] matrix) { if(matrix == null  matrix.length == 0) return; int m = matrix.length, n = matrix[0].length; dp = new int[m + 1][n + 1]; for(int i = 1; i <= m; i++) { for(int j = 1; j <= n; 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]; }

That assumption was not there before I came up with my solution. It was added later. However I did think about whether or not I wanted to remove those Math.min statements after that assumption was added.
Considering the fact that these Math.min statements would not cause dramatic performance penalty and the principle that never trust user inputs, I decided to leave them there as some very basic precaution measure.

improve the space from O(mn) to O(1) by using the matrix to store DP since:
Note 1. "You may assume that the matrix does not change."
public class NumMatrix { private int[][] dp; public NumMatrix(int[][] matrix) { for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix[0].length; j++) { int left = (j == 0) ? 0 : matrix[i][j  1]; int up = (i == 0) ? 0 : matrix[i  1][j]; int corner = (i == 0  j == 0) ? 0 : matrix[i  1][j  1]; matrix[i][j] += (left + up  corner); } } dp = matrix; } public int sumRegion(int row1, int col1, int row2, int col2) { int left = (row1 > 0) ? dp[row1  1][col2] : 0; int up = (col1 > 0) ? dp[row2][col1  1] : 0; int corner = (row1 > 0 && col1 > 0) ? dp[row1  1][col1  1] : 0; return dp[row2][col2]  left  up + corner; } }

No need to create a larger matrix.
public class NumMatrix { int[][] mat; public NumMatrix(int[][] matrix) { mat = matrix; for(int i = 0; i < matrix.length; i++){ for(int j = 0; j < matrix[0].length; j++){ mat[i][j] += (j>0 ? mat[i][j1] : 0) + (i>0 ? mat[i1][j] : 0)  (i>0&&j>0?mat[i1][j1]:0); } } } public int sumRegion(int row1, int col1, int row2, int col2) { return mat[row2][col2]  (col1>0 ? mat[row2][col11]:0)  (row1>0?mat[row11][col2]:0) + (col1>0 && row1>0 ? mat[row11][col11]:0); } }

@ricace the idea is that for one given matrix, the user is going to perform a lot of sum calculations, so instead of retraversing the matrix everytime he asks for a sum, we calculate once and for all the sum from the origin to each cell and store them in a matrix then the sum from any point to another can be easily calculated fast from this matrix. So the sum method works in O(1), just the construction is O(n*m)

@lingjiadeng Me too.
public int sumRegion(int row1, int col1, int row2, int col2) { if(col1>0&&row1>0) return sum[row2][col2]sum[row2][col11]sum[row11][col2]+sum[row11][col11]; if(col1==0&&row1==0) return sum[row2][col2]; if(col1==0) return sum[row2][col2]sum[row11][col2]; if(row1==0) return sum[row2][col2]sum[row2][col11]; return 0; }