2D segment Tree in Python, why TLE?


  • 0
    M

    The logic is roughly the same as normal segment tree and I don't know why TLE.

    class NumMatrix(object):
        def __init__(self, matrix, up=-1, down=-1, left=-1, right=-1):
            """
            initialize your data structure here.
            :type matrix: List[List[int]]
            """
            if not len(matrix) or not len(matrix[0]):
                return
            m, n = len(matrix), len(matrix[0])
            
            if up < 0 or down < 0 or left < 0 or right < 0:
                up, down, left, right = 0, m - 1, 0, n - 1
            
            sub_matrices = []
            val = 0
            
            if up == down and left == right:
                val = matrix[up][left]
                
            elif up == down and left < right:
                mid = (left + right) // 2
                
                sub_matrices.append(NumMatrix(matrix, up, down, left, mid))
                sub_matrices.append(NumMatrix(matrix, up, down, mid + 1, right))
                
                for matrix in sub_matrices:
                    val += matrix.val
                    
            elif up < down and left == right:
                mid = (up + down) // 2
                
                sub_matrices.append(NumMatrix(matrix, up, mid, left, right))
                sub_matrices.append(NumMatrix(matrix, mid + 1, down, left, right))
                
                for matrix in sub_matrices:
                    val += matrix.val
            else:
                ud_mid = (up + down) // 2
                lr_mid = (left + right) // 2
                
                sub_matrices.append(NumMatrix(matrix, up, ud_mid, left, lr_mid))
                sub_matrices.append(NumMatrix(matrix, ud_mid + 1, down, left, lr_mid))
                sub_matrices.append(NumMatrix(matrix, up, ud_mid, lr_mid + 1, right))
                sub_matrices.append(NumMatrix(matrix, ud_mid + 1, down, lr_mid + 1, right))
                
                for matrix in sub_matrices:
                    val += matrix.val
                    
            self.up, self.down, self.left, self.right = up, down, left, right
            self.val = val
            self.sub_matrices = sub_matrices
            
    
        def update(self, row, col, val):
            """
            update the element at matrix[row,col] to val.
            :type row: int
            :type col: int
            :type val: int
            :rtype: void
            """
            up, down, left, right = self.up, self.down, self.left, self.right
            if row < up or row > down or col < left or col > right:
                return
            if row == up and row == down and col == left and col == right:
                self.val = val
            else:
                tmp_val = 0
                for matrix in self.sub_matrices:
                    matrix.update(row, col, val)
                    tmp_val += matrix.val
                self.val = tmp_val
    
        def sumRegion(self, row1, col1, row2, col2):
            """
            sum of elements matrix[(row1,col1)..(row2,col2)], inclusive.
            :type row1: int
            :type col1: int
            :type row2: int
            :type col2: int
            :rtype: int
            """
            up, down, left, right = self.up, self.down, self.left, self.right
            if row2 < up or row1 > down or col2 < left or col1 > right:
                return 0
            elif row1 <= up and row2 >= down and col1 <= left and col2 >= right:
                return self.val
            else:
                res = 0
                for matrix in self.sub_matrices:
                    res += matrix.sumRegion(row1, col1, row2, col2)
                return res
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.