附录：原型 RT 树在应用上的一个简单变种

critnos · 2026-03-18 20:36:22 · 算法·理论

结论：原型 RT 树的变种可以花费 n^{\epsilon} 倍的额外时间求出莫队转移次数的常数倍近似最优解。

我们希望求出一个近似的最小生成树。

取一个常数 k，考虑对原先以 \frac 1 U,U=2^t 概率保留的每一层，做 \frac {\ln n} k 轮，每轮以 \frac 1 U 概率保留每个集合，将每轮保留的集合并起来。注意这里保留不再是从下层保留，而是在所有集合中每轮独立选择。这样对于两个（包含其的集合族）对称差大小为 U 的元素，有 (1-\frac {1} {U})^{Uk\ln n}=n^{-k} 的概率位于同一个等价类。

我们在这一层重复做 3n^k\ln n 次，每次把位于同一个等价类的元素尝试连边。这样对于对称差不超过 U 的集合对，其高概率某一次在同一个等价类；对于对称差大于 U(\frac {2} k+1.01) 的集合对，某次在同一个等价类的概率是 O(n^{-2})。

对最后得到的树求一个 dfs 序即可。