线段树, OI中最为常用的一种数据结构之一, 特点是结构美丽, 性质特殊, 可以用来解决很多看似不相干的问题。
标记的处理
通常情况下, 线段树获取一个区间的信息需要$\Theta{(\log n)}$的时间复杂度, 但是在经历多次访问后, 我们可以通过记录每次访问的一些信息来优化后续的访问速度, 避免重复的行为
这种处理方式就是打标记, 它通常有两种方式
懒标记
懒标记$\texttt{(lazy tag)}$顾名思义, 就是当你访问的线段树节点区间正好包含在需要更新的区间之内时, 就不需要再往下访问了, 之间给这个节点打一个tag, 告诉他我给你这个区间的所有内容都操作了一下, 这样, 当你下次询问的时候, 之间把这个tag供上去就行了
但这样就会出现一个性质: 即靠上边的节点的信息永远比靠下的节点要新, 因此当你询问到一个区间, 它的父亲节点没有把最新的状态传下来, 你拿着的还是”过时的”状态, 那么询问就会出现异常, 因此我们只好在发现这个节点有lazy tag时十分不情愿地把它的tag挪到下一层(仅此而已!!!)此情此景, 有没有想起当你赖床的时候你妈妈催你起床, 而你经过顽强的抵抗只能一步一步地挪起来?(笑)确实可以有这种情况, 就是每次询问到下一层, 懒标记就要先逃到再下一层, 甚至要逃到叶子节点才能停下来, 这样, 懒标记就丧失了它懒的用途, 仍会拖慢我们的时间复杂度
标记永久化
这是一种比懒标记更懒的标记!
它直接赖在节点上不动了!!!
标记永久化是一种比较神奇的技巧, 它的 update 操作和上面那位一样的, 不同的在于它的标记不会移动, 永远固定在那个节点上
在 query 时, 多维护一个 add值, 从上到下一点一点把这条链上的 tag 串起来
这样就会有一个新的性质: 即在q到一个节点时同时累计起来的add值就是该节点最新的标记情况, 因此返回的信息就变为$val[p] + add \times (r - l + 1)$
但这样做具有较大的局限性: 由于它改变了更新的先后顺序, 所以只能适用于区间加, 区间乘, 区间异或等等可以满足交换律的操作
代码这里就不放了, 网上随便找都有
ps 这个技巧是我在看一篇题解时才学到的, 他这里的 update 操作似乎没有一点 pushdown 的影子, 然后它没有 $\texttt{query}$ 操作, 直接把 $tree[1]$ 拿去更新答案了. 其实这就利用了标记永久化的性质, 因为到第一个节点时 $\texttt{add}$ 的值是 $0$ 啊, 所以 $tree[1]$ 永远是最新的!
讲完了代码的技巧, 现在我们来讲线段树的一些应用
线段树&扫描线
遇到求一些会有重叠的矩形的面积并(或周长并)时, 我们应该想到线段树＋扫描线
这里推荐阅读学习笔记-扫描线这篇文章
总结 这里的细节真的是亿点点多, 看的蒟蒻我惊慌失措.
其中有一个要注意的点是原文中没有讲的, 就是它的代码里用的标记永久化思想, 我在上面也写了.
还有一些重要的点, 原文中也有写, 这里在重申一下
- 由于他习惯从下往上扫(我习惯性理解的扫描线都是从左往右的, 不过这不是重点), 又由于题目给的坐标相差很大(取值范围 $0\leq x_1<x_2\leq10^9,0\leq y_1<y_2\leq10^9$ ) 因此我们考虑把 $x$ 坐标进行离散化, 变成线段树的下标
- 如何用一个线段树上的一段区间表示一小条线段? 答案是一段区间$[l, r]$表示 $[X[l], X[r + 1])$ 每段包括左端点, 但不包括右端点, 避免重复计数
线段树&树链剖分
遇到一些一次性修改一条树链(或子树) 的题, 我们通常是把它剖分了
然后利用$\texttt{dfn}$ 序的连续性, 将链上(子树)修改转变为线段树区间修改
其中修改树链时要做个求$\texttt{LCA}$的操作, 而修改子树时不用, 但是要用到子树的大小这个信息
李超线段树
留坑待填