根号数据结构与根号平衡入门指南

· · 算法·理论

更好的阅读体验。

本文为本人为应付学校科技节写的屑作。写得比较仓促，可能存在不严谨或错误之处，欢迎批评指正。

在本文中若无特殊说明，n 表示元素数量，m 表示询问数量，V 表示值域范围为 [1, V]。

一、分块

分块，即将数据划分为多个块，并在操作时对整个块进行整体处理的思想。分块并非一种算法或数据结构，只能称为一种“思想”。下面将介绍一些分块思想的具体数据结构形式。

1. 块状数组（序列分块）

序列分块，即直接对原始数据从第一个元素开始连续地划分为多个块，并将每个块的信息保存到线性表中。进行区间操作时对整块整体处理，对两边不完整的部分（称为散块）暴力处理。一般来说每个块的块长为 O(\sqrt n)。这是分块的最基本形式。

示例：在线区间众数

题目描述：有一个长度为 n 的正整数序列。有 m 次询问，每次询问一个区间 [l, r]，输出该区间的区间众数。要求在线回答询问。

目标复杂度：线性根号。

首先将序列离散化并以 \sqrt n 为块长序列分块。预处理出每个块中每个数字的出现次数并做前缀和，以及每两块之间的众数以及它的出现次数。查询时可以算出两端散块中所有出现过的数字在整个区间中的出现次数并将该出现次数最大值与预处理的整块众数出现次数比较即可获得答案。

序列分块与其它领域结合

(1) 序列分块与计算几何结合

计算几何不仅可以用来解决纯几何问题，也可以用来将某些问题抽象化为几何问题从而解决其它问题。其中二维凸包相关理论经常与数据结构互相结合。

示例：区间加减区间最大子段和（洛谷 P4118 [Ynoi2018] 末日时在做什么？有没有空？可以来拯救吗？）

题目描述：有一个长为 n 的序列，有 m 次操作。

  1. 把区间 [l,r] 内所有数都加上 x。（x 可以为负数。）
  2. 查询区间 [l,r] 内的最大子段和，可以不选数。

目标复杂度：线性根号。

首先是关于最大字段和与计算几何之间的一个常用 trick：

对于某个区间。将该区间内前缀和与后缀和作为点按照横坐标为前后缀和长度，纵坐标为前后缀和值投射到两个平面上去。每次询问中前缀和平面与后缀和平面中均有且只有一个点会对答案产生贡献。设某点坐标为 (x, y)，并设该区间被整体加 a。则该点对答案的贡献（如果有）为 ax + y。观察发现只有平面上这些点围成的上凸壳上的点在不同的 a 值下可能对答案产生贡献。因此只保留这些上凸壳上的点。对前缀和凸壳以及后缀和凸壳做闵可夫斯基和后在凸壳上二分 ax + y 最大值即为该区间最大子段和。

将该思路拓展到本题。以 \sqrt n 为块长序列分块。将询问离线并逐块处理，对于每个询问记录此时已经整块加的值。对每块建线段树，线段树每个节点内保存上文所述的三个凸壳。整块修改在询问中已经记录不用处理。对于散块修改，将线段树节点内被完整修改的直接打整体加标记退出，被部分修改的暴力重构，这部分时间复杂度为单次 O\left(\sqrt n + \frac{\sqrt n}{2} + \frac{\sqrt n}{4} + \frac{\sqrt n}{8} + \cdots\right) = O(\sqrt n)。

对于整块查询，将两次散块修改（或开头末尾）之间的查询按照被整块加的值（此时就等于 a）递增排序（为保证复杂度应使用基数排序）。在凸壳中设一个位置变量表示上次答案所取的点，由于 a 递增，位置变量只会不断向右移动，移动到合适位置即为贡献点。虽然每次散块修改会重置位置变量，但每两次散块修改之间位置变量最多只会移动凸壳长度次。因此保证该部分均摊复杂度正确，总复杂度为 O(m \sqrt n)。对于散块查询，按照常规线段树方式查询，对于需要被查询的节点，在凸壳中二分即可找到贡献点，单次复杂度为 O(\log^2{\sqrt n})。

综上所述，总时间复杂度为 O(m \sqrt n)。

当只存在区间加正数不存在区间减时，该问题存在 \text{polylog} 解法，但与本文主题无关不再赘述。

(2) 序列分块与状态压缩结合

状态压缩是一种常用的当元素数量有限时将多个元素同时处理，从而将高复杂度操作降为 O(1) 复杂度的技术。当序列分块与状态压缩结合时，能够优化许多只用序列分块无法做到低复杂度的过程。

示例：区间极值（RMQ）问题

题目描述：给定一个长度为 n 的数列，和 m 次询问，求出每一次询问的区间内数字的最大值。

目标复杂度：线性。

