树状数组Binary Indexed Tree，又称Fenwick Tree，这是一种查询和修改复杂度均为O(logn)的数据结构。这个树状数组比较有意思，所有的奇数位置的数字和原数组对应位置的相同，偶数位置是原数组若干位置之和，假如原数组A(a1, a2, a3, a4 ...)，和其对应的树状数组C(c1, c2, c3, c4 ...)有如下关系：
self.c[1] = nums[0]
self.c[2] = nums[0] + nums[1]
self.c[3] = nums[2]
self.c[4] = nums[0] + nums[1] + nums[2] + nums[3]
self.c[5] = nums[4]
self.c[6] = nums[4] + nums[5]
self.c[7] = nums[6]
self.c[8] = nums[0] + nums[1] + nums[2] + nums[3] + nums[4] + nums[5] + nums[6] + nums[7]
那么是如何确定某个位置到底是有几个数组成的呢，原来是根据坐标的最低位Low Bit来决定的，所谓的最低位，就是二进制数的最右边的一个1开始，加上后面的0(如果有的话)组成的数字，例如1到8的最低位如下面所示：
坐标 二进制 最低位
1 --- 0001 --- 1
2 --- 0010 --- 2
3 --- 0011 --- 1
x & -x is lowbit function, which will return x's rightmost bit 1, e.g. lowbit(7) = 1, lowbit(20) = 4.
class NumArray:
def __init__(self, nums):
self.n = len(nums)
self.a, self.c = nums, [0] * (self.n + 1)
for i in range(self.n):
k = i + 1
while k <= self.n:
self.c[k] += nums[i]
k += (k & -k)
def update(self, i, val):
diff, self.a[i] = val - self.a[i], val
i += 1
while i <= self.n:
self.c[i] += diff
i += (i & -i)
def sumRange(self, i, j):
res, j = 0, j + 1
while j:
res += self.c[j]
j -= (j & -j)
while i:
res -= self.c[i]
i -= (i & -i)
return res
# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# obj.update(i,val)
# param_2 = obj.sumRange(i,j)