我的集训队论文：近最优的在线范围修改查询算法与莫队转移代价上下界

· · 算法·理论

摘要

本文建立了莫队与范围修改查询问题之间的联系，并给出了近最优的在线范围修改查询算法和莫队转移代价上下界的新结果。

1. 前言

范围修改查询问题是一个经典问题，例如 K-D tree 是解决高维矩形修改查询问题的最优范围划分树。

莫队算法（Mo's Algorithm）是一个经典算法，最初被用于解决一类静态区间查询问题，后来被拓展到更多的范围，如树链、双子树、半平面等。我们希望知道各种范围上的莫队算法的转移代价的上下界。

本文将建立上述两个问题的联系，并给出一些新的结果。

本文在第 2,3 节介绍莫队与范围修改查询问题；第 4 节建立了莫队与范围修改查询问题之间的联系；第 5 节给出了一般莫队问题的转移代价忽略对数因子的上下界；第 6 节给出了一种在线范围修改查询问题的代数结构运算次数忽略对数因子最优的算法。此前据 Optimal partition trees[3] 的作者 Timothy M. Chan 所说（注：nzhtl1477 学长在五年前询问得到的结果），在线的圆范围修改查询只有时间复杂度为 \Theta(n^{5/3}) 的做法，而我们得到了一个时间复杂度 \tilde O(n^{3/2}) 的近最优的算法。

2. 莫队算法介绍

莫队算法最初被用来解决这个问题：

例题（小Z的袜子）（有改动） 给出一个序列 a_{1\dots n}，有 m 次询问，每次询问给出一个区间 [l,r]，计数满足 l\le i<j\le r\land a_i=a_j 的二元组 (i,j) 的数量。

假设任意两个询问区间互不相同，即 m\le n^2。

先离线读入所有的询问，然后考虑将询问的顺序重排列并维护一个由当前区间中的所有数组成的可重集合，动态维护这个集合中相等点对的数量。依次扫描重排列后的询问，假设正在考虑第 i>1 个区间 [l_i,r_i]，集合此前维护的是 [l_{i-1},r_{i-1}] 中的数，因此需要删除和加入一些元素。显然，删除和加入的总量不超过 |l_i-l_{i-1}|+|r_i-r_{i-1}|。

维护集合是简单的，只需要维护一个数组 cnt_x 表示 x 的出现次数以及答案。因此，需要使得 |l_1-r_1|+\sum_{i=2}^n |l_i-l_{i-1}|+|r_i-r_{i-1}| 较小。

先介绍一些经典的构造方法。下面称将集合从表示一个区间修改为另一个区间的过程为“转移”或“移动”，过程中删除和加入元素的总量为“转移代价”。

算法 2.1（二维莫队构造方法 1） 取 B=n/\sqrt{m}，将所有询问以 l/B 为第一关键字，r 为第二关键字排序。即对序列分块，先将询问按照左端点所属块归类，每一类再按照右端点排序。

这样左端点的移动要么在一块内，代价不超过 B；要么跨越出块，总代价为 O(n)。对于每一块，右端点的移动代价为 O(n)。因此，总代价为 O(mB+n^2/B)=O(n\sqrt m)。

这是最常用的经典算法。同时可以发现将第偶数个块的右端点由升序排序改为降序可以避免相邻块之间右端点从最右侧直接跳到最左侧的无意义移动，减小常数。

算法 2.2（二维莫队构造方法 2） 考虑一张 m 个点的完全图，点 i 与点 j 之间的边权为其转移代价 |l_i-l_j|+|r_i-r_j|。不难发现找一条最短且遍历了所有点的路径是最优的，即旅行商问题。不难验证边权满足三角不等式，同时将区间看作一个平面上的点 (l_i,r_i)，边权就是曼哈顿距离。此时求出这张图的最小生成树，其 dfs 序的代价一定不超过最小生成树边权和的两倍，所以也不超过最优解的两倍。根据算法 2.1，最优解的代价是 O(n\sqrt m) 的，所以这个构造也是 O(n\sqrt m) 的。

算法 2.3（二维莫队构造方法 3）

来源于 https://codeforces.com/blog/entry/61203。

仍然考虑构造平面路径，直接将点按照其在希尔伯特曲线上的顺序排序。

图2.1：希尔伯特曲线，图片来自原博客

取阈值 B=\log(n/\sqrt{m})，简单分析该分形曲线在 2^B\times 2^B 上层和下层的代价可知转移总代价是 O(n\sqrt m)。

