class NumMatrix {

private int[][] sum;

public NumMatrix(int[][] matrix) {

if (matrix.length == 0 || matrix[0].length == 0) return;

int M = matrix.length;

int N = matrix[0].length;

sum = new int[M+1][N+1];

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

if (sum == null) return 0;

return sum[row2+1][col2+1] - sum[row2+1][col1] - sum[row1][col2+1] + sum[row1][col1];

}

}

class NumMatrix2 {

private int[][] sums;

private int M;

private int N;

public NumMatrix2(int[][] matrix) {

if (matrix.length != 0 && matrix[0].length != 0) {

this.M = matrix.length;

this.N = matrix[N].length;

this.sums = new int[M][N + 1];

for (int i=0; i<M; i++) {

for (int j=1; j<=N; j++) {

this.sums[i][j] += this.sums[i][j-1] + matrix[i][j-1];

}

}

}

}

public int sumRegion(int row1, int col1, int row2, int col2) {

int res = 0;

for (int i=row1; i<=row2; i++) {

res += this.sums[i][col2+1] - this.sums[i][col1];

}

return res;

}

}

/**