首先以 \log n 为块长序列分块。预处理每块中的最大值，对该最大值建 ST 表。再预处理出每块内部的前缀和后缀最大值。这些预处理复杂度均为线性。这样对于跨块的询问，答案可以分成左端散块、右端散块和全部整块三部分，前两者可以通过查块内前后缀最大值得到，后者通过 ST 表得到，三者均为 O(1) 复杂度。

这样问题就只剩下不跨块询问的处理。考虑对每个块做一遍互相独立的单调栈（单调递减）。称加入块中第 i 个元素后为第 i 时刻，保存每个时刻的单调栈。由于块长为 \log n 而 n \leq 2^{32} 或 n \leq 2^{64}，所以该单调栈可以被状态压缩为一个 32 或 64 位无符号整数，因此可以 O(1) 保存，用该整数二进制表示中第 i 位的 0 或 1 表示块中第 i 个元素是否存在于单调栈中。当询问块内 [l, r] 范围内最大值时，将第 r 时刻单调栈中 l 前面的元素通过右移删除，再查询从末尾开始 1 第一次出现的位置，将其加上 l 后即可获得答案。查询从末尾开始 1 第一次出现的位置可以用 gcc 内建函数 __builtin_ctz() 来 O(1) 实现。

综上所述，总时间复杂度 O(n + m)，为线性。

2. 值域分块

将元素的值作为点投射到数轴上，再对该数轴分块。值域分块独立使用的情况很少，一般与其它根号算法或数据结构联合使用进行根号平衡。

值域分块与序列分块结合

示例：区间数值替换区间 kth（洛谷 P4119 [Ynoi2018] 未来日记）

题目描述：有一个长为 n 的序列 a（1 \leq a_i \leq V），有 m 次操作。

  1. 把区间 [l,r] 内所有的 x 变成 y。
  2. 查询区间 [l,r] 内第 k 小值。

目标复杂度：线性根号。

以 \sqrt n 为块长序列分块，以 \sqrt V 为块长值域分块。预处理出各块中每个数字的出现次数以及属于某值域块的数字的出现次数，对这两者各做一遍前缀和。然后对于块内所有的值，给他们各赋一个编号，将原数组第 i 个元素记作 a_i，其所属的块记作 bel_i，第 i 块中 val 的编号记作 root_{i,val}，第 i 块中编号 id 所对应的值记作 val_{i,id}，第 i 个元素在块内对应的编号为 index_i。这样总有 a_i = val_{bel_i,index_i}。

对于一个整块要把 x 修改为 y 的情况，如果该块内没有 y ，则直接把 x 的编号赋给 y，即让 root_{i,y}:=root_{i,x}，并把 x 的编号赋为 0；如果块内有 y，则暴力重构整个块。暴力重构时首先利用 a_i = val_{bel_i,index_i} 更新原数组，再将块内的所有 x 改为 y，然后重求一遍该块的 root，val，index 以及块中每个数字的出现次数以及属于某值域块的数字的出现次数（需要差分得到原数据修改完再重做一遍前缀和）。至于判断第 i 块中 y 是否存在，可以直接使用 root_{i,y} \neq 0。

这个方法看似暴力，但可以证明它的复杂度是正确的。考虑每个块各自的最大可能重构次数。显然这个次数只与块内的数字种类数有关。初始时每块最多有 O(\sqrt n) 种数字。重构的复杂度是 O(\sqrt n) \times O(\sqrt n) \times O(\sqrt n) = O(n \sqrt n) 的。修改时整块的数字种类数要么减一，要么不变。只有两端散块的数字种类数有可能加一。因此修改对复杂度最多只会增加 O(m \sqrt n)。因此修改部分的复杂度即为 O((n+m) \sqrt n)。

查询时，对于不跨块的询问，直接重构该块后暴力处理。对于跨块的询问，重构两端散块，在散块中算出询问中每个数字的出现次数以及属于某值域块的数字的出现次数。然后从第一个值域块开始扫描，每次将询问的 k 值减去整块+散块中属于该值域块的数字的出现次数（整块的答案由差分得到），直到即将减去该值会使 k \leq 0，然后在该值域块内部从左端点数值开始扫描，每次将询问的 k 值减去整块+散块中该数字的出现次数，直到即将减去该值会使 k \leq 0。最后扫描到的这个数字即为答案。因此查询部分的复杂度为单次 O\left(\sqrt n + \sqrt V\right)。

因此总时间复杂度 O\left((n+m) \sqrt n + m\left(\sqrt n + \sqrt V\right)\right)，为线性根号级别。

3. 块状链表

在读入数据后即可一次性完成分块而不需要重新分块的数据结构称为块状数组。而块状数组无法满足在序列中间插入或删除元素的需求，因此块状链表便应运而生。块状链表类似链表，但与链表不同的是块状链表每个节点保存一个长度为 O(\sqrt n) 的线性表。在某个节点插入一个元素后，若该节点保存的线性表长度超过 2 \sqrt n，则将该节点分裂为两个节点；在某个节点删除一个元素后，若该节点与相邻节点大小和小于 \sqrt n，则将它们合并。这样即可保证节点数量和节点大小均为 O(\sqrt n)。

