@douglasleer A fourth point to mention: 2D segment tree has O(nlog(n)) complexity for range update, because the lazy propagation technique for segment tree can only be applied to one of the dimensions. Point update still has O(log(m) * log(n)) complexity, though.
Your method is blazingly fast because of it's unique initial method. I'm still trying to understand how it worked.
You can write the __init__ method in following way, it's probably easier for understand and will also pass the OJ, but it's of course not as fast as @davidzhu918 's original method:
def __init__(self, matrix):
initialize your data structure here.
:type matrix: List[List[int]]
if len(matrix) == 0:
self.matrix = None
self.orig = [[0 for _ in xrange(len(matrix))] for _ in xrange(len(matrix))]
self.matrix = [[0 for _ in xrange(len(matrix) + 1)] for _ in xrange(len(matrix)+1)]
for i in xrange(len(matrix)):
for j in xrange(len(matrix)):
self.update(i, j, matrix[i][j])