Problem statement

https://leetcode.com/problems/range-sum-query-2d-mutable/

Solution

This problem is natural extension of problem 0307, but here we have two dimensional array. Again, we can solve it either with segment tree or with BIT. The second one is easier to code, it is very similar to 1d case.

Complexity

Time complexity for query and update is $O(\log m \cdot \log n)$. Time complexity of $O(\log m \cdot \log n \cdot mn)$. Space complexity for whole data structure is $O(mn)$.

Code

class BIT_2d:
    def __init__(self, m, n):
        self.sums = [[0] * (n+1) for _ in range(m+1)]
        self.m, self.n = m, n
    
    def update(self, i, j, delta):
        while i <= self.m:
            j2 = j
            while j2 <= self.n:
                self.sums[i][j2] += delta
                j2 += j2 & (-j2)
            i += i & (-i)
    
    def query(self, i, j):
        res = 0
        while i > 0:
            j2 = j
            while j2 > 0:
                res += self.sums[i][j2]
                j2 -= j2 & (-j2)
            i -= i & (-i)
        return res

class NumMatrix:
    def __init__(self, matrix):
        m, n = len(matrix), len(matrix[0])
        self.bit = BIT_2d(m, n)
        for i, j in product(range(m), range(n)):
            self.bit.update(i+1, j+1, matrix[i][j])
        self.matrix = matrix
        print(self.bit.sums)

    def update(self, r, c, val):
        self.bit.update(r+1, c+1, val - self.matrix[r][c])
        self.matrix[r][c] = val
        

    def sumRegion(self, r1, c1, r2, c2):
        return self.bit.query(r2+1, c2+1) + self.bit.query(r1, c1) - self.bit.query(r2+1, c1) - self.bit.query(r1, c2+1)

Remark

Interestingly, there is solution with $O(n)$ complexity for both operations, if we just use cumulative sums for rows.