块状链表实质上可以理解为数组和链表这两种线性表的复杂度平衡。它实现了一种动态的块状数组，因此块状链表与块状数组本质上没有太大区别。这里不再给出示例。

4. 二维分块

当需要在平面上进行矩形操作时，序列分块就显得无能为力了。而该分块形式可以实现以下操作：（定义矩形加和矩形查的范围为以 (0,0) 为左下角，(x, y) 为右上角的矩形。O(a)-O(b) 表示修改复杂度为 O(a)，查询复杂度为 O(b)。）

首先将矩形进行以下几种同时存在的分块：

以修改 O(1) 查询 O(\sqrt n)​ 的单点加矩形查为例，一次查询可以划分为下图几种矩形。红色、蓝色、绿色、黄色矩形表示修改矩形中包含的完整的块，并且将修改划分为这些矩形时尽量保证某位置被最大的块覆盖。黑色、灰色矩形为修改矩形中无法包含完整的块的矩形。红色、蓝色、绿色、黄色矩形统称整块，黑色和灰色矩形统称散块。

（这图有地方不太好，比如右上角没必要涂黑，和旁边的灰色一样就行了。）

维护单点加对整块的贡献时直接维护块内和，这显然可以做到 O(1)。当整块查询时，先对红色矩形求和，而红色矩形最多只有 n^{0.25} \times n^{0.25} 个。再对蓝色矩形求和，因为蓝色矩形在 y 轴方向上不超过 \frac{n^{0.75}}{n^{0.5}}=n^{0.25} 个（如果超出，由于划分时尽量保证某位置被最大的块覆盖，则部分蓝色矩形就会变成红色矩形），因此蓝色矩形的数量不超过 n^{0.25} \times n^{0.25} 个。绿色矩形同理。黄色矩形在 x 轴和 y 轴方向上均不超过 \frac{n^{0.75}}{n^{0.5}}=n^{0.25} 个（如果超出，由于划分时尽量保证某位置被最大的块覆盖，则部分黄色矩形就会变成蓝色或绿色矩形），因此黄色矩形的数量不超过 n^{0.25} \times n^{0.25} 个。综上所述，整块查询的复杂度为 O(\sqrt n)。

为了计算散块查询的值，需要利用被修改的点的横纵坐标两两不同的性质，修改时直接记录该点 x 坐标被加上的值。散块查询时枚举纵向散块的 x 值和横向散块的 y 值。由于被修改点横纵坐标两两不同，通过建立从被修改点 y 坐标到 x 坐标的映射，可以由枚举的 y 值判断出是否存在该 y 坐标的被修改点，若存在，还可以得到该点的 x 坐标。 同理也可以由 x 值获得被修改点的 y 坐标。如果枚举的 x 值或 y 值存在被修改点且在查询范围内则计入答案。由于纵向散块在 x 轴方向的长度以及横向散块在 y 轴方向的长度均小于 \sqrt n。因此散块查询的复杂度也为 O(\sqrt n)。于是我们获得了一个能够实现修改 O(1) 查询 O(\sqrt n) 的单点加矩形查的数据结构。

其余三种类型的二维分块原理类似，读者可自行思考。

由于二维分块修改与查询复杂度的不平衡性，二维分块极少单独使用，而是常与其它根号算法或数据结构结合进行根号平衡。二维分块及其与其它根号算法结合的具体示例将在后文中介绍。

5. 树分块

树分块是一种通过模仿序列分块思路，将树分割为多个块，从而完成许多 \text{polylog} 树上算法难以解决的任务或与其它根号算法或数据结构连用以进行根号平衡的算法。树分块算法种类繁多，这里将介绍最为通用的基于 top tree 相关理论的一种树分块算法，一般称为 top cluster 树簇划分。

(1) 基本概念

一个树簇（cluster）是树上的一个连通子树，有至多两个点与外界连接。这两个点称为界点（boundary node），簇中其余的点称为内点（internal node）。两个界点之间的路径称为簇路径（cluster path）。方便起见，本文设每个簇中必有两个界点，称一个簇中深度较浅的界点为上界点，较深的为下界点。

簇是可合并的，也可以将整棵树合并为一个簇。簇的合并过程会形成一个二叉树的结构称这棵树为 top tree。

Top tree 本身的实现对于树分块来说不太重要。但可以借用 top cluster 的理论，建立一种比常见树分块具有更多优秀性质的树分块算法。能够做到对于一棵 n 个点的树和一个块大小 B，将原树划分为 O\left(\frac{n}{B}\right) 个簇，每个簇的大小均为 O(B)。并且使用该算法划分出的簇满足以下性质：

如何实现这个算法？一个自然的想法是先建出 top tree，然后在 top tree 上截取子树。然而 top tree 的构建比较复杂，较难实现。实际上存在一种更加易于实现的静态构建算法。

(2) 算法过程

选取任意节点为根节点，并且强令根节点为一个界点。