同时，可以给出一组使得转移代价为 \Omega(n\sqrt m) 的数据。这只要使得任意两点之间的边权都是 \Omega(B)，也就是在序列上等间距取 \sqrt m 个点，询问两两点构成的区间即可。

这样就完成了对序列区间范围，即二维莫队的转移代价上下界的分析。

2.1 莫队的定义

定义 2.1（范围） 一个范围是 \{1,2,\dots,n\} 的某些子集构成的集族。

每种范围的莫队都被定义在一类满足某种条件的范围上。

定义 2.2（莫队转移代价） 给定范围中的 m 个集合，将其重排列得到 S_1,S_2,\dots,S_m，其转移代价为 |S_1|+\sum_{i=2}^n |S_{i-1}\oplus S_i|，\oplus 表示对称差。

引理 2.1 考虑 i,j 之间连边为 |S_i\oplus S_j| 的完全图，该图的边权满足三角不等式即 w(i,j)\le w(i,k)+w(k,j)。

证明 这是对称差显然具有的性质。\square

因此直接求出最小生成树就可以得到转移代价达到下界的莫队构造，但时间复杂度过高无法接受。

OI 中将 d 维空间中的偏序关系构成的范围的莫队简称为 d 维莫队，本文将采用这一称呼。OI 中流行的所谓“dsu on tree”技巧就是子树莫队，对序列前缀的扫描线可以视作一维莫队。

接下来考虑一个更复杂的问题。

例题（双子树交莫队）

注：双子树莫队的原题为 https://www.luogu.com.cn/problem/P9988，此处有改动

根据定义，表述为：给出两棵编号 1\sim n 的树，范围是所有子树对中编号的交，即范围中每个集合对应一组 (x,y) 使得该集合是第一棵树 x 子树和第二棵树 y 子树中包含的编号的交。不妨假设给出的集合互不相同。

直接给出一种转移代价上界为 O(n\sqrt m) 的构造方法。其下界 \Omega(n\sqrt m) 是容易构造的。

算法 2.4（双子树（交）莫队构造方法 1）

我们直接构造双子树莫队，即集合是两子树中结点的并。这样在插入和删除结点时，可以判断集合中该编号的存在性。于是这样也保证了子树交的转移代价。

取块长 B=n/\sqrt{m}，利用 Top Cluster 树分块将树分解为若干大小为 \Theta(B) 的块，再将每一块收缩为一个点，得到一棵规模为 \Theta(n/B) 的树。可以证明，对于一棵大小为 l 的树，当给定集合是范围中所有 l^2 个集合时，存在构造方式的转移代价为 O(l^2)。对收缩后的树这样构造的转移代价是 O((n/B)^2\times B)=O(n^2/B)=O(n\sqrt m)，同时每个集合在块内的转移总代价是 O(mB)=O(n\sqrt m)。

考虑证明这一点。对树轻重链剖分，设 x 的重儿子为 son_x，特别地，若 x 不存在重儿子则设 son_x=0；设点 x 的子树大小为 size_x，特别地，设 size_0=0。对于集合 (x,y)，选择 (x,son_y) 和 (son_x,y) 中到其转移代价较小的一个集合向其连边，即选择 size_y-size_{son_y} 和 size_x-size_{son_x} 中较小的一边。这样 l^2 个点构成了一个外向树森林，对每棵树求 dfs 序即可。

此时的转移代价不超过所有 \min(size_y-size_{son_y},size_x-size_{son_x}) 的和的两倍，考虑分析该和的量级。可以将其放缩为任意轻子树对大小的 \min 的和。对于任意 k\ge 0，可以证明 2^k\le size_{v_i}<2^{k+1} 且作为轻儿子的 v_i 不超过 2l/2^k 个。因为若三个 v_i 在同一条祖先链上，则第一个 v_i 的子树大小至少是第三个的两倍，因此其子树大小的和等于每个点到根的 v_i 数量的和，不超过 2l，所以至多有 2l/2^k 个 v_i。

注：在我写原论文的这一段的时候意识不太清醒，把原证明改成了错误的。感谢香蕉同学指出这一点。

2.2 不删除莫队

有时候撤销向集合中加入元素的影响是简单的，但任意删除元素并不简单，此时可以使用不删除莫队。

