树状数组和线段树
树状数组和线段树是两种常用的数据结构,其可以大大提升数组的区间查询的效率,同时也保证了数据修改的灵活度。
一般数组 | 前缀和数组 | 树状数组 | 线段树 | |
---|---|---|---|---|
单点查询 | \(O(1)\) | \(O(1)\) | \(O(logn)\) | \(O(logn)\) |
区间查询 | \(O(n)\) | \(O(1)\) | \(O(logn)\) | \(O(logn)\) |
单点修改 | \(O(1)\) | \(O(n)\) | \(O(logn)\) | \(O(logn)\) |
区间修改 | \(O(n)\) | \(O(n^2)\) | \(O(nlogn)\) | \(O(logn)\) |
树状数组
树状数组的原理讲解可以参考视频:五分钟丝滑动画讲解 | 树状数组
用于区间求和和单点修改的树状数组模版
1 |
|
- 树状数组的核心就是
lowbit()
函数,数状数组第i
项代表的区间长度为lowbit(i)
- 树状数组的下标只能从 1 开始,不能从 0 开始
用于求前缀最大值的树状数组模版
1 |
|
线段树
线段树相对于树状数组而言则更为灵活,其可以实现高效区间修改。
线段树的原理就是将数组的区间储存在二叉树的节点中,[left, right]
区间对应的左右节点分别为 [left, mid]
和
[mid + 1, right]
(mid = (left + right) / 2
)。
‼️注:线段树的数组长度要开到原数组长度的 4 倍
用于区间求和的线段树模版
- 单点更新
- 区间求和
1 |
|
用于求区间极值的线段树模版
- 单点更新
- 区间求极值
1 |
|
有时候我们可能会遇到这样的需求:要多次将数组中一个区间内的每个元素都添加一个固定的值,如果逐一修改,则会消耗大量的时间,这个时候我们就可以使用带延迟标记的线段树。
什么是延迟标记?
—— 即对线段树的某个节点的数据更新完后不急于对其子节点进行更新,而是将更新信息存储下来,而当必须更新的时候再将信息传递给子节点。
使用延迟标记进行区间修改的线段树模版
- 区间修改
- 区间求和
1 |
|
案例
逆序对记数
1 |
|
二维数点
二维数点是树状数组的一个典型应用,本题的 AC 代码如下:
注:需要开启 O2 优化
1 |
|
统计最长递增子序列
1 |
|
其他
1 |
|
树状数组和线段树
https://goer17.github.io/2023/03/30/树状数组和线段树/