1
class NumMatrix {
2

3
  int mat[][];
4

5
  public NumMatrix(int[][] matrix) {
6
    mat = matrix;
7
    int rows = mat.length;
8
    int cols = mat[0].length;
9

10
    for (int i = 0; i < rows; i++) {
11
      for (int j = 0; j < cols; j++) {
12
        if (i > 0) mat[i][j] += mat[i - 1][j];
13
        if (j > 0) mat[i][j] += mat[i][j - 1];
14
        if (i > 0 && j > 0) mat[i][j] -= mat[i - 1][j - 1];
15
      }
16
    }
17
  }
18

19
  public int sumRegion(int row1, int col1, int row2, int col2) {
20
    int res = mat[row2][col2];
21
    if (row1 > 0) res -= mat[row1 - 1][col2];
22
    if (col1 > 0) res -= mat[row2][col1 - 1];
23
    if (row1 > 0 && col1 > 0) res += mat[row1 - 1][col1 - 1];
24

25
    return res;
26
  }
27
}