从树分块到树上莫队

· · 算法·理论

本文主要讲解树分块。树上莫队部分则主要将基于树分块的树上莫队，实用性较低，建议选择性阅读。

树分块

假如现在有一个线段树等朴素分治结构不支持维护的信息，要你支持在树链上查询，例如在线支持树链加、树链查 \le v 的点数，以下以这个为例。

记树的点数为 n，操作数为 m，编号为 1 的节点是根节点。这个定义对下文均适用。

  1. 假如树退化成一条链，也就是这个东西被放在序列上，这是一个经典题。防止有人不知道复杂度怎么来的，这里说一遍。

    考虑对序列以 B 为块长分块，在每个块内维护块排序后的结果。每次被散块加的块直接重构掉整个块，可以利用原有信息归并 \mathcal{O}(B) 计算；整块加打标记即可，单次操作 \mathcal{O}\left (\dfrac{n}{B}\right)；散块查询直接暴力统计个数，单次操作 \mathcal{O} (B)；整块查询则考虑在整块维护的有序序列上二分答案即可，单次操作可以做到 \mathcal{O}\left (\dfrac{n \log n}{B}\right)。

    取 B=\mathcal{O}(\sqrt{n\log n})，此时时间复杂度为 \mathcal{O}(m\sqrt{n\log n})。

  2. 对于一般情况的树，考虑重链剖分，对于 dfn 序的序列套用上述分块，单次操作每次跳重链都是一个区间操作，相当于将一个操作拆成了 \mathcal{O}(\log n) 次序列操作。直接与 1. 的复杂度相乘得到该算法时间复杂度为 \mathcal{O}(m\sqrt{n}\log^{1.5}n)。

    但事实上，对于一个操作而言，每次跳过的重链是互不相交的，即它们在 dfn 序列上也互不相交。所以一个序列上的块在单次树上操作最多被整块操作一次，故整块操作还可以去一个 \log。

    即单次树上修改复杂度为 \mathcal{O}\left (B \log n + \dfrac{n}{B}\right )，单次树上查询复杂度为 \mathcal{O}\left ((B + \dfrac{n}{B})\log n\right )。

    查询复杂度严格大于修改了，取 B=\mathcal{O}(\sqrt{n}) 即可，此时时间复杂度为 \mathcal{O}(m\sqrt{n}\log n)。

  3. 还是考虑重链剖分，这次我们直接对每条重链单独分块。即对于长度为 k 的一条重链，我们以 B=\mathcal{O}(\sqrt{k\log k}) 为块长对其分块。然后我们与 2. 相同地进行操作。

    由于跳过一条轻边子树大小至多是原先的 \dfrac{1}{2}，而重链长度一定不超过重链顶端的子树大小，所以在一条树链上的第 i 条重链长度是 \mathcal{O}\left ( \dfrac{n}{2^i}\right) 的。

    对一次操作中每条重链带入 1. 的复杂度，复杂度为 \displaystyle \sum _{i}\sqrt{\dfrac{n\log n}{2^i}}=\mathcal{O}(\sqrt{n \log n})。

    即总时间复杂度为 \mathcal{O}(m\sqrt{n \log n})。这和序列上做到了相同的复杂度，可以说明这一定已经最优了。

但是聪明的你发现，上面所有的针对一般树的做法都需要将若干链上的答案合并起来成为询问的答案。假如答案是不可合并的信息，那上述的东西全都是扯淡了。比如在线树链数颜色（P6177）。

还有一个缺点，我们在序列上常常使用如 \mathcal{O}(\sqrt{n})-\mathcal{O}(1),\mathcal{O}(1)-\mathcal{O}(\sqrt{n}) 的分块用于平衡复杂度。但是上重链剖分之后，单个操作的复杂度有一个下界 \mathcal{O}(\log n)，这远远不够用。

上面的东西本质上都是换着花样的序列分块，考虑如何真正的对「树」分块。

