树状数组可以解决什么样的问题:
这里通过一个简单的题目展开介绍,先输入一个长度为n的数组,如[1,2,3,5,10,8],然后我们有如下两种操作:
- 输入一个数m,输出数组中下标1~m的前缀和
- 对某个指定下标的数进行值的修改
多次执行上述两种操作,如何操作呢?
方法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,对于一个长度为n的数组,A数组存放的是数组的初始值,引入一个辅助数组C(我们通过C数组建立树状数组)
我们称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)
树状数组-求和
对于一个的数组,如果需要求1~m的前缀和我们可以将其从下标1开始对m个数进行求和,对于n次操作, 时间复杂度 是O(n^2),对于值的修改,我们可以直接通过下标找到要修改的数,n次操作时间复杂度为O(n),在数组n值比较大的时候,求前缀和(即前k个数的和)的效率显得低了
初始我们用一个数组A的保存每个位置的初始值,然后用一个 辅助数组B 存放的是下标为i的时候A数组的前i个的和(前缀和),那么当我们需要查询m个数的前缀和的时候只要直接使用下标对B数组进行查询即可,n次查询,时间复杂度为O(n),而此时,对于单点更新值的维护消耗,由原来的O(n)变成了O(n^2),因为每一次与更新单点值都会对后面的已经计算好的B数组前缀和的值造成影响,需要不断更新B数组的值,n次更新维护的消耗自然就变成了O(n^2),更新的效率变得低下
那么是否有一种方法可以让查询和更新的时间复杂度都小一些呢,至少可以令人接受,这里将介绍树状数组如何处理 前缀和查询 和 单点更新 的问题,对于n次操作,时间复杂度都为O(nlogn)
而对于输入的数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 + C4
m == 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,我们把图再一次拿下来
假设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 ans if __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项的和
相关文章
本站已关闭游客评论,请登录或者注册后再评论吧~