从根节点开始 DFS，维护一个栈存储暂时还未归类的边（实际上存的是点，但代表的意义是连向其父亲的边）。当 u 要结束 DFS 时，如果发生以下 3 种情况，则要将栈中的一些边确定为若干个以 u 为上界点的簇。处理完毕后把栈中所有 u 的子树中的节点弹出。

  3. 栈中剩余边（点）的数量大于 B。

下面要解决的问题是：如何合适地将 u 的子树划分为不同的簇，来满足最初的要求。考虑贪心地在栈中选取极长合法前缀作为同一个簇，直到下列情况之一发生：

  2. 新加入一个子树将会使当前簇中有两个下界点。
  3. 新加入一个子树将会使当前簇的大小超过 B。

全部 DFS 结束后，就能得到一种符合要求的划分方案。

(3) 正确性证明

显然上述算法能够保证每个簇的大小均为 O(B)。只需证明划分出的簇的个数为 O\left(\frac{n}{B}\right) 即可。换言之，只需证明上述两个部分各自 3 种情况的发生次数为 O\left(\frac{n}{B}\right) 即可。

对于第一部分：显然情况 1、3 发生的次数为 O\left(\frac{n}{B}\right)。而情况 2 只会发生在由已经找到的界点形成的虚树上，因此也是 O\left(\frac{n}{B}\right) 的。

对于第二部分：显然情况 1、2 只与第一部分的发生次数有关。对于情况 3，考虑将每个发生这种情况时正在划分的簇和当前做到的子树配对。则每对的未归类边数和一定大于 B，从而对数不超过 \frac{n}{B}，因此归于这种情况的簇的数量是 O\left(\frac{n}{B}\right) 的级别。

综上所述，总的划分出簇的个数为 O\left(\frac{n}{B}\right)，大小为 O(B)。符合上面的要求。

树分块及其与其它根号算法结合的具体示例将在后文中介绍。

二、基于分块思想的离线双指针算法——“莫队”算法

莫队算法是一种基于分块思想的离线双指针算法。最初是由 Codeforces 网站上几位用户发明，但仅限于小范围流传且不成体系。后来经过莫涛的整理总结，该算法被公之于众，因此被 OIer 称为莫队算法。后来经过算法竞赛生的集体智慧改造，莫队算法又有了许多变种和扩展。本文将介绍常规莫队算法及其常见变种以及莫队算法在根号平衡上的应用。

1. 常规莫队算法

常规莫队算法用于处理静态区间询问问题，且要求可以由 [l,r] 的答案 O(1) 获得 [l \pm 1, r] 以及 [l, r \pm 1] 的答案。

先对序列以 B 为块长序列分块，记 bel_i 表示第 i 个元素所属块。将询问以 bel_l 为第一关键字，r 为第二关键字升序排序。（其中 r 也可以降序排序。）排序后从 L=1,R=0 开始顺序处理每个询问，连续地移动 L,R 两个指针（本文中称一次移动为向莫队中插入或删除一个元素）转移答案即可。

下面来分析莫队算法的复杂度。对于 bel_l 相同的询问，R 指针的移动总次数为 O(n)，L 指针的单次移动次数为 O(B)。而本质不同的 bel_l 最多只有 O\left(\frac{n}{B}\right) 种，因此 R 指针移动的复杂度为 O\left(\frac{n^2}{B}\right)。设询问次数为 m，则 L 指针移动复杂度为 O(mB)。此外，当两个询问之间的 bel_l 不相同时，L 与 R 指针的移动次数均为 O(n)，这种情况最多会发生块数次即 O\left(\frac{n}{B}\right) 次，因此这部分复杂度仍为 O\left(\frac{n^2}{B}\right)。综上所述，莫队算法的总时间复杂度为 O\left(\frac{n^2}{B}+mB\right)，B 取 \frac{n}{\sqrt m} 时取得最小值 O(n\sqrt m)。

2. 回滚莫队算法

回滚莫队适用于向莫队中插入或删除元素这两个操作中有且只有一个难以实现或其复杂度高于 O(1) ，但按操作顺序撤销最后几次操作（称为回滚）的复杂度为 O(1) 的情况。根据删除困难或插入困难分为只增莫队或只删莫队。这里将介绍只增莫队的具体过程，只删莫队过程类似不再赘述。

仍先对序列以 \frac{n}{\sqrt m} 为块长序列分块，记 bel_i 表示第 i 个元素所属块，ED_i 表示第 i 块的右端点。将询问以 bel_l 为第一关键字，r 为第二关键字升序排序，这里 r 不能降序排序。将所有 bel_l 相同的询问一起处理，首先暴力处理 r \leq ED_{bel_l} 的询问。对于 r>ED_{bel_l} 的询问，从 L=ED_{bel_l}+1,R=ED_{bel_l} 开始。先向右移动 R 指针，由于询问的 r 值升序排序，因此移动 R 指针是只增不删的。然后向左移动 L 指针获得答案。之后撤销 L 指针的移动以及移动 L 指针所产生的插入操作再处理下一个询问。这样即可保证 L 指针在移动时也是只增不删的。