有两种方法：

  1. 随机撒点树分块：

    设定阈值 B，在树上随机撒 \dfrac{n}{B} 个点，然后对这些点建立虚树，我们称虚树上的点为关键点。关键点的数量是 \mathcal{O}\left (\dfrac{n}{B}\right ) 个（严格 \le 2 \cdot \dfrac{n}{B} 个）。

    对于任意一条树上的长度为 L 的链。期望下这条链上存在 \dfrac{LB}{n} 个关键点且均匀分布。故一条链被分为 \Theta\left (\dfrac{L}{B}\right ) 个长度为 \Theta(B) 的关键点间的路径。这也说明了两个相邻关键点的距离为 \Theta(B)。

  2. top cluster 树分块：

    设定阈值 B，对树进行 DFS，维护一个存贮边的栈，每条边在向上回溯时加入，则此时对应子树中所有的边都被加入过。

    当前点 u 要结束 DFS 的时候，如果出现以下三种情况，我们将栈清空并将点 u 记为关键点。

    • 点 u 是树的根结点。（只是为了处理方便）
    • 点 u 的至少有 2 个儿子 v，使得以 v 为根的子树中存在关键点。（使关键点形成树形结构，我们称其为收缩树）
    • 栈中有至少 B 条边。

    我们发现其实我们只关心栈中边的数量，所以我们只需在点 u 结束 DFS 后，记录此时栈中剩余的边数 h_u。

    只需在触发上面三种情况的时候让 h_u \gets 1，否则 h_u \gets 1+\sum \limits _{i \in \mathrm{son}(u)}h_i。

    显然第三种情况最多出现 \dfrac{n}{B} 次，而收缩树的叶子结点一定由这种情况提供，所以收缩树的叶子数 \le \dfrac{n}{B}，故弹栈次数 \le 2 \cdot \dfrac{n}{B}。即关键点数为 \mathcal{O}\left(\dfrac{n}{B}\right) 级别。

    我们将块改称为簇。我们将两个相邻关键点中间的部分划分出一个簇。这两个关键点构成祖先关系，我们分别叫它们上界点和下界点。任意两个簇有至多一个点相交。

    例如上图中 0,4,5,8,10 是界点。

    有时我们需要将点 u 不同儿子划分到不同的簇中，考虑将所有儿子依次列出，记其有 k 个儿子，a_i 为第 i 个儿子的 h，b_i 表示以第 i 个儿子为根的子树中是否有关键点。

    因为情况三，显然有 a_i \le B，否则其一定会触发清空。

    我们将 [1,k] 划分为若干段，对于其中的一段 [l,r] 需要满足 \sum \limits_{i=l}^{r}a_i \ge B 且 \sum \limits_{i=l}^{r-1}a_i < B 且 \sum \limits_{i=l}^{r}b_i \le 1，最后还有至多一段 \sum \limits_{i=l}^{r}a_i < B 的特殊情况加入。

    比较容易证明簇的数量是 \le 6 \cdot \dfrac{n}{B}。

两种方法的对比：

关键点（界点）的数量 块（簇）直径长度 块（簇）结点数 块（簇）的个数
随机撒点树分块 \le 2 \cdot \dfrac{n}{B} \Theta(B) \le n \le n
top cluster 树分块 \le 2 \cdot \dfrac{n}{B} \mathcal{O}(B) \mathcal{O}(B) \le 6 \cdot \dfrac{n}{B}

注：随机撒点树分块如果将每个子树中没有关键点的结点归于其第一个关键点祖先，则块（簇）的个数 \le 2 \cdot \dfrac{n}{B}。如果将这些点构成的联通块单独划分，则块（簇）结点数为 \Theta(B)。

例题 1

给定一个 n 个节点的树，点有权值。有 m 次询问，每次给出 u,v，查询 u 到 v 的路径上有多少个不同的整数。强制在线。

离散化后值域变为 \mathcal{O}(n)。

对序列上分块数颜色类比，我们预处理任意两个关键点之间的颜色数。单次询问链 (x,y) 时先取出询问链上第一个关键点 x' 和最后一个关键点 y' 之间对应的答案，然后我们需要暴力加入剩下的 \mathcal{O}(B) 个元素。

每暴力加入一个新的散块元素，我们都需要知道这个元素是否已经在之前被加入过，也就是考虑其出现次数。分为在之前加入散块与整块两种，前者可以维护一个桶，后者考虑维护树上前缀和。

