'''
keys: https://www.topcoder.com/community/competitive-programming/tutorials/binary-indexed-trees/
Solutions:
Similar: 
T:
S:
'''
from typing import List

    # binary index tree
class NumMatrix:

    def __init__(self, matrix):
        if not matrix: return
        self.M, self.N = len(matrix), len(matrix[0])
        self.mat  = [[0] * self.N for _ in range(self.M)]
        self.BIT  = [[0] * (self.N + 1) for _ in range(self.M + 1)]
        for i in range(self.M):
            for j in range(self.N):
                self.update(i, j, matrix[i][j])

    def update(self, row, col, val):
        diff,  = val - self.mat[row][col]
        i, self.mat[row][col] = row + 1, val
        while i <= self.M:
            j = col + 1
            while j <= self.N:
                self.BIT[i][j] += diff
                j += (j & -j)
            i += (i & -i)

    def sumRegion(self, row1, col1, row2, col2):
        return self.sumCorner(row2, col2)         + \
               self.sumCorner(row1 - 1, col1 - 1) - \
               self.sumCorner(row1 - 1, col2)     - \
               self.sumCorner(row2, col1 - 1)

    def sumCorner(self, row, col):
        res, i = 0, row + 1
        while i:
            j = col + 1
            while j:
                res += self.BIT[i][j]
                j -= (j & -j)
            i -= (i & -i)
        return res
        
        
        
        # sum the matrix into array, Matrix: M*N. T of insert: O(N)
        # T of sum: O(M)
class NumMatrix1(object):
    def __init__(self, matrix):
        """
        initialize your data structure here.
        """
        for row in matrix:
            for col in range(1, len(row)):
                row[col] += row[col-1] #making the last column as the sum of pre cols
        self.matrix = matrix
        

    def update(self, row, col, val):
        """
        update the element at matrix[row,col] to val.
        """
        original = self.matrix[row][col]
        if col != 0:
            original -= self.matrix[row][col-1]
            
        diff = original - val
        
        for y in range(col, len(self.matrix[0])):
            self.matrix[row][y] -= diff

    def sumRegion(self, row1, col1, row2, col2):
        """
        sum of elements matrix[(row1,col1)..(row2,col2)], inclusive.
        """
        sum_ = 0
        for x in range(row1, row2+1):
            sum_ += self.matrix[x][col2]
            if col1 != 0:
                sum_ -= self.matrix[x][col1-1]
        return sum_
    
    
    # my naive
class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        self.m = matrix

    def update(self, row: int, col: int, val: int) -> None:
        self.m[row][col] = val

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        res = 0
        for r in range(row1, row2+1):
            for c in range(col1, col2+1):
                res += self.m[r][c]
        return res


# Your NumMatrix object will be instantiated and called as such:
# obj = NumMatrix(matrix)
# obj.update(row,col,val)
# param_2 = obj.sumRegion(row1,col1,row2,col2)