[LeetCode] 304. Range Sum Query 2D - Immutable

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

Calculate accumulative sum in the region row by row.

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        self.row = len(matrix)
        self.column = len(matrix[0]) if self.row > 0 else 0
        
        if self.row != 0 and self.column != 0:
            self.nums = [[0] * (self.column + 1) for _ in range(self.row)]
            
            for y in range(self.row):
                for x in range(self.column):
                    self.nums[y][x+1] = self.nums[y][x] + matrix[y][x]
            
        else:
            self.nums = None
        

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        result = 0
        
        if 0 <= row1 < self.row and 0 <= col1 < self.column and \
           0 <= row2 < self.row and 0 <= col2 < self.column:
            for y in range(row1, row2+1):
                result += self.nums[y][col2+1] - self.nums[y][col1]
        
        
        return result
        
        


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

Use Binary Index Tree:

class BIT:
    def __init__(self, data):
        self.N = len(data)
        self.bit = [0] * (self.N + 1)
        
        for i in range(self.N):
            self.update(i+1, data[i])
    
    def update(self, index, delta): 
        while index <= self.N:
            self.bit[index] += delta
            index += self.lowbit(index)
    
    def query(self, index):
        sums = 0
        
        while index > 0:
            sums += self.bit[index]
            index -= self.lowbit(index)
        
        return sums
        
    
    def lowbit(self, index):
        return index & (-index)
    

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        self.bits = [BIT(row) for row in matrix]
        

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        sums = 0
        
        for i in range(row1, row2+1):
            sums += self.bits[i].query(col2+1) - self.bits[i].query(col1)
        
        return sums


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

Edited on 02/27/2021. Use BIT based approach.