也就是 (1,x') 和 (1,y') 上的的出现次数，减去 (1,fa_{\mathrm{LCA}(x',y')}) 和 (1,\mathrm{LCA}(x',y')) 上的出现次数。

因为 x',y' 都是关键点，根据虚树的性质 \mathrm{LCA}(x',y') 也是关键点，而关键点数量只有 \mathcal{O}\left (\dfrac{n}{B}\right ) 个，考虑对每个关键点 t 维护树上到根每种元素 i 的出现次数 f_{t,i}。总信息量是 \mathcal{O}\left (\dfrac{n^2}{B}\right )。

此时 (1,x'),(1,y'),(1,\mathrm{LCA}(x',y')) 上的的出现次数只需调用 f 即可。而 (1,fa_{\mathrm{LCA}(x',y')}) 直接用 (1,\mathrm{LCA}(x',y')) 减去 \mathrm{LCA}(x',y') 的单点信息即可得到。

维护两个关键点间的答案，可以从每个关键点向外 DFS，容易做到 \mathcal{O}\left(\dfrac{n^2}{B} \right)。树上前缀处理同样容易直接做到 \mathcal{O}\left(\dfrac{n^2}{B} \right)。单次查询则是 \mathcal{O}(B) 的。

取 B=\mathcal{O}\left(\dfrac{n}{\sqrt{m}}\right)，总复杂度为 \mathcal{O}(n\sqrt{m})。

例题 2

给定一棵 n 个点的树，点有点权 a_i，m 次询问，其中第 j 次询问给出 t_j 条路径，求这 t_j 条路径并集中点权的不同数个数以及 \mathrm{mex}。强制在线。

其中 \mathrm{mex}(S) 表示不在集合 S 中出现的最小非负整数。

值域这么小相当于直接把 bitset 塞你嘴里了。

显然对于每种元素，我们只关心其是否出现，而不关心其具体的出现次数。所以并集算重也没关系，单独考虑每条路径就行。

对于每个询问，我们希望计算出路径并集中每种元素是否出现的 bitset。对于不同点权计数，就是找 bitset 上 1 的个数。对于 \mathrm{mex}，则是找 bitset 上第一个 0 的位置。

考虑随机撒点后建虚树，维护任意两个关键点间路径元素是否出现的 bitset。

对于每条路径，先将中间关键点的路径点集加入答案，复杂度为 \mathcal{O}\left(\dfrac{V}{w}\right)。然后暴力 \mathcal{O}(B) 加入散块的元素即可。

然后就做完了，时间复杂度为 \mathcal{O}\left(\dfrac{(m+q)V}{w}+\dfrac{n^2}{B}+qB\right)，空间复杂度为 \mathcal{O}\left(\dfrac{n^2V}{B^2w}\right )。

取 B=\mathcal{O}\left(\dfrac{n}{\sqrt{q}}\right)，时间复杂度为 \mathcal{O}\left(\dfrac{(m+q)V}{w}+n\sqrt{q}\right)，空间复杂度为 \mathcal{O}\left(\dfrac{qV}{w}\right)。

例题 3

给定一棵 n 个节点的无根，有边权的树，m 组询问，每次询问给出 l,r，求 \sum \limits _{l \le i < j \le r}d(i,j)。

其中 d(x,y) 表示点 x 到点 y 的路径长度。

使用莫队二次离线，将问题转换为 \mathcal{O}(n\sqrt{m}) 次查询 \sum \limits _{i=1}^{r}d(i,x)，其中 x,r 给定。这步不太重要，不会莫队二离的可以跳过这部分，直接思考转换后的问题。

经典的，d(i,x)=\mathrm{dep}(i)+\mathrm{dep}(x)-2\mathrm{dep}(\mathrm{LCA}(i,x))。

所以 \sum \limits _{i=1}^{r}d(i,x)=r\mathrm{dep}(x)+\sum \limits _{i=1}^{r}\mathrm{dep}(i)-2\sum \limits _{i=1}^{r}\mathrm{dep}(\mathrm{LCA}(i,x))。

