1
// Using row prefix sum O(m)
2
class NumMatrix {
3
  vector<vector<int>> prefix;
4

5
 public:
6
  NumMatrix(vector<vector<int>> &matrix) {
7
    int m = matrix.size(), n = matrix[0].size();
8
    for (int i = 0; i < m; i++) {
9
      vector<int> row(n);
10
      row[0] = matrix[i][0];
11
      for (int j = 1; j < n; j++) {
12
        row[j] = row[j - 1] + matrix[i][j];
13
      }
14
      prefix.push_back(row);
15
    }
16
  }
17

18
  int sumRegion(int row1, int col1, int row2, int col2) {
19
    int sum = 0;
20
    for (int i = row1; i <= row2; i++) {
21
      sum += prefix[i][col2];
22
      if (col1 > 0) sum -= prefix[i][col1 - 1];
23
    }
24
    return sum;
25
  }
26
};
27

28
// Using mat prefix sum O(1)
29
class NumMatrix {
30
  vector<vector<int>> prefix;
31

32
 public:
33
  NumMatrix(vector<vector<int>> &matrix) {
34
    int m = matrix.size(), n = matrix[0].size();
35
    prefix = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));
36
    prefix[1][1] = matrix[0][0];
37
    for (int i = 1; i <= m; i++) {
38
      for (int j = 1; j <= n; j++) {
39
        prefix[i][j] =
40
            prefix[i - 1][j] + prefix[i][j - 1] + matrix[i - 1][j - 1] - prefix[i - 1][j - 1];
41
      }
42
    }
43
  }
44

45
  int sumRegion(int row1, int col1, int row2, int col2) {
46
    int sum = 0;
47
    sum += prefix[row2 + 1][col2 + 1];
48
    sum -= prefix[row1][col2 + 1];
49
    sum -= prefix[row2 + 1][col1];
50
    sum += prefix[row1][col1];
51
    return sum;
52
  }
53
};