不删除莫队形如给定范围中的 m 个集合，通过若干次如下操作维护一个集合，使得所有给定的集合都在某一时刻等于维护的动态集合：

  1. 在集合中加入一个元素
  2. 撤销上一次未被撤销的操作 1

转移代价定义为进行的操作次数。

将不删除莫队加入和撤销的过程建一棵树，即每个叶子代表一个集合，每个叶子到根的路径上的所有元素即为该集合。取叶子构成的虚树，就得到了不删除莫队的版本树。

定理 2.1 对某一范围，若存在转移代价为 O(T) 的莫队，则存在转移代价为 O(T\log m) 的不删除莫队。

证明 使用线段树分治算法即可。\square

可以证明在一些情况下该对数因子是必须存在的。如，取 m=n/2，每个集合是序列上形如 [i,i+n/2] 的区间，其莫队的转移代价显然是 O(n)，但其不删除莫队的转移次数下界为 \Omega(n\log n)。

证明 来自 [2]。通过调整，可以说明最优的不删除莫队每个时刻的集合都是一个区间的形式。考虑转移过程中长度为 l\le n/2 的区间的出现次数，由于每个 [i,i+n/2] 的区间中都要包含至少一个长度为 l 的区间，因此相邻两个长度为 l 的区间的左端点之间的距离不超过 n/2-l+1。计算调和级数求和可知转移过程至少包含 \Omega(n\log n) 步。\square

2.3 在线化莫队

有时候询问是在线即需要按顺序处理的，此时可以使用在线化莫队。

在线化莫队形如维护持久化的集合，每个询问都可以进行若干次操作，每次操作在此前某个版本的集合进行修改，生成一个新的版本，其转移代价定义为操作总次数。在一般情况下，需要使用完全持久化数组维护集合，这样会有 O(\log \log n) 的额外代价。

若给在线化莫队加上不删除的限制，即只能往此前某个版本的集合加入元素，此时其转移代价将在某些情况下比在线化莫队或不删除莫队的转移代价高多项式，下面是一个例子。

例题 设 n=m，范围是 \{1,2,\dots,n\} 的所有大小为 n-2 的子集构成的集合族。

显然此时在线化莫队或不删除莫队的转移代价都是 \tilde O(n)，但可以证明：询问一个等概率随机生成（允许重复）的集合序列的在线化不删除莫队的期望代价为 \Omega(n\sqrt{n})。

证明 不妨设当前转移代价不超过 n\sqrt n/4，考虑当前拥有的集合中大小 \ge n-\sqrt{n} 的集合，关注它们之间的转移代价。也即存在一种将它们排列的顺序，每次在前一个集合中加入一些元素再删除一些元素，其删除次数不超过 n\sqrt n/4。每次删除操作会新增至多 \sqrt n 个范围中的集合，使之成为当前集合的超集，从而可以从这个集合转移过来。所以至多有 n^2/4 即不超过一半的范围中的集合可以被大小 \ge n-\sqrt{n} 的集合转移过来，其余集合的转移代价都是 \Omega(\sqrt n)。所以此时随机选择范围中集合的期望代价为 \Omega(\sqrt n)。\square

3. 范围修改查询问题

例题（矩形修改查询） 给定平面上的 n 个点 (x_i,y_i)，每个有初始权值 v_i。你需要维护 m 次操作，每次操作为给出一个矩形，求矩形中所有点的权值和对 2^{64} 取模的值；或给出一个矩形和常数 c，将矩形中所有点的权值乘上 c。

更一般地，将加法与乘法拓展为任意分配双半群。

这个问题最广为人知的解决方法是使用 K-D tree。下面将介绍两种其他的算法。

算法 3.1（四分树） 该结构十分简单，但笔者此前从未得知。笔者发现其在对坐标离散化外的建树复杂度是线性，且结构简明直观，因此具有更强的拓展性。

考虑对 x,y 轴分别分块，即将横/纵坐标排序后，将排序数组以块长为 \sqrt n 分块。这样将平面划分为了 \sqrt n\times \sqrt n 的网格，每个网格中落有一些点，用一棵四分树维护这个 \sqrt n\times \sqrt n 平面。即，一个结点代表一个矩形，其四个儿子为将其从两维的中间切割开的四个小矩形。而递归到单个网格后，可以对网格内部的点任意建树。这样得到了一棵和通常使用的 K-D tree 功能相同但结构不同的树。