前两者维护容易。考虑第三个咋做。

同样经典的，对于两条从根 1 开始的路径 (1,u),(1,v)，它们的交集显然是 (1,\mathrm{LCA}(u,v))。可以考虑对于 1 \sim r 中的每个 i，将路径 (1,i) 的点的点权全部加上这个点的父边长度。然后查询 (1,x) 的点权和即为 \sum \limits _{i=1}^{r}\mathrm{dep}(\mathrm{LCA}(i,x))。

考虑按 r 从小到大处理，也就是有 \mathcal{O}(n) 次根链加父边，\mathcal{O}(n\sqrt{m}) 次根链求和。

这个你肯定要做到 \mathcal{O}(\sqrt{n})-\mathcal{O}(1)。所以直接考虑树分块。

在每个位置 u 维护 b_u 表示散块加对 u 到所在簇的上界点的点权和的影响，记 u 属于块 t_u。对于编号为 i 的上界点的位置 v 维护 c_i 表示 fa_v 到根的点权和。用 s_x 表示块 x 被整体加的次数。

显然，答案可以使用 b_x+c_{t_x}+s_{t_x}d 表示，其中 d 是 x 到其所在簇上界点的距离。

对于一次修改 (1,x)，显然只有块 t_x 中的 b 发生修改，可以 \mathcal{O}(B) 计算，而 c 本身就只有 \mathcal{O}\left(\dfrac{n}{B}\right) 个。而它们单个贡献的考虑都是简单 \mathcal{O}(1) 的。

所以单次修改可以做到 \mathcal{O}\left(\dfrac{n}{B}+B\right)。

取 B=\mathcal{O}(\sqrt{n})，时间复杂度为 \mathcal{O}(n\sqrt{n}+n\sqrt{m})。

例题 4

给定一棵 n 个节点的树，m 次操作，每次操作是链加点权或者链求点权和。

容易想到重链剖分，但是树剖要开很多数组，而且点权你不可能不存，为了保存树的形态你还要存父亲，所以即使你尽可能少开数组也绝对跑不了树剖。

考虑一些额外空间较少的结构。

不妨使用树分块。

先考虑如何构建树分块。随机撒点后建立虚树一般需要按 dfn 序排序后查询相邻 \mathrm{LCA}，但是这明显空间不够用。考虑依次从每个原始的关键点向上跳，同时对跳过的点打标记，碰见第一个被打过标记的点就是某两个关键点的 \mathrm{LCA}。

这样显然可以找到所有虚树上的点，且时间复杂度为 \mathcal{O}(n)。空间方面只用额外开一个 bitset 即可。其实还挺实用的是不是。

对每个关键点维护其在虚树上的父亲，空间显然是 \mathcal{O}\left (\dfrac{n}{B}\right )。

对每次操作，为方便将操作差分为四个根链操作，这个过程需要支持查询树上两个点 u,v 的 \mathrm{LCA}，可以利用树分块解决，先跳到关键点，然后在虚树上暴力跳，这样可以在 \mathcal{O}\left (\dfrac{n}{B}+B\right) 的时间复杂度得到 \mathrm{LCA}(u,v)。也可以用差不多的想法解决 \mathrm{dep} 查询。

下界点有点不好找，考虑对于每个关键点预处理下面每个方向遇到的第一个关键点，总量显然是 \mathcal{O}\left (\dfrac{n}{B}\right )。

后面的部分就与上题比较类似了，但是注意不要多开 \mathcal{O}(n) 的数组。

取 B=\mathcal{O}(\sqrt{n})，时间复杂度为 \mathcal{O}(n+m\sqrt{n})。

例题 5

菜菜子给了你一棵 n 个节点的树，有 m 个询问，每个询问包含参数 p_0,d_0,p_1,d_1 ，求：

\sum\limits_{d(p_0,a)\leq d_0}\sum\limits_{d(p_1,b)\leq d_1}d(a,b)

其中 d(x,y) 表示点 x 到点 y 的路径长度。

？？？？的第七分块。难度评分 10 /11。

记 N(x,d) 为 x 的 d 级邻域，即所有与 x 的距离 \le d 的位置的集合。

