$$\Huge 手撕线段树!$$
(龟速逃
一、线段树简介
线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。
线段树可以在$O(log~N)$ 的时间复杂度内实现单点修改、区间修改、区间查询(区间求和,求区间最大值,求区间最小值)等操作。
它所维护的信息,需要满足可加性,即能以可以接受的速度合并信息和修改信息,包括在使用Lazy标记时,标记也要满足可加性。
注:可加性表示运算能否合并,例如取模就不满足可加性,对 $4$ 取模然后对$3$ 取模,两个操作就不能合并在一起做。
二、线段树的基本结构
1. 线段树是什么东西
线段树($Segment~Tree$)是一种基于分治思想的二叉树结构。
用于在区间上进行信息的统计,将每个长度不为$1$的区间划分为左右两个区间,再通过区间合并求得该区间的信息。与按照二进制位($2$的次幂)进行区间划分的树状数组相比,线段树显得更加通用,但我认为也更复杂(复杂度属于我个人观点)。
线段树的基本结构:
- 线段树的每个节点都代表一段区间。
- 线段树具有唯一的根节点,其区间代表整个统计范围,如$[1,N]$。
- 线段树的每个叶节点都代表一个长度为$1$的区间$[x,x]$。
- 对于每个内部节点$[l,r]$,左子节点是$[l,mid]$,右子节点是$[mid+1,r]$。其中$mid=(l+r)/2$(向下取整)。
如图:
上图来自《算法竞赛进阶指南》。
再看一篇博客的图片。
给出数组$A=$ { $11,22,33,44,55$ }
对这个数组构造线段树,根节点编号为$1$,用数组$D$存储这棵线段树。
其中 $D_i$ 保存线段树上编号为 $i$ 的结点的值(每个结点所维护的值就是这个节点所表示的区间总和),如下图所示:
$D_1$即为根节点,它代表的区间就是$[1,5]$($a_1,a_2,…,a_5$)。它的值就是$\sum_{i=1}^{n=5} a_i$
观察可以发现,除去线段树的最后一层,整棵线段树一定是一棵完全二叉树,深度为$O(log~N)$。
因此我们可以按照与二叉堆相似的“父子$2$倍”(又称堆式存储)存储法存储线段树。
- 根节点编号为$1$。
- 编号为$x$的左子节点编号为$x \times 2$,右子节点编号为$x \times 2 + 1$。
这样就可以简单地使用$struct$数组存储线段树。
线段树最后一层在数组中保存的位置不是连续的,因此保存线段树的数组长度要不小于$4N$才能保证不越界。
2. 线段树的建树
线段树支持查询与修改指令。但这之前需要先建树$build$。
给定一个长度为$N$的序列$a$,要在区间$[1,N]$建立线段树。
一般用递归建树,从根节点往下递归$build$左右子树。
仍然通过图片解释:
我们还可以通过动图了解递归的过程(以区间最小值线段树为例):
既然过程已经了解了,那么就来试一下用代码实现?
可以用堆式存储法存线段树(说过了)
先用$build$函数进行“建树”。
void build(int rt, int l, int r) {
if (l == r) {
d[rt] = a[l];
return;
}
int mid = l + r >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
push_up(rt << 1, rt << 1 | 1);
//push_up是上传操作,即往上一个节点传信息。
}
3. 线段树的区间查询
区间查询指:求区间$[l,r]$的总和、最大值、最小值、$gcd$等等的操作。
线段树的性质:对于给定的区间,一定可以将其拆分为$log~n$个极大的区间。对这些区间的答案合并就可以得到$[l,r]$的答案。
代码实现其实就是分别找出这几个区间并合并它们的答案。
int query(int rt, int l, int r, int L, int R) {
if (l >= L && r <= R) return d[rt]; //当前的[l,r]区间被询问的[L,R]区间完全覆盖,直接返回答案。
int mid = l + r >> 1, ans = 0;
if (l <= mid) ans += query(rt << 1, l, mid, L, R);
if (r > mid) ans += query(rt << 1 | 1, mid + 1, r, L, R);
return ans;
}
4.线段树的区间修改
如果用暴力解决(遍历$[l,r]$区间)那么需要耗费$O(n)$的时间。
如何优化呢?。
我们可以引入$Lazy$标记(懒标记)。
引用一个经典故事:
$A$ 有两个儿子,一个是 $B$,一个是 $C$。
有一天 $A$ 要建一个新房子,没钱。刚好过年嘛,有人要给 $B$ 和 $C$ 红包,两个红包的钱数相同都是 $1$ 元,然而因为 $A$ 是父亲所以红包肯定是先塞给 $A$ 咯~
理论上来讲 $A$ 应该把两个红包分别给 $B$ 和 $C$,但是……缺钱嘛,$A$ 就把红包偷偷收到自己口袋里了。
$A$ 高兴地说:「我现在有 $2$ 份红包了!我又多了 $2 \times 1 = 2$ 元了!哈哈哈~」
但是 $A$ 知道,如果他不把红包给 $B$ 和 $C$,那 $B$ 和 $C$ 肯定会不爽然后导致家庭矛盾最后崩溃,所以 $A$ 对儿子 $B$ 和 $C$ 说:「我欠你们每人 $1$ 份 $1$ 元的红包,下次有新红包给过来的时候再给你们!这里我先做下记录……嗯……我欠你们各 $1$ 元……」
儿子 $B$、$C$ 有点恼怒:「可是如果有同学问起我们我们收到了多少红包咋办?你把我们的红包都收了,我们还怎么装?」
父亲 $A$ 赶忙说:「有同学问起来我就会给你们的!我欠条都写好了不会不算话的!」
这样 $B$、$C$ 才放了心。
不难发现,$A$是父亲节点,$B$、$C$是$A$的子节点。这个“这里我先做下记录……嗯……我欠你们各 $1$ 元……”就是懒标记。
关于懒标记……
相当于父节点先拿到了一些“钱”(赋值),它要分给两个儿子,接着……他自己就没钱了。
就这么简单!
来几张图:
就不放代码了,累死了
给个三连行不行!
点赞转发评论收藏~
嘿嘿
$BiliBili$:我有五连
%%%
azzz