方法1：对付一个的数组，如果须要求1~m的前缀和我们可以将其从下标1开始对m个数进行求和，对付n次操作，韶光繁芜度是O(n^2)，对付值的修正，我们可以直接通过下标找到要修正的数，n次操作韶光繁芜度为O(n)，在数组n值比较大的时候，求前缀和（即前k个数的和）的效率显得低了
方法2：
那么有人提出了一种优化的办法：初始我们用一个数组A的保存每个位置的初始值，然后用一个赞助数组B存放的是下标为i的时候A数组的前i个的和（前缀和），那么当我们须要查询m个数的前缀和的时候只要直策应用下标对B数组进行查询即可，n次查询，韶光繁芜度为O(n)，而此时，对付单点更新值的掩护花费，由原来的O(n)变成了O(n^2)，由于每一次与更新单点值都会对后面的已经打算好的B数组前缀和的值造成影响，须要不断更新B数组的值，n次更新掩护的花费自然就变成了O(n^2)，更新的效率变得低下
方法3：
树状数组(Binary Indexed Tree(B.I.T), Fenwick Tree)，便是本文先容的方法那么是否有一种方法可以让查询和更新的韶光繁芜度都小一些呢，至少可以令人接管，这里将先容树状数组如何处理前缀和查询和单点更新的问题，对付n次操作，韶光繁芜度都为O(nlogn)
图1-数状数组C与元素组A对应关系
如图1，对付一个长度为n的数组，A数组存放的是数组的初始值，引入一个赞助数组C（我们通过C数组建立树状数组）
C1 = A1
C2 = C1 + A2 = A1 + A2
C3 = A3
C4 = C2 + C3 + A4 = A1 + A2 + A3 + A4
C5 = A5
C6 = C5 + A6 = A5 + A6
C7 = A7
C8 = C4 + C6 + C7 + A8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8
我们称C[i]的值为下标为i的数所统领的数的和，C[8]存放的便是被编号8所统领的那些数的和（有8个），而下标为i的数所统领的元素的个数则为2^k个（k为i的二进制的末端0的个数）举两个例子查询下标m==8和m==5所统领的数的和
C[i]数学表达式：C[i] = A[i - 2^k+1] + A[i - 2^k+2] + ... + A[i]（k为i的二进制的末端0的个数）
8 = 1000（8的二进制），末端3个0，故k == 3，所统领的个数为2^3 == 8，C8是8个数的和5 = 0101（5的二进制），末端没有0，故k == 0，所统领的个数为2^0 == 1，C5是一个数的和（它本身A5）树状数组-求和而对付输入的数m，我们哀求编号为m的数的前缀和A1~Am（这里假设树状数组已经建立，即C1~C8的值已经求出，别焦急，在本文的最下方会做出建立树状数组的过程讲解，由于现在是在求前缀和，就假设C数组已经可用了吧）举两个例子m==7和m==6（sum(i)表示求编号为i的前缀和）
m==7 sum(7) = C7 + C6 + C4那么我们是怎么得到编号7是由哪几个C[i]求和得到呢（C4, C6, C7怎么得到的），这里有先容一种奥妙的方法：对付查询的m，将它转换成二进制后，不断对末端的1的位置进行-1的操作，直到全部为0停滞7的二进制为0111（C7得到），那么先对0111的末端1的位置-1，得到0110 == 6（C6得到），再对0110末端1位置-1，得到0100 == 4（C4得到），末了对0100末端1位置-1后得到0000（结束旗子暗记），打算停滞，至此C7，C6，C4全部得到，求和后便是m == 7时它的前缀和
m==6 sum(6) = C6 + C4m == 6时也是一样，先转成2进制即是0110，经由两次变换后为0100（C4）和0000（结束旗子暗记），那么求和后同样也得到了估量的结果
这里要先容一个高效的方法，lowbit(int m)，这是一个函数，它的浸染是求出m的二进制表示的末端1的位置，对付要查询m的前缀和，m = m - lowbit(m)代表不断对二进制末端1进行-1操作，不断实行直到m == 0结束，就能得到前缀和由哪几个Cm构成，十分奥妙，lowbit也是树状数组的核心
python代码
def lowbit(m): return m &(-m)
关于m&(-m)很多童鞋可能感到困惑，那么就不得不提及一下负数在打算机内存中的存储形式，负数在打算机中因此补码的形式存储的，如13的二进制表示为1101，那么-13的二进制而将13二进制按位取反，然后末端+1，即0010 + 0001 = 0011，那么1101 & 0011== 0001，很显然得到m == 13二进制末端1的位置是2的0次方位，将13 - 0001 == 12，再对12实行lowbit操作，1100 & 0100 == 0100，也很轻易得到了m == 12时二进制末端1的位置是2的2次方位，将12 - 0100 == 8，再对8实行lowbit操作，0100 & 1100 == 0100，得到m == 8时二进制位是2的2次方位，8 - 0100 == 0（结束操作），通过循环得到的13，12，8，则sum(13) == C13 + C12 + C8
求前缀和的代码
def sum(m): ans = 0 while m > 0 : ans += c[m] m = m - lowbit(m) return ans
对付n次前缀和的查询，韶光繁芜度为O(nlogn)
树状数组-单点更新
对付输入编号为x的值，哀求为它的值附加一个value值即A[i]=A[i]+value，我们把图再一次拿下来
图2-树状数组C与初始数组A对应关系
假设x==2，value==5，那么我们先找到A[2]的位置，通过不雅观察我们得知，如果修正了A[2]的值，那么统领A[2]的C[2]，C[4]，C[8]的前缀和都要加上value（所有的先人节点），那么和查询类似，我们如何得到C2的所有先人节点呢（由于C2和A2的下标相同以是更新时查询从C[x]开始），依旧是上述的奥妙的方法，但是我们把它倒过来对付要更新x位置的值，我们把x转换成二进制，不断对二进制末了一个1的位置+1，直到达到数组下标的最大值n结束
对付给出的例子x==2，假设数组下标上限n==8，x转换成二进制后即是0010（C2），对末端1的位置进行+1，得到0100（C4），对末端的1的位置进行+1，得到1000（C8），循环结束，对C2，C4，C8的前缀和都要加上value，当然不能忘却对A[2]的值+value，单点更新值过程结束python代码实现
def update(x,value): A[x] += value #//不能忘了对A数组进行掩护 while x < n: C[x] += value x = x+ lowbit(x)
对付n次更新操作，韶光繁芜度同样为O(nlogn)
这里有一个把稳事变，我们对付求前缀和与单点更新时，树状数组C是拿来直策应用的，那么问题来了，树什么时候建立好的，我怎么不知道？?
事实上，对付一个输入的数组A，我们一次读取的过程，就可以想成是一个不断更新值的过程（把A1~An从0更新成我们输入的A[i]），以是一边读入A[i]，一边将C[i]涉及到的先人节点值更新，完成输入后树状数组C也就建立成功了
树状数组-python完全实当代码示例class FenwickTree: def __init__(self, arrayA): # 传入初始数组，构建树状数组 self.size = len(arrayA) # 保存数组大小 self.arrayA = [0 for i in range(self.size)] #保存初始数组以及变更 #树状数组初始设置为0 self.arrayC = [0 for i in range(self.size)] for i in range(1,self.size+1): """ 构建类的初始数组A和树状数组B 这里有一个把稳事变，我们对付求前缀和与单点更新时，树状数组C是拿来直策应用的， 那么问题来了，树什么时候建立好的，我怎么不知道？? 事实上，对付一个输入的数组A，我们一次读取的过程，就可以想成是一个不断更新值的过程 （把A1~An从0更新成我们输入的A[i]），以是一边读入A[i]，一边将C[i]涉及到的先人节点值更新， 完成输入后树状数组C也就建立成功了 """ self.update(i,arrayA[i-1]) #【把稳】数组从0下标开始，update方法从1开始 def lowbit(self,m): """ 求出m的二进制表示的末端1的位置 :return: """ return m & (-m) def update(self, i, val): # 【把稳】数组从0下标开始，update方法从1开始 self.arrayA[i-1] += val # 更新初始数组 while i <= self.size: self.arrayC[i-1] += val #把稳数组下标从0开始 i += self.lowbit(i) def sum(self, i): # 求前缀和，sum方法从1开始 ans = 0 while i > 0: ans += self.arrayC[i-1] #数组下标从1开始 i -= self.lowbit(i) return ansif __name__ == "__main__": fenwickTree = FenwickTree([1,2,3,4,5,6,7,8]) print(fenwickTree.arrayA) #打印初始数组 print(fenwickTree.arrayC) #打印树状数组 print(fenwickTree.sum(4))#求arrayA前4项的和 fenwickTree.update(1,3) #arrayA第1个元素+3 print(fenwickTree.arrayA) # 打印更新数组[4,2,3,4,5,6,7,8] print(fenwickTree.arrayC) # 打印树状数组 print(fenwickTree.sum(4))#求arrayA前4项的和