考虑对树进行树分块。

对于一个块 S，若 x \in S，我们记邻域 N(x,d_o) 在块中的部分 N(x,d_o)\cap S 为 G(x,d_o)。

若 x \notin S，设 y 是 S 中距离 x 最近的点，则 N(x,d_o)\cap S=G(y,d_o-d(x,y))。

对于任意一个 N(x,d_o)，我们可以将其拆分为树上的 \mathcal{O}\left (\dfrac{n}{B}\right ) 个块中的邻域 G。

对于一个询问 p_0,d_0,p_1,d_1，分别将 N(p_0,d_0),N(p_1,d_1) 拆分成 G(x,y) 状物。则只有 \mathcal{O}(1) 个 G(x,y) 的 x 不是块交界处的点。

现在每次询问我们都要统计 \mathcal{O}\left (\dfrac{n^2}{B^2}\right) 个邻域对的答案之和 (G_0(x_0,y_0),G_1(x_1,y_1))，两个邻域分别来自 N(p_0,d_0),N(p_1,d_1)。设它们分别位于块 B_0,B_1。

  1. 若 B_0=B_1：

    每次询问这种情况有 \mathcal{O}\left (\dfrac{n}{B}\right) 次。

    假如 x_0,x_1 中有至少一个点不是界点。这种情况只有 \mathcal{O}(m) 次。此时可以考虑暴力求出结果，将 d(x,y) 写作 \mathrm{dep}(x)+\mathrm{dep}(y)-2\mathrm{dep}(\mathrm{LCA}(x,y))，前两个可以直接求出。第三个可以转换为 \mathcal{O}(B) 次链加后 \mathcal{O}(B) 次链求和。树上差分后建立树上前缀和即可。这部分时间复杂度总共是 \mathcal{O}(mB)。

    假如 x_0,x_1 都是界点。由于块的直径大小是 \mathcal{O}(B) 的。所以 y_0,y_1 都分别只有 \mathcal{O}(B) 种可能。而 x_0,x_1 有 4 种组合。故一个块中本质不同的邻域对只有 \mathcal{O}(B^2) 种。

    考虑预处理出所有可能的答案，从小到大枚举 y_0 的大小，每次在前面所有距离 <y_0 的基础上扩展出一圈距离 =y_0 的点，相当于二维前缀和。这部分复杂度为 \mathcal{O}(B^2)。则这里预处理一共有 \mathcal{O}(nB) 的时间复杂度。

    查询时只需枚举每个块，每个块都是 \mathcal{O}(1) 的，所以这对复杂度的贡献是 \mathcal{O}\left( \dfrac{nm}{B} \right)。

  2. 若 B_0 \ne B_1：

    每次询问这种情况有 \mathcal{O}\left (\dfrac{n^2}{B^2}\right) 次，所以必须同时求解。

    此时 G_0,G_1 必然互不相交。设 G_0 中距离 G_1 最近的点是 n_0，G_1 中距离 G_0 最近的点是 n_1。

    则我们分别在 G_0,G_1 选一个点，这两个点的路径必然经过链 (n_0,n_1)。

    易知答案为 |G_0| \cdot |G_1| \cdot d(n_0,n_1)+ |G_1| \sum \limits _{i \in G_0}d(i,n_0)+ |G_0| \sum \limits _{i \in G_1}d(i,n_1)。

    对于每个 G 而言，只要我们知道 |G| 和 \sum \limits _{i \in G}d(i,n_o) 即可在收缩树上 dp 求出答案。

    与 1. 类似，可以直接在 \mathcal{O}(nB) 的时间复杂度内预处理。每次询问有至多 \mathcal{O}(1) 个需要暴力 \mathcal{O}(B) 处理。

则总时间复杂度为 \mathcal{O}\left(\dfrac{nm}{B}+(n+m)B\right)。取 B=\mathcal{O}(\sqrt{n})，得到最终的时间复杂度为 \mathcal{O}((n+m)\sqrt{n})，空间复杂度为 \mathcal{O}(n\sqrt{n})。

空间复杂度过高，考虑离线逐块处理，容易将空间降至 \mathcal{O}(n+m)。

