树状数组, 又名二叉索引树(Binary Indexed Tree), 利用该结构能够有效地解决区间和查询问题, 并且查询的时间复杂度是O(log N)
前缀和查询
如图所示, 在原始数组的基础上我们引入一个辅助数组c[], c[i]代表的含义是数组i的值以及所有递归的前驱之和,整个辅助数组看上去像一颗树, 因此得名. 举例
-
- sum[3] = a[3] + c[2] = a[3] + a[2] + c[1] = a[3] + a[2] + c[1]
- sum[13] = a[13] + c[12] + c[8], 通过同样的代入方法递归计算c[12], c[8],可以算得c[13] 就是数组13个数值的和
从上面的计算看出, 本来13个值的和, 这里通过辅助数组只有3个数相加, 这也就是他能够O(log N)查询前缀和的秘密, 所有之前的数据按照倍增的思想,只要达到2的次方的规模即接管和值, c[2], c[4], c[8]均是一个数便计算出和值
现在的问题是如何根据index找出前驱呢
- c[7]的前驱是c[6]
- c[6]的前驱是c[4]
- c[4]的前驱是c[0] (不存在, 即c[4]已经包含前面所有)
- c[12]的前驱是c[8]
咋一看,还真看不出什么特点, 我们尝试一下把所有的数值用二进制表示一下
从上面的可以看出, 当前节点到前驱节点是当前节点减去只有最末尾为1的数, 知道0为止, 至于怎么求最末尾为1的数,请参考 巧用位运算
- pre = cur - cur & (~cur + 1)
def lowbit(self, i): # return i & (~i + 1) # 因为(~i + 1)是负数的表示方法, 所以可以简化成下面的写法 return i & (-i)
前缀和的查询代码如下
# 前缀和查询, i是数组的index def query(self, i): result = self.c[i] pre = (i+1) - self.lowbit(i+1) while pre > 0: result += self.c[pre-1] pre = pre - self.lowbit(pre) return result
区间和查询(i, j)
- 其实就是两个前驱和做下减法 sum(j) - sum(i-1)
- 注意判断边界条件 i == 0的情况
树状数组的建立(时间复杂度N*O(log N))
- 跟找前驱不一样, 它本身收集的是前驱的下一个元素到当前元素的和值
- 代码如下
# 根据数组创建树状数组, 自动处理下标, 没有下标从1开始的要求 def build(self): for i, val in enumerate(self.arr): left = (i+1) - self.lowbit(i+1) self.c[i] = self.arr[i] pre = i while pre > left: self.c[i] += self.c[pre-1] pre = pre - self.lowbit(pre)
原始数组数值更新(只能单点更新)
- 这个不像raw数组中的数值更新O(1)的时间复杂度
- 除了更新raw数组中的数值, 还要更新辅助数组中对应的值及递归所有后继的值, 时间复杂度O(log N)
- next = cur + cur & (~cur + 1)
- 有利有弊, 加快区间和查询的情况下, 其实是增加了更新时的负担, 所以树状数组适用于区间查询频繁, 而鲜有更新的场景
- 代码如下
# 单点更新, i是index, value是需要更新的值 def update(self, i, value): # 算出差值,方便后继更新 diff = value - self.arr[i] if diff != 0: self.arr[i] += diff self.c[i] += diff next = (i+1) + self.lowbit(i+1) while next <= len(self.arr)+1: self.c[next-1] += diff next = next + self.lowbit(next)
喜欢本篇内容, 请点击下方赞、在看或分享吧!?