科普文章 - NOI 一轮复习 III：数据结构
NOI 一轮复习 III：数据结构
知识清单：
简单工具
- 线段树
- 其他树形数据结构
基本思想
分治
数点
- 莫队
- 分块
树上问题
链剖分
树分治
- 虚树
阅读须知：
- 作者数据结构水平很低。
- 由于上条，所以你会发现本文中只有基础内容。
- 本文中 $\log$ 一般指以 $2$ 为底的对数。
1. 简单工具
这一部分学习一些结构简洁的数据结构工具。
树状数组
取出 $[1,2^n]$ 标准线段树中所有左儿子和根，构成一个森林结构，就是树状数组。
树状数组也称芬威克树（Fenwick Tree），二叉索引树（Binary Index Tree）。
树状数组相比于线段树的优点在于有着更小的时间和空间常数（具体地，少了一半），易于储存，但缺点是只能维护前缀的可结合信息——从结构来看，它是一个只能支持前缀区间定位的线段树。
设 $\operatorname{lowbit}(x)$ 表示 $x$ 二进制下最低位的 $1$ 的位权，考虑一个 $[1,n]$ 的树状数组，结点 $i$ 维护的是区间 $[i-\operatorname{lowbit}(i)+1,i]$ 的信息，查询前缀 $[1,x]$ 的信息时，我们只需进行一个简单的循环：初始令 $s=x$，然后不断累计 $s$ 的信息，然后令 $s\leftarrow s-\operatorname{lowbit}(s)$，直到 $s=0$。
正确性显然，而复杂度证明也很简单：只会循环 $s$ 在二进制下 $1$ 的个数次。
树状数组也可以支持动态开点，但一般来说这样做就影响了它的便捷性，所以一般要么用线段树替代，要么进行离散化。
树状数组大部分时候可以被线段树替代，基本只用于一些比较简单的序列维护问题以及动态二维数点的外层树。
K-Dimensional Tree
线段树维护了 $[1,n]$ 中的一个树形的线段集合，使得任意一条指定线段都可以拆成其中 $O(\log n)$ 个线段的不交并。
将这个问题扩展到更高维，我们需要一种数据结构，维护 $[1,n_1]\times [1,n_2]\times\ldots\times [1,n_k]$ 中的一个超长方体集合，使得任意一个给定的超长方体都可以拆成其中数量较少的超长方体的不交并。
可惜的是，要彻底做到这一点很难，我们退而求其次，解决下列问题：
给定 $m$ 个 $[1,n_1]\times [1,n_2]\times\ldots\times [1,n_k]$ 中的点，我们需要用一种数据结构维护一些点集，使得任意给定一个超长方体，其中包含的点都可以由较少的点集的不交并得到。
KD-Tree 解决这个问题的方法基于对点集的划分：
建立一个二叉树，每个结点维护一个超长方体内的点，假设当前点集为 $S$，若 $|S|\ne 1$，则挑选一个维度 $i$，按第 $i$ 个维度将所有点排序，设前一半和后一半分别为 $S_0,S_1$，分别递归构造 $S_0,S_1$ 的子树，令它们为 $S$ 对应结点的左右儿子。
那么如何选切分维度就比较关键，有一种比较简单的方法：第 $i$ 层划分时就划分第 $(i-1)\bmod k+1$ 维，也就是轮流划分。
KD-Tree 建树复杂度为 $O(n\log n)$，因为求长为 $n$ 的序列中的第 $k$ 大可以 $O(n)$ 完成。
下面分析这种 KD-Tree 进行一次超长方体定位的复杂度。
KD-Tree 的定位原理和线段树一样，考虑 $k$ 维超长方体中包含的 $2k$ 个 $k-1$ 维超长方体表面，我们求出这其中每个超平面经过的点集数量，再相加，就与复杂度直接相关。
考虑一个超平面，在连续 $k$ 轮划分中，原本的点集被分为了 $2^k$ 个子点集，而超平面必然只能经过其中最多 $2^{k-1}$ 个（可以选超平面少掉的那一维用扫描线进行分析），再递归下去，所以设点集大小为 $n$，复杂度是：
这里讨论 $k$ 较小的情况，$O(2^k)$ 可以看成常数 $C$，对 $n$ 应用 Master 定理，分类讨论：
如果 $\log_{2^k} 2^{k-1}=\dfrac{k-1}{k}=0$，那么 $k=1$，此时时间复杂度为 $O(n\log n)$，这就是线段树的复杂度。
如果 $\log_{2^k} 2^{k-1}=\dfrac{k-1}{k}>0$，那么 $k>1$，此时时间复杂度为 $O(n^{1-\frac{1}{k}})$。
由于总共 $O(k)$ 个超平面，所以第二类应该实际上是 $O(k\times n^{1-\frac{1}{k}})$。
例如，$k=2$ 时的 KD-Tree，一条边线最多经过一个点集分治两层后四个点集中的两个，如图，复杂度为 $O(\sqrt n)$。
实际上你可能已经注意到，上面叙述的 KD-Tree 大致是一种类似线段树的结构，最后的叶子是每个点，这种结构被称为是 Leafy 的，而另一种比较广泛使用的 KD-Tree 采用的是类似 BST 的结构，每个结点都存储一个单独的点，一般来说 Leafy 的数据结构好维护些。
例题 $33$：
维护一个二维平面上的大小为 $n$ 的点集，支持 $m$ 个操作，操作包括矩形区域加，以及矩形区域求最值。
直接上 KD-Tree 的矩形拆分即可。
时间复杂度为 $O(n\log n+m\sqrt n)$。
带插入的 KD-Tree：
如果强制在线问题中要求往 KD-Tree 中加点，最常见的解决方法是设置平衡常数 $\alpha$，插入后一旦某个最浅的祖先满足某个儿子的比重超过 $\alpha$ 就暴力重构，复杂度我不会分析。
还有一种复杂度容易分析的做法，根号重构：每插入 $B$ 个点就重新建 KD-Tree，而最近一块中的点在查询时可以暴力访问。
由于一次重构复杂度为 $O(n\log n)$，而查询复杂度为块长加上 $O(\sqrt n)$，所以当操作数为 $m=n$ 时可以设定 $B=\sqrt{n\log n}$，得到总复杂度 $O(n\sqrt{n\log n})$。
KD-Tree 实现搜索剪枝
在很多 $k$ 维空间搜索问题中，采用 KD-Tree 的递归结构可以进行大量最优性剪枝，从而达到期望较优的复杂度。
最常见的问题就是最近 $k$ 点问题。
注意 KD-Tree 的复杂度只有超长方体查询时才有确定的保证。
例题 $34$：[BZOJ 3053] The Closest M Points
给定 $k$ 维空间中 $n$ 个点，$q$ 次查询与给定点欧几里得距离前 $m$ 小的点。
采用非 Leafy 的结构，在 KD-Tree 上 DFS，用一个堆维护当前的前 $m$ 小答案。
定义一个点到 KD-Tree 上一个结点的距离 $dis$：设这个结点子树内所有点形成的最小超长方体为 $[l_1,r_1]\times\ldots[l_k,r_k]$，即 $l,r$ 分别是每一维坐标的最小值和最大值，$dis$ 就是点到这个超长方体的最短距离。
DFS 到一个结点时，假设询问点到当前结点距离超过堆中最大值，那么直接剪枝，不用递归。
否则，先尝试加入根代表的点（如果比堆中最大值小就替换），然后递归左右儿子。
时间复杂度玄学（最差应该是 $O(nq\log m)$），当给定点平均分布在以询问点为球心的超球面附近时表现较差。
用 KD-Tree 解决一些二维平面上的矩形划分问题，可以实现一些两层树套树做不到的功能，但代价是 $n$ 的指数增加 $0.5$。
2. 基本思想
因为快要 NOI 了，所以我之后写的可能有点暴躁，有可能会越写越短，毕竟本来是写给自己看的。
这一部分会提到一些数据结构以及其他算法中常用到的思路，比如序列分治，cdq 分治，整体二分，莫队，简单的分块等。
序列分治/猫树
实际上这个思路在前面那个 ynoi 题里就说到了，首先考虑一个简单的题目：
例题 $35$：
给定长度为 $n$ 的序列，$q$ 次询问区间和/区间最值/区间 $\gcd$/区间最大子段和。
解一：
线段树，都可以线段树。
时间复杂度 $O(n+q\log n)$。
解二：
区间和可以前缀和做到 $O(n+q)$，区间最值和区间 $\gcd$ 可以 ST 表做到 $O(n\log n+q)$。
那么，最大子段和上，难道不能去掉 $q$ 乘的 $\log n$ 吗？
当然可以，我们考虑对序列进行分治，假设当前处理所有询问区间属于 $[l,r]$ 的询问，设 $mid=\dfrac{l+r}{2}$。
对于每个 $i$ 维护 $[i,mid]$（如果 $i\in [l,mid]$）或 $[mid+1,i]$（如果 $i\in [mid+1,r]$）的最大前缀和，最大后缀和，最大子段和，然后对于跨过 $mid$ 的询问，我们可以 $O(1)$ 得到答案（用前后缀拼一下）。
那么不跨过 $mid$ 的询问自然可以递归成 $[l,mid]$ 和 $[mid+1,r]$ 分别求解。
这样询问的复杂度降到了 $O(1)$，总复杂度 $O(n\log n+q)$。
具体怎样的问题可以直接用这个方法求解：
- 没有修改；
- 可以给每个区间维护信息，使得一个区间的答案可以由前后缀的信息拼合；
- 在区间头或尾新增元素，信息可合并。
可能讲的不太本质。
但是上面这个做法还有个问题：它是离线的。
我们可以通过一系列操作将它在线化，具体就是记录下分治的整个过程。
考虑建立 $[1,n]$ 的线段树，对于每个区间 $[l,r]$，对所有 $i\in [l,r]$ 记录 $[i,mid]$ 或 $[mid+1,i]$ 的区间信息。
然后对于询问 $[l_0,r_0]$，我们只需要找到线段树上 $[l_0,l_0]$ 和 $[r_0,r_0]$ 的 LCA，然后根据这个点上 $l_0,r_0$ 的信息来 $O(1)$ 回答询问。
问题就是如何找这个 LCA？显然用 ST 表有经典的 $O(n\log n)-O(1)$ 做法。
考虑到线段树 $O(\log n)$ 层，每层每个点都有个到它所在区间分治中心的信息，所以时空复杂度本身就是 $O(n\log n)$，求 LCA 不会增加复杂度。
所以这样的话总的复杂度就是 $O(n\log n+q)$，可以支持在线区间询问，但不能修改。
值得一提的是，如果 $n=2^k$，上面求 LCA 还可以再简单一些——直接求 $l_0\oplus r_0$ 的最高位 $1$，就得到了 LCA 的深度，而分析上述过程发现我们并不需要 LCA 具体是哪个点，知道深度就够了。
上面的这种线段树似乎就叫猫树。
例题 $36$：[Luogu P7482] 不条理狂诗曲
给定 $n$ 个点的点带权链，求所有区间（一条子链为一个区间）点权最大独立集之和。
考虑序列分治，设当前分治区间 $[l,r]$，分治中心 $mid$，对于 $i\in [l,mid]$ 预处理 $a_i$ 表示 $[i,mid]$ 最大点权独立集，$b_i$ 表示 $[i,mid-1]$ 最大点权独立集，同理对于 $i\in [mid+1,r]$ 预处理 $c_i$ 表示 $[mid+1,i]$ 最大点权独立集，$d_i$ 表示 $[mid+2,i]$ 最大点权独立集。
设 $f(l_0,r_0)$ 为区间 $[l_0,r_0] (l\leq l_0\leq mid< r_0\leq r)$ 最大点权独立集，那么有：$f(l_0,r_0)=\max(a_{l_0}+d_{r_0},b_{l_0}+c_{r_0})$。
考虑何时取到前者，即 $a_{l_0}+d_{r_0}\ge b_{l_0}+c_{r_0}$，所以 $a_{l_0}-b_{l_0}\ge c_{r_0}-d_{r_0}$。
所以我们将左右边点按照 $a-b$ 和 $c-d$ 排序，枚举左边点，对于 $c-d$ 不超过当前点 $a-b$ 的都取 $a+d$ 为答案，否则取 $b+c$ 为答案，这容易通过维护 $c,d$ 的部分和来实现。
时间复杂度为 $O(n\log^2 n)$（考虑到需要排序，而且这里元素会变，不可以归并）。
例题 $37$：[COCI 2015] Norma
给定长度为 $n$ 的序列，定义一个区间的权值为区间最小值乘区间最大值乘区间长度，求所有区间权值和。
序列分治，设当前分治区间 $[l,r]$，分治中心 $mid$。
枚举 $i\in [l,mid]$，设 $a,b$ 为 $[i,mid]$ 的最小值和最大值，再令 $u,v$ 分别表示 $[mid+1,r]$ 中一个最小的数，使得其到 $mid+1$ 的区间中最小值小于 $a$，或最大值大于 $b$。
那么 $u,v$ 就把 $[mid+1,r]$ 分成了三段，每一段分别可以通过一些部分和简单地算出答案，这里不列式子了。
时间复杂度为 $O(n\log n)$。
例题 $38$：
给定平面上 $n$ 个点，求欧几里得距离最近点对。
其实和数据结构没什么关系，但是也是分治。
设 $n$ 个点为 $p_1,\ldots,p_n$，不妨设它们横坐标递增，令 $A(l,r)$ 表示 $p_l,\ldots,p_r$ 中的最近点对距离（$r-l\ge 1$）。
考虑如何求 $A(l,r)$，首先分治，令 $A_0=\min(A(l,mid),A(mid+1,r))$，我们只需要考虑是否存在 $l\leq u\leq mid<v\leq r$ 使得 $p_u,p_v$ 的距离 $d(u,v)$ 小于 $A_0$。
我们只取中点所在横坐标两侧 $A_0$ 范围内的点（如图左右两条线之间），枚举一个左侧点 $p_i$，然后只考虑纵坐标与其差不超过 $A_0$ 的点，由于右侧任意两点距离不小于 $A_0$，所以根据简单的抽屉原理可知这样的点最多有六个（如图中六个红点），所以依次枚举是可以接受的。
我们只需要将左右两边的点分别按照纵坐标排序，枚举左边点，对右边点按照纵坐标双指针，然后每次对区间中所有合法右侧点枚举一遍更新答案即可。
时间复杂度 $O(n\log n)$。
还有一类分治由于涉及到区间最值，常会取最值点作为分治点。
但此时破坏了 $\log$ 层的结构，所以一般会涉及到启发式合并等技巧。
其实这种分治也可以看作笛卡尔树上的搜索。
例题 $39$：[Luogu P4755] Beautiful Pair
给定长度为 $n$ 的序列 $a_1,\ldots,a_n$，求有多少个区间 $[l,r]$ 满足，$a_l\times a_r\leq \max(a_l,\ldots,a_r)$。
分治到区间 $[l,r]$ 时，设 $a_p$ 是 $[l,r]$ 的区间最大值，考虑跨过 $p$ 的区间，最大值一定是 $a_p$。
也就是说，我们要在 $[l,p-1],p,[p+1,r]$ 中任选两段各拿出一个数，积不超过 $a_p$ 的方案数。
用线段树维护当前做完的区间（如 $[l,p-1]$ 和 $[p+1,r]$），然后采用启发式合并，每次选其中长度短的那一边枚举，更新答案并将所有值插入另一棵线段树中。
时间复杂度为 $O(n\log^2 n)$。
CDQ 分治
cdq 分治其实有很多应用场景，比如决策单调性 DP 的分治优化，分治 FFT 等都是 cdq 分治的思想，但这里主要说的是和数据结构关系比较大的。
先从最简单的说起：归并排序求逆序对。
采用一个分治的思想，如果我们先将左右分别排序，然后仅考虑一左一右构成的逆序对。
那么原本两维的问题（位置，大小）就变成了一维（大小），分别排序后扫一遍即可。
同时排序也就简单了，可以 $O(n)$ 合并两个长度为 $n$ 的有序数组。
所以说，在一些数点问题中，CDQ 分治可以以一个 $\log$ 的代价，使问题的维度降低 $1$。
数点
许多数据结构问题最后都化为数点问题。
最经典的数点问题形如：给定 $n$ 个 $k$ 维空间中的点，$q$ 次询问超长方体中的点数。
根据是否在线，是否有修改要求等，可以继续分成一些 Case。
衡量一个数点算法，主要看它的预处理时间复杂度，单次询问时间复杂度以及空间复杂度。
我们有许多工具，设第 $i$ 个维度坐标大小范围为 $D_i$，首先来回顾一下：
| 工具 | 预处理复杂度 | 询问复杂度 | 空间复杂度 | 适用范围 |
|---|---|---|---|---|
| 前缀和 | $+O(\prod D_i)$ | $\times O(1)$ | $+O(\prod D_i)$ | 静态，在线 |
| 线段树（树状数组） | $(n)\times O(\log n)$ | $\times O(\log n)$ | $(n)\times O(\log n)$ | 带修改，在线 |
| CDQ 分治 | $(n)\times O(\log n)$ | / | $(n)\times O(1)$ | 离线 |
CDQ 分治没有询问复杂度是因为它是离线算法，预处理复杂度就表示总的复杂度。
上面这个表可能不是很严谨，但可以稍微理解一下。
此外，我们可以用扫描线将静态离线问题降 $1$ 维变成动态问题，也可以主动将动态问题升 $1$ 维变成静态问题。
稍微总结一下：
- 每个询问的复杂度由 CDQ 分治和树套树的总层数相加决定；
- 每用一层前缀和，这一部分预处理时空复杂度乘上 $O(D_i)$，所以一般前缀和最多用一层；
- 空间复杂度由树套树的层数决定。
P1：在线/离线静态一维数点
$O(D_1)$ 可以接受时采用前缀和，复杂度 $O(D_1+n+q)$。
否则要用前缀和就要离散化，是 $O((n+q)\log n)$。
离线情况下的处理可以理解成扫描线，但因为要排序所有有个 $\log n$。
P2：在线动态一维数点
使用线段树，$O(n\log n)-O(\log n)$。
P3：离线静态二维数点（离线动态一维数点）
扫描线+树，$O(n\log n)-O(\log n)$。
也可以 CDQ+扫描线，$O(n)-O(\log n)$。
P4：在线静态二维数点
前缀和+树（也就是主席树），$O(n\log n)-O(\log n)$。
P5：在线动态二维数点
由于在线且动态，前缀和和扫描线这样 $O(1)$ 的白嫖工具都失效了。
老老实实采用树套树，$O(n\log^2 n)-O(\log^2 n)$。
P6：离线静态三维数点（离线动态二维数点）
扫描线+树+树，$O(n\log^2 n)-O(\log^2 n)$。
CDQ+扫描线+树，$O(n\log n)-O(\log^2 n)$（去看陌上花开题解，最常见的方法）。
CDQ+CDQ+扫描线，$O(n)-O(\log^2 n)$。
再套下去感觉意义不大了，反正这种常规问题的一般套路就是：
如果静态，可以将一维用扫描线（排序即扫描线）或前缀和（如果在线）处理掉。
之后根据离线或在线考虑用 CDQ 或树来解决。
大家似乎比较喜欢在离线问题中使用恰好一层树。
当然，如果问题稍微修改一下：比如超长方体区域最大值，这时 CDQ 分治和前缀和等基于差分的方法可能会失效，考虑采用树套树解决。
此外，直接使用 KD-Tree，将复杂度加在 $n$ 的指数上，也是一种可以考虑的方案。
K 维偏序
一类比较特殊的数点问题：给定 $n$ 个 $k$ 维空间点 $P_1,\ldots,P_n$，求二元组 $(i,j)$ 的个数使得 $P_i$ 各维坐标均不大于/小于 $P_j$ 的各维坐标。
发现这个问题可以暴力，复杂度为 $O(kn^2)$。
发现这个问题可以看作离线静态 $k$ 维数点，复杂度为 $O(n\log^{k-1} n)$。
发现数点也可以用 KD-Tree，复杂度为 $O(n^{2-1/k})$。
还有一种比较诡异的暴力优化，考虑维护矩阵 $M_i (i\in [1,k])$ 表示第 $i$ 维某两个点的大小情况（$P_x$ 比 $P_y$ 小则第 $x$ 行 $y$ 列为 $1$，否则为 $0$），然后把所有 $M_i$ 对应位置相乘后取 $1$ 的个数即可。
可以发现这可以用 bitset 维护，求矩阵可以对每一维排序后分开考虑，复杂度 $O(kn\log n+\dfrac{kn^2}{\omega})$。
有的时候时间可以但是空间开不下，这时候可以使用分块优化空间，后面再说。