对于四分树，可以将其视作点集是 \sqrt n\times \sqrt n 平面上所有整点构成的特殊的 K-D tree，因此在网格上递归的时间复杂度是正确的。但有另一种更好的刻画方式：将四分树每层的结点取出，每层的结点代表的矩形构成一个划分平面的网格，且每层网格的边长取出来是一个等比数列。一个矩形在某一层经过的结点数是与其有交的网格数，即其周长除以网格边长，等比数列求和自然得到其经过的总结点数为 O(\sqrt n)。

而在底层网格内部的点，其所在网格是两行区间加两列区间的形状。而一开始的分块方式保证了每行和每列的网格中点的总和是 O(\sqrt n)，因此底层点递归的时间复杂度也是 O(\sqrt n)。

除排序外建树的时间复杂度是线性的，当然也可以简单地拓展到高维。

沿用范围的定义，可以定义任意范围的修改查询。修改查询问题同样定义在一类范围上。下文中约定 n 为元素个数，m 为修改查询的集合数量总和。

这里给出对范围的进一步定义。

定义 3.1（对偶范围） 对于范围中若干个集合 S_1,S_2,\dots ,S_m，定义其对偶范围：对偶范围包含 n 个集合，\forall 1\le j\le n，第 j 个集合为 S'_j=\{i|j\in S_i\}。

定义 3.2（等价类） 对于范围中若干个集合 S_1,S_2,\dots ,S_m，元素 j,k 同属一个等价类当且仅当 S'_j=S'_k。

定义 3.3（范围的等价类数） 对于一个范围，在其中选取 x 个集合，将得到的不同的 S' 数量的最大值记为 P(x)。

下文中用 P' 表示某个范围的对偶范围的等价类数函数。不失一般性地，设 P(m)=n。

算法 3.2（等价类分治） 等价类分治算法来源于 [1]，是一种解决离线修改查询问题的算法。

考虑维护一个动态森林。森林的结构类似线段树，每个结点维护一个等价类中的信息以及懒标记。过程中会动态地加入一个根连接两棵树，或将一个点的标记下传后删除这个点。（实际上，线段树或平衡树都可以被描述为这个模式。）

每次处理一段长度为 B 的操作序列，对操作序列分治，同时在分治到区间 [l,r] 的时候，森林中每棵树都是一个区间 [l,r] 中集合构造出的等价类。这是因为处理这个区间时，同一个等价类中的元素受到的操作是完全相同的。递归到 [l,mid] 和 [mid+1,r] 时，新建若干个根合并一些此前的等价类，处理完后再将这些根的标记下传并删除。直到递归到 l=r 时只有至多两个等价类，也即森林只有两棵树，作为该集合的那棵树就是我们所想要的了。

总代数结构运算次数为 O(m/B\times(P(B)+2P(B/2)+4P(B/4)+\dots))。

例如解决上述矩形修改查询问题，取 B=\sqrt n，P(x)=O(\min(x^2,n))，所以 (P(B)+2P(B/2)+4P(B/4)+\dots)=O(n)，代数结构运算次数为 O(m/B\times n)=O(m\sqrt n)。而其中合并等价类的过程不增加复杂度，因此时间复杂度相同。

定义 3.4（范围划分树） 定义范围划分树为一类有根二叉 leafy tree。其恰好有 n 个叶子，每个叶子对应范围的集合中 \{1,2\dots,n\} 的元素，即对应一个单元素集合。每个非叶子结点代表其子树中叶子的集合（这集合不一定在范围中）。

一个范围中集合 S 的代价定义为：在树上找到一个最小的包含根的连通块使得连通块的叶子对应集合的并恰好为 S，该连通块的大小。将此连通块的叶子称为这个范围的分解。

定义 3.4.1（离线范围划分树） 根据给出的范围中的集合 S_1,S_2,\dots,S_m 构造的范围划分树，其代价总和定义为 S_1,S_2,\dots,S_m 的代价总和。

定义 3.4.2（在线范围划分树） 给出一个范围，其的一个在线范围划分树的代价定义为范围中所有集合代价的最大值。

如 K-D tree、四分树或线段树都是在线范围划分树；等价类分治不是范围划分树。

4. 莫队与范围修改查询问题的关系

定理 4.1 莫队的转移代价与其对偶范围的离线范围划分树的代价总和在忽略对数因子的情况下相同。

