Skip to content

308. Range Sum Query 2D - Mutable 👍

  • Time: $O(mn\log 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class FenwickTree {
 public:
  FenwickTree(int m, int n) : sums(m + 1, vector<int>(n + 1)) {}

  void add(int row, int col, int delta) {
    for (int i = row; i < sums.size(); i += lowbit(i))
      for (int j = col; j < sums[0].size(); j += lowbit(j))
        sums[i][j] += delta;
  }

  int get(int row, int col) {
    int sum = 0;
    for (int i = row; i > 0; i -= lowbit(i))
      for (int j = col; j > 0; j -= lowbit(j))
        sum += sums[i][j];
    return sum;
  }

 private:
  vector<vector<int>> sums;

  static inline int lowbit(int i) {
    return i & -i;
  }
};

class NumMatrix {
 public:
  NumMatrix(vector<vector<int>>& matrix)
      : matrix(matrix), tree(matrix.size(), matrix[0].size()) {
    for (int i = 0; i < matrix.size(); ++i)
      for (int j = 0; j < matrix[0].size(); ++j)
        tree.add(i + 1, j + 1, matrix[i][j]);
  }

  void update(int row, int col, int val) {
    tree.add(row + 1, col + 1, val - matrix[row][col]);
    matrix[row][col] = val;
  }

  int sumRegion(int row1, int col1, int row2, int col2) {
    return tree.get(row2 + 1, col2 + 1) - tree.get(row1, col2 + 1) -
           tree.get(row2 + 1, col1) + tree.get(row1, col1);
  }

 private:
  vector<vector<int>> matrix;
  FenwickTree tree;
};

 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class FenwickTree {
  public FenwickTree(int m, int n) {
    sums = new int[m + 1][n + 1];
  }

  public void add(int row, int col, int delta) {
    for (int i = row; i < sums.length; i += lowbit(i))
      for (int j = col; j < sums[0].length; j += lowbit(j))
        sums[i][j] += delta;
  }

  public int get(int row, int col) {
    int sum = 0;
    for (int i = row; i > 0; i -= lowbit(i))
      for (int j = col; j > 0; j -= lowbit(j))
        sum += sums[i][j];
    return sum;
  }

  private int[][] sums;

  private static int lowbit(int i) {
    return i & -i;
  }
}

class NumMatrix {
  public NumMatrix(int[][] matrix) {
    this.matrix = matrix;
    tree = new FenwickTree(matrix.length, matrix[0].length);
    for (int i = 0; i < matrix.length; ++i)
      for (int j = 0; j < matrix[0].length; ++j)
        tree.add(i + 1, j + 1, matrix[i][j]);
  }

  public void update(int row, int col, int val) {
    tree.add(row + 1, col + 1, val - matrix[row][col]);
    matrix[row][col] = val;
  }

  public int sumRegion(int row1, int col1, int row2, int col2) {
    return tree.get(row2 + 1, col2 + 1) - tree.get(row1, col2 + 1) - tree.get(row2 + 1, col1) +
        tree.get(row1, col1);
  }

  private int[][] matrix;
  private FenwickTree tree;
}

 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class FenwickTree:
  def __init__(self, m: int, n: int):
    self.sums = [[0] * (n + 1) for _ in range(m + 1)]

  def add(self, row: int, col: int, delta: int) -> None:
    i = row
    while i < len(self.sums):
      j = col
      while j < len(self.sums[0]):
        self.sums[i][j] += delta
        j += FenwickTree.lowbit(j)
      i += FenwickTree.lowbit(i)

  def get(self, row: int, col: int) -> int:
    summ = 0
    i = row
    while i > 0:
      j = col
      while j > 0:
        summ += self.sums[i][j]
        j -= FenwickTree.lowbit(j)
      i -= FenwickTree.lowbit(i)
    return summ

  @staticmethod
  def lowbit(i: int) -> int:
    return i & -i


class NumMatrix:
  def __init__(self, matrix: list[list[int]]):
    self.matrix = matrix
    self.tree = FenwickTree(len(matrix), len(matrix[0]))

    for i in range(len(matrix)):
      for j, val in enumerate(matrix[i]):
        self.tree.add(i + 1, j + 1, val)

  def update(self, row: int, col: int, val: int) -> None:
    self.tree.add(row + 1, col + 1, val - self.matrix[row][col])
    self.matrix[row][col] = val

  def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
    return (self.tree.get(row2 + 1, col2 + 1) - self.tree.get(row1, col2 + 1) -
            self.tree.get(row2 + 1, col1) + self.tree.get(row1, col1))