# 2D segment Tree in Python, why TLE?

• 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):
"""
: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
``````

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