证明 若某一范围存在总代价为 T 的离线范围划分树，那么其叶子按 dfs 序排序就是其对偶范围转移代价为 O(T) 的莫队。因为考虑将在每个范围的分解上挂上这个范围，在 dfs 进入子树时加入，出子树时撤销，就可以发现转移代价不超过 2T。实际上，这给出的是一个不删除莫队。

若某一范围存在总代价为 T 的莫队构造，那么可以得到每个元素在莫队的范围序列中出现的若干个区间，区间个数总和是 O(T)。所以对范围序列建线段树，就是一个对偶范围上总代价为 O(T\log m) 的离线范围划分树。\square

同时还可以发现不删除莫队版本树的概念和其对偶范围的离线范围划分树是相似的，但代价为连通块的叶子个数而非大小，这里可能会产生对数代价。如一维不删除莫队的转移代价为 O(n)，但其对偶范围的前缀范围修改查询问题需要用线段树解决。

线段树分治是时间维上的区间对偶范围的不删除莫队。

根据这一理论，可以给出二维莫队和双子树（交）莫队使用其对偶范围的范围划分树的构造算法。

由于等价类分治并不是范围划分树，所以无法据此构造莫队。

算法 4.1（二维莫队构造方法 4） 序列区间（二维）范围的对偶是平面的矩形范围，其中区间 [l_i,r_i] 对应平面点 (l_i,r_i)，第 i(1\le i\le n) 个矩形的左下角是 (1,i)，右上角是 (i,n)。

于是可以使用 K-D tree 或四分树。但不对 x,y 分块，直接对平面构建四分树并保留范围内存在点的四分树结点的复杂度仍然正确。因为范围中矩形的特殊性，按 \sqrt m\times \sqrt m 划分格子后，每行和每列的格子只会被经过 \sqrt m 次。因此总代价是 O(n\sqrt m)。

注意到四分树存在 dfs 序恰好是希尔伯特曲线！

算法 4.2（双子树交莫队构造方法 2） 这是一种比方法 1 更加简单的做法。

考虑其对偶范围的修改查询：元素是若干双树的点对，对于每个编号，其对应的修改查询集合是所有在两棵树上的点都是其祖先的点对。

考虑对两棵树带权轻重链剖分，每个点的权值为包含这个点的点对数。对于每对重链，若这对重链上存在至少一个点对，则对其建立 K-D tree，横纵坐标为点对在两棵树上距离链顶的距离。最后把 K-D tree 按照重链链顶在 dfs 序中的位置构成的二元组的字典序排序连接起来建线段树，可以得到一棵在线范围划分树。

可以证明：对于一个范围，在其 O(\log^2 m) 对重链（即其在两棵树上到根的重链的笛卡尔积）的 K-D tree 上分解的代价总和为 O(\sqrt m)。根据（带权）轻重链剖分的性质，与自上而下第 i 条重链有交的点对数不超过 m/2^{i-1}。因此在第一棵树的第 i 条重链与第二棵树的第 j 条重链上的点对数不超过 m/\max(2^{i-1},2^{j-1})，也即其 K-D tree 的点数上界。有

\sum_{0\le i,j\le \log m} \sqrt{m/\max(2^{i-1},2^{j-1})}=O(\sqrt m)

从而分解代价总和为 O(\sqrt m)。

5. 莫队的通用构造算法与转移代价的上下界

