LeetCode Solutions

			

class FenwickTree {
 public:
  FenwickTree(int m, int n) : sums(m + 1, vector<int>(n + 1)) {}

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

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

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

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.update(i + 1, j + 1, matrix[i][j]);
  }

  void update(int row, int col, int val) {
    tree.update(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;
};

			

class FenwickTree {
  public FenwickTree(int m, int n) {
    sums = new int[m + 1][n + 1];
  }

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

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

  private int[][] sums;
}

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.update(i + 1, j + 1, matrix[i][j]);
  }

  public void update(int row, int col, int val) {
    tree.update(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;
}

			

class FenwickTree:
  def __init__(self, m: int, n: int):
    self.sums = [[0] * (n + 1) for _ in range(m + 1)]

  def update(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 += j & -j
      i += i & -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 -= j & -j
      i -= i & -i
    return summ


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.update(i + 1, j + 1, val)

  def update(self, row: int, col: int, val: int) -> None:
    self.tree.update(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)