树链剖分
- 作用
维护树上路径的相关信息。
常与线段树相结合。
- 性质
所有节点都属于且仅属于一条重链，重链将树完全剖分。
重链与子树内的 $\texttt{dfs}$ 序连续。【这一个性质非常有用】
每一条路径最多被拆分成 $\log n$ 条重链（向下经过一条轻边时，子树大小至少除以 $2$）。
- 一些定义
f[x]节点 $x$ 的父亲。sz[x]节点 $x$ 对应的子树大小。dep[x]节点 $x$ 的深度（假定编号为 $r$ 的节点深度为 $1$）。dfn[x]节点 $x$ 的 $\texttt{dfs}$ 序。hson[x]节点 $x$ 所对应的重儿子。top[x]节点 $x$ 所在的重链的顶部节点。rk[x]$\texttt{dfs}$ 序所对应的节点编号，即rk[dfn[x]] = x。
- 两个 $\texttt{dfs}$
- 第一个分别求出
fa[x] sz[x] dep[x] hson[x]。
具体代码如下 ：
1 | void dfs1 (int u,int fa) |
- 第二个分别求出
top[x] dfn[x] rk[x]。
具体代码如下 ：
1 | void dfs2 (int u,int fa) |
- 树上两点路径权值和的修改与查询
每次选择深度大的链往上跳，直到两点在同一条链上。由于链上的 $\texttt{dfn}$ 连续，所以直接再用线段树（或树状数组）进行维护即可。
以查询为例 ：
1 | void upd (int x,int y,int v)// x - y 的最短路径上，所有点的权值均加上 v |
- 完整代码
点击展开完整代码
1 |
|
- 拓展应用
求最近公共祖先。不断向上跳重链，当跳到同一条重链上时，深度较小的结点即为 $\texttt{LCA}$。
核心代码就是上一模板题的查询操作的修改。
1 | int LCA (int x,int y) |
可持久化线段树
- 作用
可保留每一个历史版本。
实现一些强制在线的功能。
- 性质
每一次修改后所增加的节点数最大为 $\log n$。
具有若干个根，且每一个根均可以构成一棵完整的线段树。
- 实现过程
只对进行修改的结点进行复制处理。
直接新开一块内存储存新节点，建树等同于新建节点。
对于每一个根，对应着一个版本，因此若要处理某一版本 $i$，访问或更新时直接使用
root[i]即可。其它过程与普通线段树差不多。
注意空间开到
N << 5差不多。
- 完整代码
1 |
|
P3834 【模板】可持久化线段树 2 同 P1533 可怜的狗狗
和上题差不多，用 root[i] 表示范围为 $[1,i]$ 的一个版本，查询时用前缀和的思想进行线段树的相减。
即在求第 $k$ 小的数时，先判断是否在左子树内，是则递归；否则递归右子树并将问题变为求第 $k - x$ 小的数（$x$ 表示进行相减后的区间的数的个数）。
代码如下：
1 |
|
李超线段树
支持区间加入一条平面上的线段，单点询问函数最值，用一次函数的形式储存线段。
有两种操作：
加入一个值域为 $[l,r]$ 的一次函数
给定 $k$ 后求与 $x = k$ 相交时 $y$ 最大的线段编号（相同时按照字典序）
拿新线段在中点处的值与原最优线段在中点处的值作比较，择优选取。主要可以分为以下几种情况：
之前没有线段，则新线段为最优解。
新线段完全优于原线段，直接更新整段。
新线段完全劣于原线段，直接忽略。
新线段与原线段有交点，继续进行分类讨论，两种情况继续对应更新左右子区间的两种情形：
交点在中点中间及左侧
交点在中点右侧
在写法上大致与普通线段树相同，但是有几个细节需要注意一下：
对于一条线段，如果直接用点斜式表示，斜率可能不存在（但由题知不会为 $0$），所以可以特判此情况将其标记为 $0$。
输入时需要调整两端点的位置，确保 $x_0 < x_1$ 从而方便计算。
在更新最优子区间时相当于标记下放，在此因减少分类讨论量默认为当前最优子区间的中点小于新加入的线段，若不符合强制交换一下，然后在此基础上更新左区间或右区间。
若不存在任何一条线段与查询直线有交，则输出 $0$；若有多条线段与查询直线的交点纵坐标都是最大的，则输出编号最小的线段。以上为输出的要求，对于不相交的线段，特判一下即可；而对于输出答案的方式，写一个函数进行比较，纵坐标相同时比较编号，否则比较纵坐标即可。
代码如下：
1 |
|
再来一道几乎属于是模板题的题目—P4254 [JSOI2008]Blue Mary开公司。
还是一样求 $x = k$ 时的最大值，不过还是有一些细节要注意：
虽然这是一个一次函数，但是由题目的数据范围可以看作一条 $[1,500000]$ 的线段。
第一天的收益为 $S$，之后每天增长 $P$，所以函数的斜率与截距分别为 $P$ 与 $S - P$。
询问的是函数的值而非编号，同时下取整至百位。
具体代码和上一个差不多，就不写出了。
莫队
简单来说就是一类把 $[l,r]$ 的答案用 $O(1)$ 的算法扩展到 $[l,r - 1],[l,r + 1],[l - 1,r],[l + 1,r]$ 的数据结构。由于涉及到分块，所以时间复杂度为 $O(n\sqrt{n})$。下面我们来简单证明一下莫队的时间复杂度。
首先考虑 $n,m$ 同阶的情况。令每一块 $l$ 的最大值分别为 $\max_1,\max_2,\cdots,\max_{\lceil \sqrt n \rceil}$。每一个块的第一个询问暴力查找，时间复杂度为 $O(n)$。之后在极端情况下每个 $R$ 均为 $n$，$L$ 为 $\max_i \to \max_{i - 1}$ 或 $\max_{i - 1} \to \max_i$。$R$ 同块内由于已经有序，最多为 $O(n)$，全部为 $O(n\sqrt n)$；$L$ 全部为 $O(\sqrt n (\max_i - \max_{i - 1}))$，通过裂项求和已知为 $O(\sqrt n (\max_ {\lceil n \rceil - 1}))$，最坏情况下也就是 $O(n\sqrt n)$。综上，莫队此时的时间复杂度为 $O(n\sqrt n)$。
对于 $n,m$ 不同阶的情况，设块长度为 $S$，则复杂度为 $O(n \times \dfrac{n}{S} + mS)$，由基本不等式可知，当 $S = \dfrac{n}{\sqrt m}$ 时取到最小值，即 $O(n \sqrt m)$。
莫队的模板如下（需要特别注意四个 while 循环的位置，前两步先扩大区间，即 --l 与 ++r，后两步再缩小区间，即 ++l 与 --r，从而保持 $l \le r + 1$，使得区间保持合法）：
1 | void solve () |
一道例题 P1494 [国家集训队] 小 Z 的袜子。
在排序之后，设 $f_i$ 表示颜色 $i$ 当前出现的次数，则更新答案时，扩大区间后答案为 $\tbinom{f_k + 1}{2} - \tbinom{f_k}{2}$，缩小区间为 $\tbinom{f_k}{2} - \tbinom{f_k - 1}{2}$。令答案为 $k$，则对于一个 $[l,r]$ 的询问，答案即为 $\dfrac{k}{\tbinom{l - r + 1}{2}}$。经过计算可以化简表达式， $\tbinom{f_k + 1}{2} - \tbinom{f_k}{2} = \dfrac{(f_k + 1)f_k - f_k(f_k - 1)}{2} = \dfrac{2f_k}{2} = f_k$。
因此我们通过莫队维护，时间复杂度为 $O(n\sqrt{n})$。完整代码如下：
1 |
|
关于普通莫队，还有一个小小的优化。通过奇偶化排序，可以优化 $r$ 指针的移动次数，从而加快效率。因此上题的 cmp 函数可以修改如下：
1 | bool cmp (node x,node y) |
普通莫队不支持修改，但我们可以加入一个时间的信息来支持修改。时间这一维的加入让我们移动的方向由四种变为六种，同时排序的关键字也随之增加。
按照 $n^\frac{2}{3}$ 的大小分成了 $n^{\frac{1}{3}}$ 块，按照左右时间这一关键字顺序进行排序，之后的移动有两种情况：
左右端点所在块不变，时间向后移动，时间复杂度为 $O(n)$。
左右端点所在块改变，最快情况下，时间移动 $n$ 个单位，时间复杂度为 $O(n)$。
由于左右端点所在块各有 $n^{\frac{1}{3}}$ 种，加上时间的复杂度，总共为 $O(n^{\frac{1}{3} + \frac{1}{3} + 1}) = O(n^{\frac{5}{3}})$。
于是来看一下这一题，P1903 [国家集训队] 数颜色 / 维护队列 。
加入时间这个维度后，按照 $l,r,t$ 的顺序从小到大排序。现在唯一多的一个步骤就是处理时间这个维度。若当前将第 $p$ 个位置上的颜色 $x$ 改为 $y$，莫队当前区间为 $[l,r]$。有以下两种情况：
加入修改。若该位置在区间 $[l,r]$ 内，则将其删除后改为 $y$，否则直接加上新的颜色 $y$。
还原修改。转换一下，相当于将 $p$ 个位置由颜色 $y$ 改为 $x$。
写的时候两个操作用了两个结构体区别开。$Q$ 是存放询问的内容，里面的元素分别为询问编号，左端点，右端点，时间；$M$ 是修改，里面的元素分别为位置，旧颜色，新颜色。最后还要注意一下空间大小，具体代码如下：
1 |
|
- 回滚莫队
在区间转移时，可能会出现删减操作无法实现的问题，而这时可以考虑是使用回滚莫队解决问题。
以这道例题 AT1219 JOISC 2014 Day1 历史研究 为例。该题的删除操作用普通莫队难以解决，由于询问离线，故可以考虑回滚莫队。
设块大小为 $s$，对于第 $i$ 的块有左右端点 $l_i,r_i$，莫队当前区间为 $[L,R]$。先对询问按之前的方式排序，然后根据不同情况分类讨论：
当前左端点对应的块的编号为 $x$，若与上一个询问的左端点所处编号为 $y$ 的块的左端点不同，那么有 $L = r_x + 1,R = r_x$。
询问的左右端点处于同一个块，则直接暴力循环求解。
询问的左右端点处于不同块，则有：
- 询问右端点大于 $R$：扩展莫队区间右端点。
- 同理扩展莫队区间左端点。
- 回答询问后撤销扩展莫队区间左端点，并将其回滚至 $r_x + 1$。
现在来分析一下时间复杂度，块大小仍然是 $s$。还是分类讨论，对于一个询问：
若左右端点在同一个块内，则普通的块内查询即可，显然遍历的时间复杂度为 $O(s)$。
若不在同一个块内，基于排序的方式，固定左端点，同时右端点单调。那么移动右端点所需的时间复杂度为 $O(n)$，左端点最多移动 $s$ 次。
所以总复杂度为 $O(s \times m + n \times
\dfrac{n}{s})$，有基本不等式易知当 $s = \dfrac{n}{\sqrt{m}}$ 时最优，为 $O(n \sqrt{m})$。
代码如下：
1 |
|
再来一道P5906 【模板】回滚莫队&不删除莫队。简要题意：求一段区间 $[l,r]$ 种相同数中下标的极值，多次询问并且离线。
还是一样，用普通的莫队易于扩展区间而不利于缩小区间，仍然考虑回滚莫队。记得记录最大最小值下标的也要回滚，同时变量不要冲突，多次覆盖。代码如下：
1 |
|
