Skip to content

304. Range Sum Query 2D - Immutable 👍

  • Time: $O(mn)$
  • Space: $O(mn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class NumMatrix {
 public:
  NumMatrix(vector<vector<int>>& matrix) {
    if (matrix.empty())
      return;

    const int m = matrix.size();
    const int n = matrix[0].size();
    // prefix[i][j] := sum of matrix[0..i)[0..j)
    prefix.resize(m + 1, vector<int>(n + 1));

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        prefix[i + 1][j + 1] =
            matrix[i][j] + prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j];
  }

  int sumRegion(int row1, int col1, int row2, int col2) {
    return prefix[row2 + 1][col2 + 1] - prefix[row1][col2 + 1] -
           prefix[row2 + 1][col1] + prefix[row1][col1];
  }

 private:
  vector<vector<int>> prefix;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class NumMatrix {
  public NumMatrix(int[][] matrix) {
    if (matrix.length == 0)
      return;

    final int m = matrix.length;
    final int n = matrix[0].length;
    // prefix[i][j] := sum of matrix[0..i)[0..j)
    prefix = new int[m + 1][n + 1];

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        prefix[i + 1][j + 1] = matrix[i][j] + prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j];
  }

  public int sumRegion(int row1, int col1, int row2, int col2) {
    return prefix[row2 + 1][col2 + 1] - prefix[row1][col2 + 1] //
        - prefix[row2 + 1][col1] + prefix[row1][col1];
  }

  private int[][] prefix;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class NumMatrix:
  def __init__(self, matrix: List[List[int]]):
    if not matrix:
      return

    m = len(matrix)
    n = len(matrix[0])
    # prefix[i][j] := sum of matrix[0..i)[0..j)
    self.prefix = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m):
      for j in range(n):
        self.prefix[i + 1][j + 1] = \
            matrix[i][j] + self.prefix[i][j + 1] + \
            self.prefix[i + 1][j] - self.prefix[i][j]

  def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
    return self.prefix[row2 + 1][col2 + 1] - self.prefix[row1][col2 + 1] - \
        self.prefix[row2 + 1][col1] + self.prefix[row1][col1]