回滚莫队的复杂度证明类似常规莫队，这里不再赘述。时间复杂度为 O(n\sqrt m)。

3. 莫队与扫描线结合

当向莫队中加入或删除一个元素时产生的贡献与整个 [L,R] 区间其它元素相关时，转移答案的复杂度通常会在 O(1) 以上，设为 O(k)。但如果该贡献具有可差分性，可以通过将莫队与扫描线结合，将复杂度由 O(kn\sqrt m) 降为 O(kn + n\sqrt m)。 这种莫队算法一般被称为莫队二次离线。

设 f(i,[l,r]) 表示第 i 个元素能够对 [l,r] 产生的贡献，设 F(i,r)=f(i,[1,r])。以 R 指针右移一次为例，第 R+1 个元素能对答案产生的贡献为 f(R+1,L,R)=F(R+1,R)-F(R+1,L-1)。其中 F(R+1,R) 可以预处理并求前缀和，对于每个询问可以 O(1) 求得。由于莫队的指针移动是连续的，因此在处理第 i 次询问 [l,r] 时所有 R 指针右移的 -F(R+1,L-1) 之和为 -\sum\limits^{r}_{x=R+1} F(x,L-1)。这部分可以在莫队结束后使用扫描线进行处理。具体地，将三元组 (a,b,c)=(R+1,r,-i) 挂载在 L-1 处。执行扫描线时，设扫描到第 i 个元素，先将第 i 个元素加入数据结构（这里需要该数据结构查询复杂度为 O(1)），然后处理挂载在 i 处的三元组，对于每个三元组，暴力地从 a 到 b 查询 F(x,i)，根据 c 的正负给第 |c| 个询问的答案加上或减去该值。由于 b-a 的大小与莫队指针移动的次数相同，因此暴力查询复杂度与常规莫队相同。由于预处理复杂度为 O(kn)，因此莫队二次离线的时间复杂度为 O(kn+n\sqrt m)。

4. 莫队与块状数组结合

由于常规莫队、回滚莫队可以抽象为对一个数据结构进行 O(n\sqrt m) 次修改，O(m) 次查询，而莫队二次离线可以抽象为 O(n) 次修改，O(n\sqrt m) 次查询。因此可分别使用 O(1)-O(\sqrt n) 以及 O(\sqrt n)-O(1) 的数据结构进行复杂度平衡。块状数组正是其中常用的一种。

示例：静态区间数字出现次数 kth（洛谷 P3730 曼哈顿交易）

题目描述：有一个长为 n 的序列 a（1 \leq a_i \leq V），有 m 次询问。定义某数字在区间 [l,r] 的“热度”为其在 [l,r] 的出现次数，每次询问 [l, r] 中第 k 小的“热度”。

目标复杂度：线性根号。

莫队维护 [L,R] 中每个数字的出现次数，然后按照类似区间数值替换区间 kth 的方法维护一个 O(1)-O(\sqrt n) 的值域分块，查询方式亦类似。总时间复杂度 O(n\sqrt m + m\sqrt V)，为线性根号级别。

5. 莫队与二维分块结合

示例：静态带权矩形颜色数（洛谷 P8530 [Ynoi2003] 博丽灵梦）

题目描述：给定一个有 n 个点的二维平面，每个点坐标为 (i,p_i) ，其有权值 a。给定一个长为 n 的数组 b，其下标从 1 到 n。

有 m 次查询，每次查询给定一个矩形 l_1,r_1,l_2,r_2，定义集合 S=\{a_i|l_1\le i\le r_1 \land l_2\le p_i\le r_2\}，求对于集合 S 中所有元素 j，b_j 的和。

目标复杂度：线性根号。

将 a_i 称为“颜色”。考虑一维颜色数的常用 trick，维护第 i 个点上一个同色点的位置 pre_i（不存在上一个同色点则为 0），问题可转化为求 [l,r] 中 pre_i<l 的 i 的个数。现在考虑带权，问题可抽象为：平面上有 n 个带权点 (i,pre_i)，求被 [l,r][0,r) 矩形包含的点权和。由于除 pre_i=0 的情况，i 和 pre_i 均为两两不同的，因此 pre_i \neq 0 的情况可以使用 O(1)-O(\sqrt n) 单点加矩形查的二维分块维护，pre_i = 0 的情况可以直接使用序列分块维护。

现在将这个问题扩展到二维，考虑将点按照 y 坐标排序来降维的思路。对 x 轴进行莫队，对于被加入莫队中的点，按照 y 坐标升序求出 pre_i。因为要进行一个类似排序的操作，插入复杂度将难以做到 O(\log n) 以下，因此考虑只删莫队。通过先建出已排好序的链表，因为只存在删除而不存在插入，因此在链表中删除元素不影响剩余元素在链表中的相对位置。这样删除时即可 O(1) 更新 pre_i，且链表的形式便于回滚。查询时直接查询当前询问的 [l2,r2][0,l2) 矩形包含的点权和即可。

