主题 作者
- 09
- 14
- 3
- 文章类型
- 完全原创 —— 自由转载
本文主要介绍 lxl, ccz 的 《Offline Optimal Range Query and Update》
这篇文章就是所谓的 tb5 分治 的出处啦
如果大家打 信息学竞赛 / 算法竞赛，那么你肯定听说过 lxl 的 ynoi ，以及 ccz 的响亮名号
这两位也是洛谷管理员，可以说是国际顶级大脑水平
本文难度较大，基本上是属于偏难的紫题到黑题难度，作为学习笔记与大家分享
tb5 分治这个科技是比较新的，还没有被大规模传颂
它本身是一种 基于离线处理问题的思想，在线做法往往是对信息进行分治，而 tb5 实现了对操作本身进行分治
lxl 明确指出，由于分治本身是有开销的，在某些问题下时间复杂度不一定优秀，在后文可以证明哪些问题是会受到分治复杂度影响的
但是可以证明的是 tb5 分治 在代数结构运算次数上是渐进最优的
bonus:
目前网上有一篇 双log 的 序列问题、区间操作 tb5 实现，本文给出了一种 单log的优化做法，符合 lxl 论文给出的复杂度下界
《Offline Optimal Range Query and Update Algorithm》
Chengze Cai
为了得到这篇论文的原文，我被 lxl 爆了 [imath]10[/imath] 次 [imath]KFC[/imath] 疯狂星期四。
而且我觉得同为作者的 ccz 很可能没有吃到。
而且后来才知道这篇论文是英文的。
这个模型可以证明一个非具体问题的复杂度下界.
范围信息，可以是序列区间，树简单路径，二维平面矩形，高维正交范围，半平面范围，圆范围...
这里讨论的是非具体问题，因此可以在不考虑问题特殊性质的情况下，得到一个下界.
(利用更少的性质，得到一个较可靠的下界)
下面的顺序和原文不完全一样
范围信息是 交换半群 [imath](D, +)[/imath] 中的元素
性质稍后给出
(交换半群性质很好，而且修改操作一般是二元运算，所以往这上面归约?)
一次修改是一个 [imath]M-expr[/imath]，
如果 [imath]a,b[/imath] 都是 [imath]M-expr[/imath], 那么 [imath](a*b)[/imath] 是 [imath]M-expr[/imath]
(两次修改，合起来也表示一类修改)
范围信息是 [imath]D-expr[/imath]，
如果 [imath]a,b[/imath] 都是 [imath]D-expr[/imath], 那么 [imath](a+b)[/imath] 是 [imath]D-expr[/imath]
(两个范围信息，合起来也表示一类范围信息)
如果 [imath]a[/imath] 是 [imath]M-expr[/imath]，[imath]b[/imath] 是 [imath]D-expr[/imath]，那么 [imath](a*b)[/imath] 是一个 [imath]D-expr[/imath]
(范围信息在修改后，依然是一个范围信息)
通过应用有限次上述构造方法，可以归纳出这两种表达式
此外，[imath]*[/imath] 对 [imath]+[/imath] 有分配率，[imath](a+b) * c = a*c + b*c[/imath]
即：对范围信息 [imath](a+b)[/imath] 应用修改 [imath]c[/imath]，等于 [imath]a, b[/imath] 分别应用修改 [imath]c[/imath]
范围信息是 交换半群 [imath](D, +)[/imath] 中的元素
[imath]\forall a,b,c \in M[/imath], 有结合率 [imath](a*b)[I]c = a[/I](b*c)[/imath],
注意，括号不改变执行顺序，修改依然保持次序，先应用 [imath](a*b)[/imath] 这组修改, 即先应用 [imath]a[/imath] 再应用 [imath]b[/imath]
[imath]\forall a,b \in D,c \in M[/imath]，有分配率 [imath](a+b) * c = a*c + b*c[/imath]
对范围信息 [imath](a+b)[/imath] 应用修改 [imath]c[/imath]，等于 [imath]a, b[/imath] 分别应用修改 [imath]c[/imath]
[imath]D \times M \rightarrow D[/imath]，范围信息修改后还是范围信息
定义初始集合 [imath]I_0[/imath]，一个有限集合 [imath]I \subset I_0[/imath]
(比如说序列是一个点集集合)
定义操作集合 [imath]Q \subset 2^{I_0}[/imath] 满足 [imath]I_0 \in Q[/imath]
([imath]2^{I_0}[/imath] 是 操作[imath]Q[/imath] 包含/不包含某个元素)
每个元素有一个初始权值 [imath]d_0 : I \rightarrow D[/imath]
(每个元素的初始权值是一个范围信息)
[imath]n = |I|[/imath] 初始权重的个数, [imath]m[/imath] 是操作次数，和信息学题目的符号一致.
可以定义范围修改和范围查询两个操作，这里给出原文
考虑离线情况下，区间加，区间求和
如果操作的次数不多，那么实际上，某些划分到最细的区间，是可以被整体地视作一个元素的
这些整体满足，对于每个操作，某个整体里的元素要么全都不在，要么全都在这个操作里
进一步地，在平面上画一些点，随便用曲线包裹一些，曲线表示操作，
可以观察到二维平面里，操作划分出的点集等价类
在离线的情况下，我们可以把这个问题优化到 [imath]O(n+ m\log m), if\ \ m < n[/imath] ，我们进行了类似缩点的想法
称这样缩完的整体是一个等价类
在没有操作的情况下，所有元素都可以在一个等价类里，但当操作极多，可能划分出 [imath]n[/imath] 个等价类
每个操作相当于将一些等价类合并起来，
从目前状态[imath]R_1[/imath] 得到操作时的状态 [imath]R_2[/imath] ，
合并过程可以认为是多加一个父节点，这个合并过程可以撤销
也就是可以从 [imath]R_2[/imath] 转移回 [imath]R_1[/imath]
首先是森林，其次是动态的，在维护过程中是认为有根的
比如区间加，区间求和，额外的域有两个，子树和 以及 懒标记
在等价类 [imath]x_1 \dots x_k[/imath] 合并的时候，会加一个父节点 [imath]z[/imath]，我们要保证父节点的域也正确维护
也就是 [imath]z[/imath] 的子树和需要被维护好，具体地说，等于 [imath]\sum_{i=1}^k[/imath] 子树等价类维护的子树和
在撤销合并的时候，我们直接删去父节点 [imath]z[/imath]，但是要保证子节点的域被正确维护
也就是说，[imath]z[/imath] 的懒标记要下传给子等价类
撤销合并的过程中，我们把一个有根树拆成了多颗子有根树
合并出来的森林不需要是二叉树森林，多叉的复杂度也是对的，后面会说
一个想法是分治，我们可以用中点分治的想法处理操作序列 (等于线段树, cdq, 整体二分)
一开始我们有 [imath]m[/imath] 个操作 [imath]q[1:m][/imath]，然后和中点分治做法一样，我们递归地看两个子区间
当进入 [imath]q[1:mid][/imath]，由于操作变少了，相应的等价类划分数量往往会减少(一定不增)
也可以进一步观察到，当在叶子结点，即 [imath]q[x:x][/imath]，只有 [imath]O(1)[/imath] 个等价类
等价类减少，也就是说我们会合并一些等价类，
假设 我们可以以 [imath]O(1)[/imath] 代价找到需要合并的等价类，那么合并的过程可以暴力去做
因为每次进入新的区间，我们只会修改 [imath]O(F(len) - F(len/2))[/imath] 个等价类，
这点可以参考线段树、归并等复杂度
[imath]F(len)[/imath] 定义为包括了 [imath]len[/imath] 个操作的等价类数量，
可以注意到 [imath]len[/imath] 越小 [imath]F(len)[/imath] 越小，是单调的
(但感觉给的这个定义是不严谨的，愉悦地理解一下即可)
同时，另一方面，撤销操作也是更加方便的，因为我们一定是先合并，再撤销
我们只要记录合并了哪些节点，产生了哪些节点，维护一个栈就可以实现撤销
那么，操作次数和合并是一致的
可以得到复杂度 [imath]T(m) = 2T(m/2) + O(F(m))[/imath]
在具体问题里可以用主定理化简
一个有用的观察是，在这个中点分治的过程中，我们分治的是操作
那么依然是先递归到 [imath]q_1[/imath]，然后是 [imath]q_2[/imath]，所以操作顺序是不变的，不用担心修改和查询顺序
一个重要的观察是，动态有根森林，的根，是需要维护好子树信息的
那么我们每次操作的时候，就把区间操作，变成了单点操作 (改/查某个根)
另一个重要的观察是，从这个中点分治结构的父节点，沿简单路径转移到子树上某个节点的过程中
只有合并操作，没有撤销操作，可以思考一下，对理解下面的有用.
一旦可以合并，那么只要记录是如何合并的，反过来撤销即可，但合并哪些等价类呢，这个比较难找
不过 ( l x l ) 给出了一种通用的哈希做法
已知当前操作的区间 [imath]q[l:r][/imath]，对每个操作区间覆盖的 等价类 加上一个随机值 [imath][0,2^\omega][/imath]
网上有一个 双log 的实现，这里加、查用了线段树，导致多了个 log
我想了下，序列信息是可以有线性做法的，哈希，然后差分和前缀一下就行
离线下来询问的端点，哈希地存一下；
扫描线(单指针+哈希)过程里在等价类序列上做差分 + 前缀，就能维护好等价类的权值
这步是 [imath]O(F(len) + len)[/imath] 的，[imath]F(len)[/imath] 是等价类个数，假设哈希表是线性的话
这么做完以后，可以被合并的等价类，必定有相同的哈希值，不可以被合并的，大概率哈希值不同
我们把能进行合并的等价类的代表元进行合并，同时新的代表元 [imath]z[/imath] 进栈
因为权值随机的，认为是不可卡哈希。这样就线性维护完了，假设哈希表是线性的话。
记得维护额外的域上的信息
如果不是序列信息，我就不会线性了，通用做法可能会额外带 [imath]log[/imath] 或者别的，不确定
难点在于在 [imath]O(F(len))[/imath] 时间内给一个询问覆盖的等价类加随机值
注意到，论文中在最后一句话，提到，
"this lower bound is not tight due to extra logarithmic cost in the divide and conquer algorithm."
或者我们看 ppt 里的"....因为分治算法导致的开销更大"
感觉可能指的就是这部分不容易维护
撤销的时候也要维护一下子树域上的信息 (下传)。
可以思考一下撤销的顺序，下传的正确性也是有保证的。
这个中点分治的过程其实和归并比较接近了，所以 [imath]O(n+ m\log m), if\ \ m < n[/imath]
前面介绍了 区间操作 的分治方法可以是线段树，
但是在其他维度，或者其他类型的单纯形范围操作，可能就需要其他的分治方法了，同样也依赖于数据结构
以下数据结构大师 lxl 总结的：
我们需要设计一种点集划分树，每次修改查询都只递归到少数子树中。
不同具体范围的划分树形态非常不同，目前对常见的几种范围有人专门设计了划分树。
序列区间
区间的最优点集划分树为线段树。
操作的时间复杂度为 [imath]O(n+mlogn)[/imath]
[imath]F(k)=\tilde Θ(k)[/imath]，代入我们的下界可以证明这个数据结构是最优的
树上简单路径
区间的最优点集划分树为静态 LCT，top tree，点分树 等
操作的时间复杂度为 [imath]O(n+mlogn)[/imath]
[imath]F(k)=\tilde Θ(k)[/imath]，代入我们的下界可以证明这个数据结构是最优的
二维平面矩形
二维平面矩形的最优划分树为 KDT
操作的时间复杂度为 [imath]O(n+msqrtn)[/imath]
[imath]F(k)=\tilde Θ(k^2)[/imath]，代入我们的下界可以证明这个数据结构是最优的
高维正交范围
高维正交范围的最优划分树为 KDT。
对 [imath]d[/imath] 维的情况，操作的时间复杂度为 [imath]O(n+mn^(1-1/d))[/imath]
[imath]F(k)=\tilde Θ(k^d)[/imath]，代入我们的下界可以证明这个数据结构是最优的
高维满点集正交范围
高维满点集正交范围的最优划分树为 KDT，四分树。
对 [imath]d[/imath] 维的情况，操作的时间复杂度为 [imath]O(n^d+mn^(d-1))[/imath]
[imath]F(k)=\tilde Θ(k^d)[/imath]，代入我们的下界可以证明这个数据结构是最优的
二维半平面
KDT 复杂度是错的
圆之类的范围 KDT 也很好卡
四分树是一种比暴力更优的半平面划分树
每次通过两条斜线将平面点集均分为 4 份
进行半平面修改查询时只会递归进 4 个儿子中的 3 个
[imath]T(n)=3T(n/4)[/imath]，解得 [imath]T(n)=O(n^{0.79})[/imath]。
时间复杂度为 [imath]O(n+mn^{0.79})[/imath]
六分树是一种比四分树更优的半平面划分树。
每次通过三条斜线将平面点集均分为 6 份。
进行半平面修改查询时只会递归进 6 个儿子中的 4 个。
[imath]T(n)=4T(n/6)[/imath]，解得 [imath]T(n)=O(n^{0.77})[/imath]。
时间复杂度为 [imath]O(n+mn^{0.77})[/imath]。
建树可以用一种类梯度下降的方法
Optimal Partition Tree 是最优的二维平面单纯型范围修改查询数据结构
即存在一种划分点集的方法，使得任何二维单纯型可以用 [imath]O(sqrtn)[/imath] 个子树所表示的点集的和表示
这个数据结构常数较大并且难以实现。
[imath]F(k)=Θ(k^2)[/imath]，代入我们的下界可以证明这个数据结构是最优的
高维单纯型
Optimal Partition Tree 可以拓展到高维单纯型范围上，同时保证理论最优。
对 d 维的情况，操作的时间复杂度为 [imath]O(n+mn^{(1-1/d)})[/imath]。
[imath]F(k)=Θ(k^d)[/imath]，代入我们的下界可以证明这个数据结构是最优的
圆范围
二维的圆范围可以看做是特殊的三维半空间范围。
设圆方程为 [imath](x-a)^2+(y-b)^2≤c[/imath]，可以将平面上的点 (d,e) 转换为三维点 [imath](d,e,d^2+e^2)[/imath]，圆转换为半空间 [imath]x^2-2ax+a^2+y^2-2by+b^2≤c[/imath]，即 [imath](-2a)x+(-2b)y+1(x^2+y^2)≤-a^2-b^2+c[/imath]，即半空间一侧点。
这里的特殊条件是转换后空间中点全部在一个抛物面上，因为第三维的坐标为前两维的坐标的二次函数。
圆范围
lxl 见过的已有的最优圆范围划分树为使用上述方法将圆转换为半空间后使用 Optimal Partition Tree。
这里和我们算法能达到的上界，以及能证明的下界不符。
对于平面上的 k 个圆，任意两个圆最多有 2 个交点，因为这里是平面图的结构，所以点数和面数同阶，所以 [imath]F(k)=Θ(k^2)[/imath]
点集划分树的优势
在范围查询问题上，基于好的点集划分树的算法可以比我们的最优范围修改查询算法更优
能在线
后面的旋转扫描线没看懂，我再去学学
这篇文章就是所谓的 tb5 分治 的出处啦
如果大家打 信息学竞赛 / 算法竞赛，那么你肯定听说过 lxl 的 ynoi ，以及 ccz 的响亮名号
这两位也是洛谷管理员，可以说是国际顶级大脑水平
本文难度较大，基本上是属于偏难的紫题到黑题难度，作为学习笔记与大家分享
tb5 分治这个科技是比较新的，还没有被大规模传颂
它本身是一种 基于离线处理问题的思想，在线做法往往是对信息进行分治，而 tb5 实现了对操作本身进行分治
lxl 明确指出，由于分治本身是有开销的，在某些问题下时间复杂度不一定优秀，在后文可以证明哪些问题是会受到分治复杂度影响的
但是可以证明的是 tb5 分治 在代数结构运算次数上是渐进最优的
bonus:
目前网上有一篇 双log 的 序列问题、区间操作 tb5 实现，本文给出了一种 单log的优化做法，符合 lxl 论文给出的复杂度下界
《Offline Optimal Range Query and Update Algorithm》
Chengze Cai
- Department of Computer Science and Technology, Tsinghua University, China
- Department of Computer Science and Technology, Tsinghua University, China
0 - 首先介绍一下，lxl 之原罪
为了得到这篇论文的原文，我被 lxl 爆了 [imath]10[/imath] 次 [imath]KFC[/imath] 疯狂星期四。
而且我觉得同为作者的 ccz 很可能没有吃到。
而且后来才知道这篇论文是英文的。
1 - 观后感和不存在的笔记
1-1 大概
范围信息是一个交换半群，修改信息是一个半群，这两个半群合起来成为双半群模型，这个模型可以证明一个非具体问题的复杂度下界.
范围信息，可以是序列区间，树简单路径，二维平面矩形，高维正交范围，半平面范围，圆范围...
这里讨论的是非具体问题，因此可以在不考虑问题特殊性质的情况下，得到一个下界.
(利用更少的性质，得到一个较可靠的下界)
下面的顺序和原文不完全一样
1-2 定义为双半群模型
修改是 半群 [imath](M, *)[/imath]中的元素范围信息是 交换半群 [imath](D, +)[/imath] 中的元素
性质稍后给出
(交换半群性质很好，而且修改操作一般是二元运算，所以往这上面归约?)
1-3 在半群基础上约定表达式
修改可以归纳为一个 [imath]M-expr[/imath] 表达式 ，范围信息可以归纳为一个 [imath]D-expr[/imath] 表达式 ，具体如下:一次修改是一个 [imath]M-expr[/imath]，
如果 [imath]a,b[/imath] 都是 [imath]M-expr[/imath], 那么 [imath](a*b)[/imath] 是 [imath]M-expr[/imath]
(两次修改，合起来也表示一类修改)
范围信息是 [imath]D-expr[/imath]，
如果 [imath]a,b[/imath] 都是 [imath]D-expr[/imath], 那么 [imath](a+b)[/imath] 是 [imath]D-expr[/imath]
(两个范围信息，合起来也表示一类范围信息)
如果 [imath]a[/imath] 是 [imath]M-expr[/imath]，[imath]b[/imath] 是 [imath]D-expr[/imath]，那么 [imath](a*b)[/imath] 是一个 [imath]D-expr[/imath]
(范围信息在修改后，依然是一个范围信息)
通过应用有限次上述构造方法，可以归纳出这两种表达式
此外，[imath]*[/imath] 对 [imath]+[/imath] 有分配率，[imath](a+b) * c = a*c + b*c[/imath]
即：对范围信息 [imath](a+b)[/imath] 应用修改 [imath]c[/imath]，等于 [imath]a, b[/imath] 分别应用修改 [imath]c[/imath]
1-4 双半群性质
修改是 半群 [imath](M, *)[/imath]中的元素范围信息是 交换半群 [imath](D, +)[/imath] 中的元素
[imath]\forall a,b,c \in M[/imath], 有结合率 [imath](a*b)[I]c = a[/I](b*c)[/imath],
注意，括号不改变执行顺序，修改依然保持次序，先应用 [imath](a*b)[/imath] 这组修改, 即先应用 [imath]a[/imath] 再应用 [imath]b[/imath]
[imath]\forall a,b \in D,c \in M[/imath]，有分配率 [imath](a+b) * c = a*c + b*c[/imath]
对范围信息 [imath](a+b)[/imath] 应用修改 [imath]c[/imath]，等于 [imath]a, b[/imath] 分别应用修改 [imath]c[/imath]
[imath]D \times M \rightarrow D[/imath]，范围信息修改后还是范围信息
定义初始集合 [imath]I_0[/imath]，一个有限集合 [imath]I \subset I_0[/imath]
(比如说序列是一个点集集合)
定义操作集合 [imath]Q \subset 2^{I_0}[/imath] 满足 [imath]I_0 \in Q[/imath]
([imath]2^{I_0}[/imath] 是 操作[imath]Q[/imath] 包含/不包含某个元素)
每个元素有一个初始权值 [imath]d_0 : I \rightarrow D[/imath]
(每个元素的初始权值是一个范围信息)
[imath]n = |I|[/imath] 初始权重的个数, [imath]m[/imath] 是操作次数，和信息学题目的符号一致.
可以定义范围修改和范围查询两个操作，这里给出原文
range update：
given [imath]q_t ∈ Q[/imath] and [imath]f_t ∈ M[/imath],
define [imath]d_t(x) = d_{t−1}(x) ∗ f_t[/imath] for [imath]x ∈ q_t[/imath], otherwise [imath]d_t(x) = d_{t−1}(x)[/imath].
range query:
given [imath]q_t ∈ Q[/imath],
define [imath]d_t(x) = d_{t−1}(x)[/imath] for all [imath]x ∈ I[/imath], and the answer is [imath]\sum_{x∈q_t} d_t(x)[/imath]
given [imath]q_t ∈ Q[/imath] and [imath]f_t ∈ M[/imath],
define [imath]d_t(x) = d_{t−1}(x) ∗ f_t[/imath] for [imath]x ∈ q_t[/imath], otherwise [imath]d_t(x) = d_{t−1}(x)[/imath].
range query:
given [imath]q_t ∈ Q[/imath],
define [imath]d_t(x) = d_{t−1}(x)[/imath] for all [imath]x ∈ I[/imath], and the answer is [imath]\sum_{x∈q_t} d_t(x)[/imath]
1-5 离线与等价类
显然，区间加，区间求和，线段树可以在线地做到 [imath]O(n+ m\log n)[/imath]考虑离线情况下，区间加，区间求和
如果操作的次数不多，那么实际上，某些划分到最细的区间，是可以被整体地视作一个元素的
这些整体满足，对于每个操作，某个整体里的元素要么全都不在，要么全都在这个操作里
进一步地，在平面上画一些点，随便用曲线包裹一些，曲线表示操作，
可以观察到二维平面里，操作划分出的点集等价类
在离线的情况下，我们可以把这个问题优化到 [imath]O(n+ m\log m), if\ \ m < n[/imath] ，我们进行了类似缩点的想法
称这样缩完的整体是一个等价类
在没有操作的情况下，所有元素都可以在一个等价类里，但当操作极多，可能划分出 [imath]n[/imath] 个等价类
1-6 动态有根森林
初始分成 [imath]n[/imath] 个等价类，视作一个节点，初始状态下是 [imath]n[/imath] 个孤立的点/树，即森林每个操作相当于将一些等价类合并起来，
从目前状态[imath]R_1[/imath] 得到操作时的状态 [imath]R_2[/imath] ，
合并过程可以认为是多加一个父节点，这个合并过程可以撤销
也就是可以从 [imath]R_2[/imath] 转移回 [imath]R_1[/imath]
首先是森林，其次是动态的，在维护过程中是认为有根的
1-7 域 和 动态有根森林
操作范围信息，往往使用懒标记，文章认为懒标记是节点/等价类上 额外的域比如区间加，区间求和，额外的域有两个，子树和 以及 懒标记
在等价类 [imath]x_1 \dots x_k[/imath] 合并的时候，会加一个父节点 [imath]z[/imath]，我们要保证父节点的域也正确维护
也就是 [imath]z[/imath] 的子树和需要被维护好，具体地说，等于 [imath]\sum_{i=1}^k[/imath] 子树等价类维护的子树和
在撤销合并的时候，我们直接删去父节点 [imath]z[/imath]，但是要保证子节点的域被正确维护
也就是说，[imath]z[/imath] 的懒标记要下传给子等价类
撤销合并的过程中，我们把一个有根树拆成了多颗子有根树
合并出来的森林不需要是二叉树森林，多叉的复杂度也是对的，后面会说
1-8 不想写了，看笔记吧
2 - 笔记与其他内容
2-1 维护加删过程中的等价类
首先，前提是可以离线所有操作一个想法是分治，我们可以用中点分治的想法处理操作序列 (等于线段树, cdq, 整体二分)
一开始我们有 [imath]m[/imath] 个操作 [imath]q[1:m][/imath]，然后和中点分治做法一样，我们递归地看两个子区间
当进入 [imath]q[1:mid][/imath]，由于操作变少了，相应的等价类划分数量往往会减少(一定不增)
也可以进一步观察到，当在叶子结点，即 [imath]q[x:x][/imath]，只有 [imath]O(1)[/imath] 个等价类
等价类减少，也就是说我们会合并一些等价类，
假设 我们可以以 [imath]O(1)[/imath] 代价找到需要合并的等价类，那么合并的过程可以暴力去做
因为每次进入新的区间，我们只会修改 [imath]O(F(len) - F(len/2))[/imath] 个等价类，
这点可以参考线段树、归并等复杂度
[imath]F(len)[/imath] 定义为包括了 [imath]len[/imath] 个操作的等价类数量，
可以注意到 [imath]len[/imath] 越小 [imath]F(len)[/imath] 越小，是单调的
(但感觉给的这个定义是不严谨的，愉悦地理解一下即可)
同时，另一方面，撤销操作也是更加方便的，因为我们一定是先合并，再撤销
我们只要记录合并了哪些节点，产生了哪些节点，维护一个栈就可以实现撤销
那么，操作次数和合并是一致的
可以得到复杂度 [imath]T(m) = 2T(m/2) + O(F(m))[/imath]
在具体问题里可以用主定理化简
一个有用的观察是，在这个中点分治的过程中，我们分治的是操作
那么依然是先递归到 [imath]q_1[/imath]，然后是 [imath]q_2[/imath]，所以操作顺序是不变的，不用担心修改和查询顺序
一个重要的观察是，动态有根森林，的根，是需要维护好子树信息的
那么我们每次操作的时候，就把区间操作，变成了单点操作 (改/查某个根)
另一个重要的观察是，从这个中点分治结构的父节点，沿简单路径转移到子树上某个节点的过程中
只有合并操作，没有撤销操作，可以思考一下，对理解下面的有用.
2-2 找到需要合并的等价类
一旦可以合并，那么只要记录是如何合并的，反过来撤销即可，但合并哪些等价类呢，这个比较难找
不过 ( l x l ) 给出了一种通用的哈希做法
已知当前操作的区间 [imath]q[l:r][/imath]，对每个操作区间覆盖的 等价类 加上一个随机值 [imath][0,2^\omega][/imath]
网上有一个 双log 的实现，这里加、查用了线段树，导致多了个 log
我想了下，序列信息是可以有线性做法的，哈希，然后差分和前缀一下就行
离线下来询问的端点，哈希地存一下；
扫描线(单指针+哈希)过程里在等价类序列上做差分 + 前缀，就能维护好等价类的权值
这步是 [imath]O(F(len) + len)[/imath] 的，[imath]F(len)[/imath] 是等价类个数，假设哈希表是线性的话
这么做完以后，可以被合并的等价类，必定有相同的哈希值，不可以被合并的，大概率哈希值不同
我们把能进行合并的等价类的代表元进行合并，同时新的代表元 [imath]z[/imath] 进栈
因为权值随机的，认为是不可卡哈希。这样就线性维护完了，假设哈希表是线性的话。
记得维护额外的域上的信息
如果不是序列信息，我就不会线性了，通用做法可能会额外带 [imath]log[/imath] 或者别的，不确定
难点在于在 [imath]O(F(len))[/imath] 时间内给一个询问覆盖的等价类加随机值
注意到，论文中在最后一句话，提到，
"this lower bound is not tight due to extra logarithmic cost in the divide and conquer algorithm."
或者我们看 ppt 里的"....因为分治算法导致的开销更大"
感觉可能指的就是这部分不容易维护
撤销的时候也要维护一下子树域上的信息 (下传)。
可以思考一下撤销的顺序，下传的正确性也是有保证的。
这个中点分治的过程其实和归并比较接近了，所以 [imath]O(n+ m\log m), if\ \ m < n[/imath]
2-3 然后
伟大的 ( l x l ) 证明了一下，这个做法，在 代数结构运算次数 上是渐进最优的2-4 单纯形范围操作对应的点集划分树、旋转扫描线
lxl 在这部分前有一段证明，简单来说，就是，不考虑问题的特殊性质，这个双半群结构可以做到:前面介绍了 区间操作 的分治方法可以是线段树，
但是在其他维度，或者其他类型的单纯形范围操作，可能就需要其他的分治方法了，同样也依赖于数据结构
以下数据结构大师 lxl 总结的：
我们需要设计一种点集划分树，每次修改查询都只递归到少数子树中。
不同具体范围的划分树形态非常不同，目前对常见的几种范围有人专门设计了划分树。
序列区间
区间的最优点集划分树为线段树。
操作的时间复杂度为 [imath]O(n+mlogn)[/imath]
[imath]F(k)=\tilde Θ(k)[/imath]，代入我们的下界可以证明这个数据结构是最优的
树上简单路径
区间的最优点集划分树为静态 LCT，top tree，点分树 等
操作的时间复杂度为 [imath]O(n+mlogn)[/imath]
[imath]F(k)=\tilde Θ(k)[/imath]，代入我们的下界可以证明这个数据结构是最优的
二维平面矩形
二维平面矩形的最优划分树为 KDT
操作的时间复杂度为 [imath]O(n+msqrtn)[/imath]
[imath]F(k)=\tilde Θ(k^2)[/imath]，代入我们的下界可以证明这个数据结构是最优的
高维正交范围
高维正交范围的最优划分树为 KDT。
对 [imath]d[/imath] 维的情况，操作的时间复杂度为 [imath]O(n+mn^(1-1/d))[/imath]
[imath]F(k)=\tilde Θ(k^d)[/imath]，代入我们的下界可以证明这个数据结构是最优的
高维满点集正交范围
高维满点集正交范围的最优划分树为 KDT，四分树。
对 [imath]d[/imath] 维的情况，操作的时间复杂度为 [imath]O(n^d+mn^(d-1))[/imath]
[imath]F(k)=\tilde Θ(k^d)[/imath]，代入我们的下界可以证明这个数据结构是最优的
二维半平面
KDT 复杂度是错的
圆之类的范围 KDT 也很好卡
四分树是一种比暴力更优的半平面划分树
每次通过两条斜线将平面点集均分为 4 份
进行半平面修改查询时只会递归进 4 个儿子中的 3 个
[imath]T(n)=3T(n/4)[/imath]，解得 [imath]T(n)=O(n^{0.79})[/imath]。
时间复杂度为 [imath]O(n+mn^{0.79})[/imath]
六分树是一种比四分树更优的半平面划分树。
每次通过三条斜线将平面点集均分为 6 份。
进行半平面修改查询时只会递归进 6 个儿子中的 4 个。
[imath]T(n)=4T(n/6)[/imath]，解得 [imath]T(n)=O(n^{0.77})[/imath]。
时间复杂度为 [imath]O(n+mn^{0.77})[/imath]。
建树可以用一种类梯度下降的方法
Optimal Partition Tree 是最优的二维平面单纯型范围修改查询数据结构
即存在一种划分点集的方法，使得任何二维单纯型可以用 [imath]O(sqrtn)[/imath] 个子树所表示的点集的和表示
这个数据结构常数较大并且难以实现。
[imath]F(k)=Θ(k^2)[/imath]，代入我们的下界可以证明这个数据结构是最优的
高维单纯型
Optimal Partition Tree 可以拓展到高维单纯型范围上，同时保证理论最优。
对 d 维的情况，操作的时间复杂度为 [imath]O(n+mn^{(1-1/d)})[/imath]。
[imath]F(k)=Θ(k^d)[/imath]，代入我们的下界可以证明这个数据结构是最优的
圆范围
二维的圆范围可以看做是特殊的三维半空间范围。
设圆方程为 [imath](x-a)^2+(y-b)^2≤c[/imath]，可以将平面上的点 (d,e) 转换为三维点 [imath](d,e,d^2+e^2)[/imath]，圆转换为半空间 [imath]x^2-2ax+a^2+y^2-2by+b^2≤c[/imath]，即 [imath](-2a)x+(-2b)y+1(x^2+y^2)≤-a^2-b^2+c[/imath]，即半空间一侧点。
这里的特殊条件是转换后空间中点全部在一个抛物面上，因为第三维的坐标为前两维的坐标的二次函数。
圆范围
lxl 见过的已有的最优圆范围划分树为使用上述方法将圆转换为半空间后使用 Optimal Partition Tree。
这里和我们算法能达到的上界，以及能证明的下界不符。
对于平面上的 k 个圆，任意两个圆最多有 2 个交点，因为这里是平面图的结构，所以点数和面数同阶，所以 [imath]F(k)=Θ(k^2)[/imath]
点集划分树的优势
在范围查询问题上，基于好的点集划分树的算法可以比我们的最优范围修改查询算法更优
能在线
后面的旋转扫描线没看懂，我再去学学
最后编辑：