定理 5.1（莫队转移代价下界） 莫队的转移代价下界为 \Omega(n\max_{1\le i\le n} P'(i)/i)。

证明 设上式在 i=B 时取到最大值。

存在其对偶范围的大小为 B 的集合族（即原范围的元素）满足其能将元素，即原范围的集合划分为 P'(B) 部分。

将这些元素复制 n/B 遍，任意两个等价类之间的转移代价都 \ge n/B。得证。\square

下面将给出一种忽略对数因子代价总和最优的离线范围划分树。

笔者将这类数据结构命名为 RT 树，以纪念笔者的一位朋友。如下的数据结构称为原型 RT 树，原型 RT 树主要用于构造莫队和分析莫队的转移代价，且实现简单。

5.1 原型 RT 树

算法 5.1（原型 RT 树的构造） 初始保留所有的集合。将所有元素代表的叶子结点作为最底层，视作初始的 n 个等价类。

接下来进行若干轮，每轮将每个集合以 1/2 概率保留进入上一层。对每个新的等价类建立结点，将其内部的下层等价类建线段树并将其作为根。直到不存在剩余的集合。

RT 树的示意图：

考虑分析原型 RT 树的代价总和。

类似四分树的分析方法，一个集合在原型 RT 树上递归时，会递归到与之有交但不包含的等价类上，再在以这个等价类为根的线段树上递归。

事实上有：

引理 5.1 对于每个集合以 1/x 的概率保留构成的等价类，一个等价类的代价以高概率不超过 O(cnt\times x\log^2 n)，cnt 表示该等价类内部的下层等价类个数。

证明 考虑线段树叶子的 dfs 序，也就是下层等价类建线段树前的序列顺序。

考虑两个元素位于同一个等价类且恰好包含其中一个的集合个数超过 Cx\ln n 的概率。若有 Cx\ln n 个集合，那么随机选中任何一个都会导致这两个等价类在本层被划分开。没有选中任何一个的概率为 (1-\frac 1 x)^{Cx\ln n}\le n^{-C}。因此根据 union bound，O(n^2) 对元素均不位于同一个等价类或恰好包含其中一个的集合个数不超过 Cx\ln n 是高概率发生的。

注：此处原论文中的分析并不严谨，感谢 Tony2 学长指出这一点。

因此每个集合在 dfs 序上出现和消失的总次数以高概率为 O(cnt\times x \log n)，再加上线段树拆分区间，一个等价类的代价即以高概率不超过 O(cnt\times x\log^2 n)。\square

设第 i 层保留了 c_i 个集合。那么从第 i 层递归到第 i-1 层（设叶子是第 0 层）的总代价就是 O(P(c_{i-1})2^i\log^2 n)。我们知道 c_{i-1}\sim m/2^{i-1}，因此可以将上式写为 (P(c_{i-1})/c_{i-1})\times m\log^2 n/2^{i-1}\times 2^i=O(m\log^2 n(P(c_{i-1})/c_{i-1}))。

但是在构造莫队时，引理 5.1 的证明中线段树带来的对数因子实际上不存在。因此构造莫队的代价以高概率为 O(n\log m\sum_{i\ge 0} P'(c_i)/c_i)，显然也是 O(n\log n\log m\max_{1\le i\le n} P'(i)/i)。

根据概率方法的道理，由于这组构造的代价以高概率为 O(n\log n\log m\max_{1\le i\le n} P'(i)/i)，因此存在构造方法使得实际代价为 O(n\log n\log m\max_{1\le i\le n} P'(i)/i)。结合定理 5.1 给出的下界，可以确定莫队转移代价的上下界。

定理 5.2（莫队之理） 莫队的转移代价为 \tilde \Theta(n\max_{1\le i\le n} P'(i)/i)。

经过测试，该构造可以通过双子树莫队的原题。

这同样给出了同复杂度在线化莫队的构造，只需要找到 P(x)=n，从初始随机保留 x 个集合开始，并预处理每个等价类中任选一个元素对应的集合即可。

例题（圆对偶莫队） 给出平面上的 n 个圆 C_i，范围中的集合 S_j=\{i|(x_j,y_j)\in C_i\}。

这是曾经 open 的莫队构造问题，该问题此前只有将其转化为三维单纯形的代价为 O(nm^{2/3}) 的构造方法，但直接使用利用原型 RT 树的构造算法即可得到一组转移代价为 O(n\sqrt m\log n) 的构造。

随机化带来的对数因子在一些情况下可以被证明必须存在，如任意子集范围的莫队；在一些情况下可以被证明不存在，如高维莫队。因此对此对数因子的分析仍需要研究。

6. 在线范围修改查询算法

引理 6.1（范围修改查询问题的代数结构运算次数下界） 范围修改查询问题的代数结构运算次数的下界为 \Omega(m\max_{1\le i\le m} P(i)/i)。

该引理源于 [1]，原论文中给出的界是取 P(i)=n 的情形，这里做了一点加强。证明只需要将原定理的证明的最后一部分的参数稍加修改。

这也说明了等价类分治在任何情况忽略对数因子的代数结构运算次数最优性。

原型 RT 树难以被简单的重构等方法在线化，且理论上关于下界有高达三个对数因子。这里给出一种在线化、去随机化且理论上关于下界只有两个对数因子的 RT 树。注意这棵树并不符合在线范围划分树的定义，而是一棵动态结构的范围划分树。

6.1 在线化与去随机化的 RT 树

维护一棵动态结构的范围划分树。

沿用类似原型 RT 树的结构，对于第 i 层，维护一个集合族 V_i 满足 |V_i|\le m/2^i，V_0\supset V_1\supset V_2\supset\dots，初始为空。第 i 层的结点即代表 V_i 构成的等价类。而对于每个等价类包含的若干下层等价类结点构成的树，建动态开点线段树的结构，使得其高度不超过 \log n。

注：该线段树可能出现只有一个儿子的结点，所以我们可以认为实际上维护的是压缩线段树，但将结点展开便于分析。

在分解一个范围，从一个等价类遍历如上的动态开点线段树结构向下层递归时，记录递归时的非终止结点数量，将第 i 层的非终止结点数记为 e_i。显然，该层的代数结构运算次数不超过终止结点数，即不超过 e_i+1。

分解后，找到最大的 i，满足 e_i>P(m/2^{i-1})\log n/(m/2^{i+1})，将该范围插入 V_{0,1,\dots ,i}。插入时会进行一些线段树分裂以分裂等价类。

此时大于 i 的层的代数结构运算次数不超过 \log n\sum_{j>i} P(m/2^{j-1})/(m/2^{j+1})，所有操作的此类代价总和不超过 O(m\log n\sum_{i\ge 0} P(m/2^i)/(m/2^i))；不超过 i 的层的代数结构运算次数被线段树分裂控制，不会带来额外贡献。

第 i-1 层至多有 P(m/2^{i-1}) 个等价类（i=0 的情况则认为每个元素本身是一个等价类，即有 n 个等价类），因此线段树的结点总数不超过 P(m/2^{i-1})\log n。线段树分裂会增加至少 e_i 个结点，所以每个 i 作为满足条件的最大的 i 的次数不超过 P(m/2^{i-1})\log n/(P(m/2^{i-1})\log n/(m/2^{i+1}))=m/2^{i+1}。V_i 中的集合只会来自不低于 i 的层，因此有 |V_i|\le \sum_{j\ge i} m/2^{j+1}\le m/2^i，因此每次操作后仍然限制条件！

因此该算法的代数结构运算次数为 \tilde O(m\max_{1\le i\le m} P(i)/i)。

可以看出底层较为特殊。一个优化是并不需要维护多个满足 P(m/2^i)=n 的层，因此可以删去从零开始的若干层。

6.2 在线圆范围修改查询

该 RT 树需要维护树结构上动态的集合分裂，比维护静态集合困难。一些情况下，可以在树结构发生变化时暴力重构。

对于圆，有 P(x)=O(\min(x^2,n))。因此只需要维护 m/2^i\le \sqrt n 的层，这样加入的圆的数量为 \tilde O(m/\sqrt n)。而在递归时，需要判断是否子树中所有点都在圆内或圆外，这相当于给定平面点集合，每次给一平面点，查询距其最近和最远的点，这可以用 Voronoi 图和最远点 Voronoi 图实现，同时需要支持在线平面图点定位，其构造时间复杂度为线性对数。

每次暴力重构最坏情况下要重构整棵树，由于树高为 O(\log n\log m)，重构的时间复杂度即为关于子树大小和的对数，即 \tilde O(n)。

总时间复杂度为 \tilde O(m\sqrt n)。

7. 总结

本文的关键结论是定理 5.2（莫队之理）和存在一种在线代数结构运算次数近最优的数据结构。定理 5.2 确定了任意范围的莫队转移代价的一个较紧的上下界，并给出了一种简单高效的构造算法，将曾经 open 的莫队问题做到了近最优；在线化的 RT 树作为一种代数结构运算次数近最优的范围划分数据结构，将圆范围修改查询问题的时间复杂度做到了近最优，并成为理解任意范围修改查询问题的有力工具。

8. 致谢

感谢 nzhtl1477 学长为本文提供的一些例题与思路，给予我启发。

感谢 ccz181078 学长的帮助，感谢 cyffff、fjy666 同学为本文审稿，感谢 Tony2 学长指出文中随机化的分析不够严谨之处和香蕉同学的指正。

感谢 Timothy M. Chan、莫涛等前辈的贡献。

感谢中国计算机学会提供学习和交流的平台。

感谢伴我走过 OI 之路的所有人。

参考文献

[1] Chengze Cai and Xinlong Li. Offline optimal range query and update algorithm. 2021.

[2] Chengze Cai and Xinlong Li. 数据结构艺术. 2022.

[3] Timothy M. Chan. Optimal partition trees. In 26th Annual Symposium on Computational Geometry, pages 1–10, 2011.