由于这里存在 O(n\sqrt m) 次对二维分块的修改，O(m) 次对二维分块的查询，而这里选用的是 O(1)-O(\sqrt n) 的二维分块，因此总时间复杂度为 O(n\sqrt m+m\sqrt n)，为线性根号级别。

6. 莫队与 top cluster 树分块结合

示例：静态区间树上距离和（洛谷 P6778 [Ynoi2009] rpdq）

题目描述：给定一棵 n 个节点的无根，有边权的树，每个点有个编号，编号为一个 1 \sim n 的排列。

共 m 组询问，每次询问给出 l,r，求所有点编号的二元组 (i,j) 满足 l \le i<j \le r 在树上的距离的和，两个点的距离定义为连接其的简单路径上的所有边的边权和。

目标复杂度：线性根号。

显然可以将问题转化为以下式子：

(r-l)\sum\limits_{i=l}^r dep_i - 2 \times \sum\limits_{i=l}^r \sum\limits_{j=i+1}^r dep_{LCA(i,j)}

前一项可以通过前缀和简单求得。后一项使用莫队算法。设 w_i=dep_i-dep_{fa_i}，f\left(x,[l,r]\right) 表示 \sum\limits_{i=l}^r dep_{LCA(i,x)}。该式可以用以下方法快速求得：将区间 [l,r] 的所有节点到根的链上每个点的 cnt_i + 1，求出 x 到根的链上所有点的 \sum w_i \cdot cnt_i。以 R 指针右移一次为例，可以把贡献差分为 f\left(R+1,[1,R]\right) - f\left(R+1,[1,l-1]\right)。这是一个经典的莫队二次离线的式子，因此使用莫队二次离线算法。需要注意的是一个节点加入后会对自己产生贡献，因此 F(i,i-1) 和 F(i,i) 的前缀和都需要求。

然而直接使用 \text{polylog} 数据结构会使 cnt_i + 1 和查询 \sum w_i \cdot cnt_i 这两部分的复杂度带上 \log。而目标复杂度为线性根号。由于莫队二次离线可以看做对一种数据结构进行 O(n) 次修改和 O(n\sqrt m) 次查询，发现这两者是非常不平衡的，因此使用树分块进行根号平衡。

加入一个节点时，把这个节点到根的路径拆分成以下 3 部分：

  1. 该点到最近簇路径上节点的路径。
  2. 该点的最近簇路径上节点到该簇上界点的路径。
  3. 该簇上界点到根节点的路径。（均为簇路径，可以认为是该簇上界点到根节点在收缩树上的路径。）

维护 val_i 表示节点 i 作为散块被贡献的值，sum1_i 表示每个节点 val_i 的树上前缀和，且簇与簇之间互相独立。val\_clp_v 表示某簇的下界点 v 到其上界点的这条簇路径被贡献的值，用 sum2_v 表示每个界点 val\_clp_v 的收缩树上前缀和。tag_v 表示某个下界点 v 所代表的簇作为整块被贡献的次数。修改时前两部分在原树上暴跳修改，第三部分在收缩树上暴跳修改。跳完之后更新一下 sum1 和 sum2 即可。当 B 取 O(\sqrt n) 时可以保证单次修改复杂度 O(\sqrt n)。查询时直接求 sum1_x + (dep_{near} - dep_{up}) \cdot tag_{down} + sum2_{up} 即可（记 x 为需要查询的节点，near 为 x 的最近簇路径上节点，up 为 x 所在簇的上界点，down 为下界点），显然是单次 O(1) 的。

这样这道题就彻底解决了。总时间复杂度为 O\left(n\left(\sqrt n + \sqrt m\right)\right)，为线性根号级别。

三、根号分治

根号分治是一种通过设置一个阈值 B，将问题划分为 \leq B 和 >B 两个部分分别处理的思想。因为 B 通常等于 \sqrt n,\sqrt m,\sqrt V，故称为“根号分治”。虽然实际上根号分治与传统意义上的分治在代码形式上完全不相似，但它们都运用了将复杂问题分解为多个子问题的思想，因此也可以认为根号分治是一种分治思想。

示例：CF 797E Array Queries

题目描述：给定长度为 n 的序列 a。m 次询问。每次询问给出 p,k。不断地执行操作 p\gets p+a_p+k，直到 p>n 为止。询问操作次数。

目标复杂度：线性根号。

发现本题有以下两种暴力：

  1. 直接暴力模拟。时间复杂度为单次 O\left(\frac{n}{k}\right)。
  2. DP。设 f_{i,j} 表示 p=i,k=j 时的答案，则 f_{i,j}= \begin{cases} 1 & i+a_i+j>n \\ f_{i+a_i+j,j}+1 & i+a_i+j \leq n \end{cases}。因此总时间复杂度为 O(nk_{max})。

