Update range-sum-query-2d-mutable.py

kamyu104 · web-flow · commit 65b391df2f10 · 2016-06-29T22:03:28.000+08:00
diff --git a/Python/range-sum-query-2d-mutable.py b/Python/range-sum-query-2d-mutable.py
@@ -16,18 +16,17 @@ def __init__(self, matrix):
         self.__bit = [[0] * (len(self.__matrix[0]) + 1) \
                       for _ in xrange(len(self.__matrix) + 1)]
 
-        bit = [[0] * (len(self.__matrix[0]) + 1) \
-               for _ in xrange(len(self.__matrix) + 1)]
-        for i in xrange(1, len(bit)):
-            for j in xrange(1, len(bit[0])):
-                bit[i][j] = matrix[i-1][j-1] + bit[i-1][j] + bit[i][j-1] - bit[i-1][j-1]
-
         self.__bit = [[0] * (len(self.__matrix[0]) + 1) \
                       for _ in xrange(len(self.__matrix) + 1)]
-        for i in xrange(1, len(bit)):
-            for j in xrange(1, len(bit[0])):
+        for i in xrange(1, len(self.__bit)):
+            for j in xrange(1, len(self.__bit[0])):
+                self.__bit[i][j] = matrix[i-1][j-1] + self.__bit[i-1][j] + \
+                                   self.__bit[i][j-1] - self.__bit[i-1][j-1]
+        for i in reversed(xrange(1, len(self.__bit))):
+            for j in reversed(xrange(1, len(self.__bit[0]))):
                 last_i, last_j = i - (i & -i), j - (j & -j)
-                self.__bit[i][j] = bit[i][j] - bit[i][last_j] - bit[last_i][j]+ bit[last_i][last_j]
+                self.__bit[i][j] = self.__bit[i][j] - self.__bit[i][last_j] - \
+                                   self.__bit[last_i][j] + self.__bit[last_i][last_j]
 
     def update(self, row, col, val):
         """