我们发现随机撒点树分块可能会划分出 \mathcal{O}(n) 个块（当树是一棵菊花，且中心作为关键点），前面的题复杂度只和块直径大小相关。但是邻域拆分复杂度与块的个数强相关，随机撒点会让复杂度退化为 \mathcal{O}((n+m)n)。所以本题一定要使用 top cluster 树分块来实现。

树上莫队

树上莫队有一种人尽皆知的实现方法，大概是对原树 DFS，记录元素的括号序，具体一点就是元素进栈时记录一次，出栈时再记录一次。

记录编号 x 在括号序上分别在 f_{x,1},f_{x,2} 的位置出现，且 f_{x,1}<f_{x,2}。

然后一次查询链 (x,y) 时，分两种情况讨论：

  1. 若 x,y 呈祖先关系，不妨设 x 是上面的点。此时我们查询区间 [f_{x,1},f_{y,1}]。对于在区间中出现了恰好一次的元素就是链上的元素。实现方法可以在第一次碰见某个元素是加入，第二次撤销，也就是状态取反。
  2. 若 x,y 不呈祖先关系，此时我们查询区间 [f_{x,2},f_{y,1}]，与 1. 使用相同的方法计算即可，但是这样 \mathrm{LCA}(x,y) 不会被统计到。查询时加入即可。

其实就是在序列模拟了 dfs 的过程，第一次遇见某个元素时进栈，第二次遇见元素就相当于元素出栈。

可以看作将树压缩成了序列，既然是压缩就肯定失去了什么，不难发现这个莫队不支持回滚。因为它的元素序列中本身就包含删除，如果你不可以支持删除自然就做不了了。

所以说括号序莫队就像是上面用重剖维护树上分块一样拙劣。考虑如何真正的对「树」维护莫队。

维护序列莫队时我们会先对序列分块，每个块大小 \mathcal{O}(B)，然后对于所有的询问区间 [l,r] 排序，其中第一关键字是 l 所在的块编号，第二关键字是 r。

类比一下，维护树上莫队，可以考虑树分块。我们对所有询问链 (x,y) 排序，其中第一关键字是 x 所在的块编号，第二关键字是 \mathrm{dfn}_y。

对于位于同一个块的 x，我们按 \mathrm{dfn} 序处理，也可以看作是在模拟 DFS 的顺序进行移动。

每次对于两个指针 x,y，我们都需要分别将其移动到新的目标位置 x',y'。按照序列莫队上的想法，我们只需要将指针一步一步移动过去。

元素可能需要按顺序加入，所以我们需要按顺序处理出链 (x,x'),(y,y') 上的元素。但是假如 x 或 y 某一步是向下移动的，想知道它往那个儿子走会比较困难。

以 x 为例，考虑 x 是 x' 的祖先的情况，我们直接从 x' 开始向上跳父亲，然后将路上遇见的点反转后依次加入答案统计。除了这种移动都是 x 跳父亲，这是简单的。

需要注意不要将 \mathrm{LCA}(x,x'),\mathrm{LCA}(y,y') 重复加入。

试分析其复杂度，对于一个块，y 指针会在 \mathrm{dfn} 上 1 \to n 地完整遍历一次，相当于在树上 DFS 一次，y 指针向上回溯与向下移动的次数均为 \mathcal{O}(n)，所以 x 指针在单个块中 y 指针有 \mathcal{O}(n) 次移动。

对于每次询问，x 指针会在块中移动。显然单次询问移动距离是 \mathcal{O}(B) 的。

故总复杂度是 \mathcal{O}\left(\dfrac{n^2}{B}+mB\right)。取 B=\mathcal{O}\left( \dfrac{n}{\sqrt{m}}\right) 时复杂度得到平衡，为 \mathcal{O}(n\sqrt{m})。

回滚的实现与序列上的回滚莫队类似，但是实现细节会非常多。所以目前没有见到树上回滚莫队题目的例子。

参考代码

剪切板链接。

大多数题都使用了 \mathcal{O}(n \log n)-\mathcal{O}(1) 的 \mathrm{LCA}，请注意辨认。

鸣谢