由于两者分别在 k 较大和 k 较小时较优，因此考虑根号分治。设根分阈值为 \sqrt n。首先预处理出所有 j\leq \sqrt n 的 f_{i,j}，此部分复杂度为 O(n\sqrt n)。处理询问时，对于 k\leq \sqrt n 的询问，直接查表即可；对于 k > \sqrt n 的询问，直接使用暴力 1 即可，复杂度为单次 O(\sqrt n)。

综上所述，总时间复杂度为 O((n+m)\sqrt n)，为线性根号级别。

1. 根号分治与序列分块结合

由于根号分治和块状数组中经常出现复杂度不平衡。因此根号分治可以和块状数组结合进行根号平衡。

示例：洛谷 P7710 [Ynoi2077] stdmxeypz

题目描述：给你一棵边权为 1，且以 1 为根的有根树，每个点有初始为 0 的点权值，定义两个点的距离为其在树上构成的简单路径的长度，需要支持两种操作：

1 a x y z：把 a 子树中所有与 a 的距离模 x 等于 y 的节点权值加 z。

2 a：查询 a 节点的权值。

目标复杂度：线性根号。

首先需要明确的是，a 子树中所有与 a 的距离模 x 等于 y 的节点就是 a 子树中深度模 x 等于 (dep_a+y)\bmod x（下文设其为 k）的节点。这样就可以把修改转化为将一个点的子树内所有深度模 x 为 k 的节点权值加上 z。

先求出 dfn 序。这样就可以把修改变为对 [dfn_a,dfn_a+size_a-1] 范围内（下文称其为 [l,r]）的点进行一次区间操作。但是因为不能将 [l,r] 范围内的所有值统一加上某数。因此考虑建立一个以 dfn 序为 x 轴，深度为 y 轴的平面直角坐标系。把第 i 个点以 (dfn_i,dep_i) 投射到平面上去。这样就把修改转化为将所有横坐标在 [l,r] 范围内，纵坐标模 x=k 的节点权值全部加上 z。

考虑直接暴力跳纵坐标，将跳到的水平线的 [l,r] 部分全部加上 z。因为 dfn 序与深度不对应的坐标是空着的，没有放点。所以把 [l,r] 的整个部分全部加上 z 不会影响正确性。用某种数据结构维护每个纵坐标对应的水平线。当 x > \sqrt n 时，暴跳的复杂度就是 O(\sqrt n) \times O(Modify) 的。查询时直接单点查询，因此复杂度是 O(1) \times O(Query) 的。其中 O(Modify) 表示该数据结构单次修改的复杂度，O(Query) 表示它单次查询的复杂度。因此使用修改 O(1)，查询 O(\sqrt n) 的序列分块+差分即可达到最优总复杂度，为单次 O(\sqrt n)。

当 x \leq \sqrt n 时，暴跳的时间复杂度可能会直接退化到 O(n)。因此考虑根号分治，将这部分特殊处理。开一个 \sqrt n \times \sqrt n 的另一种数据结构的数组，记为 DS_{i,j}。每次修改对 DS_{x,k} 执行一次让 [l,r] 区间加 z 的操作。然后询问时给答案加上 \sum\limits_{i=1}^{\sqrt n} DS(i,dep_a \bmod i,dfn_a) 即可。修改复杂度为 O(1) \times O(Modify)，询问复杂度为 O(\sqrt n) \times O(Query)。因此使用修改 O(\sqrt n)，查询 O(1) 的序列分块即可达到最优总复杂度，为单次 O(\sqrt n)。

因为这两部分都用到分块，所以可以直接把散块暴力算，整块再分类讨论。

综上所述，时间复杂度 O(m \sqrt n)，为线性根号级别。

2. 根号分治与值域分块结合

示例：可插入集合 mod 某值最小值查询（洛谷 P9809 [SHOI2006] 作业 Homework）

题目描述：给定一个集合为 S，初始为空，你需要执行以下两个操作共 N 次。

  1. 在集合 S 中加入一个新元素，其代号为 X，保证 X 在当前集合中不存在。

  2. 在当前的集合 S 中询问所有元素 \bmod\ Y 最小的值。

目标复杂度：线性根号。

考虑模数 \leq \sqrt V 的部分。此时因为模数只有 O(\sqrt V) 种，考虑直接记录每种模数的答案。单次复杂度为 O(\sqrt V) 修改，O(1) 查询。

考虑模数 > \sqrt V 的部分。由于此时商数的级别为 O(\sqrt V)，考虑直接存储集合 S，询问时枚举商数 i，找到集合中最小的 \geq Y \times i 的值然后减一下即可。因此有 O(n) 次修改，O(n \sqrt V) 次查询。使用 O(\sqrt V) 修改，O(1) 查询的值域分块平衡复杂度。具体地，用 next1_i 表示最小的 \geq i 且同块的数，用 next2_i 表示最小的大于第 i 块最后一个数的数。插入新数时修改所属块的前缀 next1 以及前面所有块的 next2。查询时先查 next1，查不到再查所属块的 next2 即可。

