树状数组
![](https://image.wsq127.top/file/9c9bc3d6a94d3ba5fbb31.png)
AI-摘要
Tianli GPT
AI初始化中...
介绍自己 🙈
生成本文简介 👋
推荐相关文章 📖
前往主页 🏠
前往爱发电购买
树状数组
wsq127写在最前
树状数组算是我目前学过最优雅好写的数据结构了。
树状数组也被称为二进制索引树(Binary Indexed Tree,BIT),是一种高效的数据结构,它可以实现 $O(\log n)$ 的单点修改和前缀和查询。
核心思想
当我们想实现单点修改和区间查询时,肯定会有人想到用一个数组来维护若干个小区间的和,使得修改和查询的复杂度都不会那么高。
树状数组便是巧妙的运用了二进制来实现这一想法。
现在我们存储每一个位置前面 lowbit 位的和,也就是是说 $c_i=\sum_{j=i-lowbit(i)+1}^ia[j]$,比如 $i=6$,那么我们可以先将 6 转化为二进制 $(0110)_2$,显然 $c[6]=a[5]+a[6]$。
实现
查询
这里偷借一下老师的图((((
不难发现长得确实很像树如果现在要求前 $i$ 项的和,那么就可以通过每次减去 $lowbit(i)$ 得到的 $c_i$ 求和,具体来说就是 $sum[i]=c[i]+sum[i-lowbit[i]]$。
还是拿 6 举例,先化成二进制 $(0110)_2$。
- $lowbit((0110)_2)=(0010)_2$,即 $lowbit(6)=2$
- $(0110)_2-(0010)_2=(0100)_2$,即 $6-2=4$
- $lowbit((0100)_2)=(0100)_2$,即 $lowbit(4)=4$
- $(0100)_2-(0100)_2=(0000)_2$,即 $4-4=0$
所以 $c[6]=c[4]+c[2]$。
代码:
1 | long long query(long long x) |
修改
查询是从上往下退,修改也同理,从下往上爬就行了,不难发现,$i$ 的父节点即为 $i+lowbit(i)$。
代码:
1 | void update(long long x,long long v) |
不过这样实在是太屎山了,不妨把他封装起来:
1 | class BIT |
进阶
区间修改单点查询
结合单点修改区间查询,不难想到差分,我们只需要对差分数组做树状数组,这样需要区间修改的话只需要单点修改差分数组的两端,单点修改的话需要修改一整个区间。
1 | c.update(l,x);c.update(r+1,-x);//l~r 加 x |
区间修改区间查询
先鸽着,有时间再来写实际是我钛菜了((
评论
匿名评论隐私政策
✅ 你无需删除空行,直接评论以获取最佳展示效果