Binary Indexed Tree (树状数组)
对于Range Sum query这道题，我们除了用线段树去求解，树状数组一样也可以实现同样的功能，而且空间复杂度更小（线段树实际上需要O(2n)的空间，而树状数组的空间需求为O(n)），同时代码比线段树简单很多，唯一的问题在于架构逻辑难以理解
线段树基本上就是一个和原数组长度一样的查询数组，每一个奇数位下标（以1开始计算）都是和原数组的元素对应，每一个偶数位都是某几个位置元素的累积和，而对于BIT， 最重要的操作就是求最低位1的bit位操作，因为每一个位置的数字都和这个最低bit位操作的结果有关系，具体来说
- 每个下标的值就是每次减去下标最低位的1对应的值之后的一系列下标值的和，例如111为第7位，计算过程
7 - 7 & (-7) -> 6
6 - 6 & (-6) -> 4
4 - 4 & (-4) -> 0
所以第7位的值就是第7位原数组的值加上第6位的树状数组的值再加上第4位的树状数组的值，这里的第几位都是用的以1开始计算的下标，这里注意，树状数组的下标设置多加一个dummy node在0位这样会比较好算，有点像dp数组的情况
- 第二个问题就是当前位置的元素会对哪些位置的值产生影响，而这个问题同样可以利用最低位操作来解决，具体的，以1举例，计算过程如下
1 + 1 & (-1) -> 2
2 + 2 & (-2) -> 4
4 + 4 & (-4) -> 8
也就是说，第1位的值对第2位，第4位，第8位的值都产生了影响，明白了这两个基本原理，树状数组就可以得到实现了
class NumArray(object):
def __init__(self, nums):
"""
:type nums: List[int]
"""
if nums:
self.n = len(nums)
self.array = [0] * (self.n + 1)
self.nums = [0] * (self.n + 1)
for i in xrange(self.n):
self.update(i, nums[i])
def update(self, i, val):
"""
:type i: int
:type val: int
:rtype: void
"""
diff = val - self.nums[i + 1]
j = i + 1
while j <= self.n:
self.array[j] += diff
j += (j & -j)
self.nums[i + 1] = val
def sumRange(self, i, j):
"""
:type i: int
:type j: int
:rtype: int
"""
return self.getSum(j + 1) - self.getSum(i)
def getSum(self, i):
result = 0
j = i
while j:
result += self.array[j]
j -= (j & -j)
return result
这里始终需要注意，query时的i， j都是以0开始的坐标，而我们对nums和array数组都认为的加了一个dummy位，所以我们这里需要在query时注意边界问题
关于这个查询数组array的一些原理性的东西这里有篇博客写的比较清楚