综上所述，总时间复杂度 O(n \sqrt V)，为线性根号级别。

3. 根号分治与莫队结合

由于莫队算法修改与查询次数的不平衡以及在根号分治中经常出现的复杂度不平衡。根号分治也可以和莫队结合进行根号平衡。

示例：静态区间(倍数,因数)二元组计数（洛谷 P5398 [Ynoi2018] GOSICK）

题目描述：有一个序列 a，有 m 次询问，每次询问给一个区间 [l,r]。查询 l \leq i,j\leq r，且 a_i 是 a_j 倍数的二元组 (i,j) 的个数。

目标复杂度：线性根号。

使用莫队二次离线。向莫队中加入一个数会对答案产生它在区间中的因数和倍数数量和的贡献。对于求 F(R+1,R) 前缀和这部分，维护每个数字的出现次数，维护 t_i 表示数字 i 的倍数的出现次数，加入第 i 个数字时直接枚举因数计算 [1,i-1] 中 a_i 的因数数量并更新 t，a_i 的倍数数量可以直接由 t_{a_i} 获得。这部分的复杂度为 O(n\sqrt V)。

对于 -F(R+1,L-1) 这部分，设即将插入的元素为 num，所有数的倍数数量依然可以由枚举 num 的因数来更新。若暴力维护所有数的因数数量，则复杂度为 O\left(\frac{V}{num}\right)，因此考虑以 \sqrt V 为阈值根号分治。

  1. 对于 num > \sqrt V 的情况，直接暴力维护所有数的因数数量。这部分的复杂度为 O(n\sqrt V)。
  2. 对于 num \leq \sqrt V 的情况，从 1 到 \sqrt V 枚举 num。记录 cnt1_i 表示 [1,i] 中 num 的出现次数，cnt2_i 表示 [1,i] 中 num 倍数的出现次数。执行扫描线时，设扫描到第 i 个元素。三元组 (a,b,c) 对答案的贡献的绝对值即为 cnt1_i \times (cnt2_b-cnt2_{a-1})。这部分的复杂度为 O((n+m)\sqrt V)。

综上所述，总时间复杂度为 O(n\sqrt m+(n+m)\sqrt V)，为线性根号级别。

4. 非根号阈值的阈值分治与莫队和 bitset 结合

Bitset 是一种基于状态压缩的数据结构。它的使用与 bool[] 数组类似，但它将多个 bool 变量压缩进一个整形进行存储。使得某些操作的时间复杂度变为 O(\frac{n}{w})。这种性质使得 bitset 易于用莫队维护且有时可以和 B=w 的阈值分治结合。

示例：洛谷 P5313 [Ynoi2011] WBLT

题目描述：给你一个长为 n 的序列，有 m 次查询操作。每次查询操作给定参数 l,r,b，需输出最大的 x，使得存在一个 a，满足 0\leq a<b，使得 a,a+b,a+2b,\ldots,a+(x-1)b 都在区间 [l,r] 内至少出现过一次。如果不存在 [0,b-1] 内的数，则输出 0。

注意：虽然题目名为 WBLT，但实际上本题与其无关。

首先用莫队提取出一段区间中代表数字出现情况的 bitset（0 为未出现，1 为出现过），然后把这个大 bitset 从 0 开始分裂成一些长度为 b 的小 bitset。显然，如果将分裂出来的这些 bitset 全部 and 起来，第一次全为 0 时的小 bitset 的下标（下标从 0 开始）即为本次询问的答案。

这样做当分出的 bitset 数 \leq \frac{V}{w} 时，复杂度能够保证单次操作 O(\frac{V}{w})。但是当分出的 bitset 数过多，即 b < w 时，复杂度就退化到 O(\frac{V}{b})。考虑进行类似根号分治的阈值分治，对 b < w 的情况特殊处理。

由于此时 b < w，考虑一种比较暴力的方法。对不同的 b 各做一次莫队。开一个长为 b 的 bitset 数组。把所有 \bmod b 同余的值除以 b 后放进同一个 bitset 里面。询问时对每个 bitset 求 mex 的最大值即可。时间复杂度 O(n\sum{\sqrt{m_i}})。

因此总的时间复杂度就是 O(\frac{Vm}{w}+n\sum{\sqrt{m_i}})。因为 C++ 中的 std::bitset 不支持分裂操作，所以需要手写 bitset。

四、根号重构

根号重构又称操作分块、时间轴分块。若数据结构难以支持修改但可以在线性时间内重构，则可以考虑根号重构。根号重构将一个复杂问题分成以下三个部分：

  1. 计算未重构部分对答案的贡献。
  2. 计算已重构部分对答案的贡献。
  3. 重构数据结构。

其中只要 1、2 部分的复杂度不高于单次根号，3 部分的复杂度不高于单次线性。即可获得线性根号级别的复杂度。

（这里本来应该出现一些例题比如 3dmq 的。时间太紧没写了。）