普通的pre sum computation，如果后续有值发生了更改，需要再重新计算一次这个pre sum 数组，时间复杂度为O(n)。但BIT，只需要对个别数值进行更改，时间复杂度为O(log n)。
但缺点是，普通的pre sum计算sum时，时间复杂度为O(1)。BIT需要O(log n)。
For example, original array = [0, 1, 2, 3, 4]
How to create BIT?
Create a new array with length 6 (5 + 1). [0, 0, 0, 0, 0, 0] Read each number from the original array and update related values in BIT following the RULE. RULE: 1. added the number to the value at (index + 1). 2. Update the next value in BIT until index is out of bound. How to get the sum from BIT?
If we want to sum(0, i), we start from index i + 1 in BIT. ans = 0. ans += BIT[i + 1] Get the parent of i + 1, ans += BIT[p[i + 1]], until the index <= 0
How to get Next?
1. 2's complement
2. &
3. add
For example, index = 5
1. Check the number with index 6 in BIT. BIT[6] += num[5]
2. 6 = 0110, 2's complement of 6 = 1001 + 1 = 1010
3. 0110 & 1010 = 0010
4. 0110 + 0010 = 1000. So next would be index 8 in BIT
________________________________________________________________________
How to get Parent?
1. 2's complement
2. &
3. subtract
For example, we want to get the sum(0, 3)
1. ans = 0
2. ans += BIT[4]
3. 4 = 0100, 2s complement of 4 = 1011 + 1 = 1100
4. 0100 & 1100 = 0100
5. 0100 - 0100 = 0. So parent of 4 would be 0.
0
1 2 4 8
3 5 6 9 10 12
7 11 13 14
15
经典题目
def __init__(self, matrix):
"""
:type matrix: List[List[int]]
"""
self.matrix = matrix
self.leftToRight = []
for l in matrix:
temp = []
for j in range(len(l)):
if j == 0:
temp.append(l[j])
else:
temp.append(temp[j - 1] + l[j])
self.leftToRight.append(temp)
# Time: O(m)
def update(self, row, col, val):
"""
:type row: int
:type col: int
:type val: int
:rtype: void
"""
for j in range(col, len(self.matrix[0])):
self.leftToRight[row][j] += val - self.matrix[row][col]
self.matrix[row][col] = val
# Time: O(n)
def sumRegion(self, row1, col1, row2, col2):
"""
:type row1: int
:type col1: int
:type row2: int
:type col2: int
:rtype: int
"""
ans = 0
for i in range(row1, row2 + 1):
ans += self.leftToRight[i][col2] - self.leftToRight[i][col1] + self.matrix[i][col1]
return ans
def __init__(self, matrix):
"""
:type matrix: List[List[int]]
"""
if matrix is None or len(matrix) == 0 or len(matrix[0]) == 0:
return
self.nums = [[0 for j in xrange(len(matrix[0]))] for i in xrange(len(matrix))]
self.tree = [[0 for j in xrange(len(matrix[0]) + 1)] for i in xrange(len(matrix) + 1)]
for i in xrange(len(matrix)) :
for j in xrange(len(matrix[0])) :
self.update(i, j, matrix[i][j])
print self.tree
# Time: O(m)
def update(self, row, col, val):
"""
:type row: int
:type col: int
:type val: int
:rtype: void
"""
delta = val - self.nums[row][col]
self.nums[row][col] = val
i = row + 1
while i < len(self.tree):
j = col + 1
while j < len(self.tree[0]):
self.tree[i][j] += delta
j += j & (-j)
i += i & (-i)
# Time: O(n)
def sumRegion(self, row1, col1, row2, col2):
"""
:type row1: int
:type col1: int
:type row2: int
:type col2: int
:rtype: int
"""
return self.sumHelper(row2, col2) + self.sumHelper(row1 - 1, col1 - 1) \
- self.sumHelper(row1 - 1, col2) - self.sumHelper(row2, col1 - 1)
def sumHelper(self, row, col):
ans = 0
i = row + 1
while i > 0:
j = col + 1
while j > 0:
ans += self.tree[i][j]
j -= j & (-j)
i -= i & (-i)
return ans
