线段树基础
2025-12-27
简介
既然是基础,那就讲基础。
线段树是一种跟树状数组相似的树形数据结构,图上表示就是一颗补齐的树状数组。
一般只需要考虑父节点与两个儿子的信息向下传递与答案向上维护。
例题
Acwing 1277. 维护序列
题目传送门
很明显,我们需要在线段树中维护 sum,add,mul 三个值,其中后两个为懒标记。
这个时候就需要考虑对于答案的表示是先加后乘还是先乘后加,即将答案表示为 (sum+add)*mul 还是 sum*mul+add。
对于第一种而言,如果此时操作为区间加,则会导致无法正确向下传递信息,所以用第二种。
假设当前操作数为 a,对加而言,只需让 add+=a;对乘而言,只需让 mul*=a , add*=a。
线段树合并
前置知识:权值线段树 考虑这样一个情景:给定一棵树,每次给 (u,v) 路径上所有节点添加一种类型为 k 的物品,需要求每个节点最多的物品是哪一类,如果一样多输出编号最小的那一种物品。
很明显,我们需要在每个节点维护一个权值线段树,那么怎么将左右儿子的线段树合并到父节点呢?很明显,一个个插入并不满足要求,我们需要一种更高效的算法。
考虑根据权值线段树的先天结构进行合并,假设当前合并的线段树为 A 和 B,具体逻辑:
- A 和 B 中都有这个节点,将其进行合并,递归左右儿子。
- 只有 A 有,返回 A 树。
- 只有 B 有,返回 B 树。
可以证明,这样合并一定不会错,那么,时间复杂度呢?
我们设势能函数 Φ(S)=∣S∣,那么我们可以把单次操作花费写为:
cnt=1+ΔΦ
容易发现,ΔΦ=Φi−Φi−1=−1,刚好能够跟操作消耗(t=1)抵消!
也就是说,每次合并消灭的那个点刚好抵消了递归的消耗。
Luogu P4556 【模板】线段树合并 / [Vani 有约会] 雨天的尾巴
题目传送门
这道题与前面的情景相符,不多说啦。
