finger-search+启发式合并

约瑟夫用脑玩 · 2022-03-06 16:24:56 · 个人记录

众所周知，普通平衡树，或者是常用 stl 容器 set，在启发式合并的时候是 n\log^2n 的。

但当你听一些 DS 大家吹一些题的解法时，经常听到“Splay 合并单 \log”的说法，这是怎么一回事呢？跟着小编一起来看看吧！

Finger-search

一般情况下，在数据结构中查找某个元素的时间复杂度会表示成关于 n （即数据结构中的元素个数）的函数。

设 d(x, y) 表示两个元素 x, y 在集合中的排名之差，在一些数据结构中，如果查找元素 y 时从节点 x 开始查找，那么时间复杂度就可以优化为关于 d(x, y) 的函数。

在数据结构中从某些特定的节点（如上述的 y，也就是“finger”）开始查找其他元素（如上述的 x），这就是 finger-search 了。

如果被查找的元素与“finger”的排名距离很近，那么查询的效率就会有很大的提升。

生活中的 Finger-search

• 在一个有序数组中，我们可以通过倍增来实现 finger-search，时间复杂度为 O(\log d(x, y)) 。

• Splay 是一种原生地支持 finger-search 的数据结构。我们可以把根节点视为一个“finger”， 那么 Splay 的所有操作其实都是用 finger-search 完成的。

  在一棵 n 个节点上的 Splay 上进行 m 次的插入、删除或 者查找操作的总时间为 O(n+m+\sum_{i=1}^m\log d_i) ，其中 d_i 表示第 i 次操作的元素与第 i−1 次操作的元素在该操作时的排名之差。第 0 次操作的元素可以视为初始的根节点。

  证明较为复杂，限于水平，笔者不会证明，感兴趣的读者可以自行查阅相关资料。

• 两个元素 x, y 在 Treap 上的路径长度是期望 O(\log d(x, y)) 的，因此，在 Treap 上实现 finger-search 时，只需要从给定的节点 x 往上走到 x, y 的最近公共祖先处，然后再往下查找节点 y 。

启发式合并

考虑使用 finger-search 来优化启发式合并：

对于 Splay，只需要把较小的一棵 Splay 中的元素按升序/降序的顺序中插入到另一棵 Splay 中。

对于 Treap，同样把较小的一棵 Treap 中的元素按升序/降序的顺序插入到另一棵 Treap 中，每次插入时从上一个插入的位置开始进行一次 finger-search，找到新元素应插入的位置。

• 附：关于 Treap 优先级不变可能带来的问题的解决办法：

  不存储节点的随机优先级，而是在需要比较优先级时再依据节点的子树大小随机地返回结果。

  例如，当连接两棵 Treap T1, T2 时， T1 的优先级大于 T2 的优先级的概率为 \frac{size(T1)}{ size(T1)+size(T2)} ，那么直接按照这个概率返回优先级的比较结果即可。

假设合并的两棵平衡树大小分别为 n, m(n \ge m) 。那么这样合并时，除了第一次插入的耗时为 O(\log n) 外，其余插入的总耗时为 O(\sum_{i=2}^m\log d_i) ，并且满足 \sum_{i=2}^m d_i\le n。

最劣情况取在所有 d_i 相等，即 d_i=\frac nm，故一次合并的复杂度为 O(m\log\frac nm)。（证明在最后）

考虑合并的总复杂度，这里考虑每个元素的贡献而非每次合并的贡献，同时 Splay 看作连续操作最后形成一棵大小为 n 的 Splay 故不用考虑每次合并时 n 的复杂度。

具体的，将一次合并的复杂度分摊在每个元素头上分析，即 O(m\log\frac nm) 视为每个较小集合的元素都有 O(\log\frac nm) 的贡献。

考虑一个元素在合并中所处集合大小分别为 s_1,s_2,\cdots,s_k，那么其贡献至多为 \sum_{i=2}^k\log\frac{s_i}{s_{i-1}}=\log\prod_{i=2}^k\frac{s_i}{s_{i-1}}=\log s_k=\log n。

总时间复杂度 O(n\log n)。

补：证明

差点忘了/qd