y-fast trie

· · 个人记录

时间 O(\log \log w)，空间 O(n) 插入，删除，查询存在性，查询前后继，查询最大最小值的数据结构。

灵活性比 vEB 要好，常数目测和 vEB 差不多。

时隔一个月，终于来填坑了。

从前有一位老哥，在研究与 vEB 数时间复杂度相同的，支持插入删除，最大最小，前后继查询的数据结构。他盯上了 01 trie 这么一个常见的数据结构。

他对 01 trie 做了一些简单的改造，并起名为 x-fast trie。x-fast trie 对于所有插入的数维护了一条链表；对于 trie 上所有节点和其对应权值间构建了一个哈希表（让我们假设这是一个“完美”哈希表，即复杂度为 O(1)）；对于每个节点维护最大最小值（直接指向它们在链表上的位置）。

让我们看看这个原型能做到什么功能。

插入，删除：x-fast trie 上暴力进行，复杂度 O(\log w)。

前后继：采取二分法二分出这个值最大的前缀，使得其存在于 x-fast trie 上。容易发现，这个前缀对应的节点一定至多有一个儿子。特判没有儿子的情况。随后使用节点上记录的 \min 或者 \max 快速跳转即可。复杂度 O(\log \log w)。

最大最小值：O(1)。

我们很不满意，因为它并没有达到我们期望的目标。复杂度瓶颈来自于插入删除部分，即 trie 树本身的缺陷。既然 trie 是有极限的，那我们就不能只用 trie 了。底层分块，堂堂登场！

现在开始 y-fast trie 的介绍。y-fast trie 仍然需要一棵 01 trie，但这次这个 trie 叶子上挂着的不再是单个值，而是一个大小为 O(\log w) 的平衡树（必须是严格复杂度的，比如红黑树就是很好的）。

当然，这个平衡树在外层 trie 里有一个挂的地方，我们称为“代表元素”。很神秘的是，代表元素并不一定需要在红黑树之内，但它必须满足其大于等于这一个红黑树的最大元素且小于下一个红黑树的最小元素。

除此之外，与 x-fast trie 的结构没有多少不同。我们再次考虑一下那一些操作的复杂度，这次就从我们已经获得了成功的前后继开始吧（以后继为例）。

通过上一次的方法在外层 trie 中找到第一个大于等于询问值的代表元素。由于代表元素的性质，这个值的后继必定在这一代表元素对应的红黑树里，由于红黑树的大小很小，暴力找复杂度是对的。复杂度仍然是 O(\log \log w)。

插入删除：找到对应代表元素，在红黑树里删掉它。O(\log \log w)。（这里请读者注意，若代表元素原本存在于集合内，删除后代表元素可能不再处于集合中，但代表元素的规定仍然被满足，这也是我们进行如上约定的原因）。

最大最小值：O(1)。

我们惊喜地发现，我们是不是就做好了？实际实现时，我们会发现一个问题：我们找不到一个合适的方式保证红黑树大小永远是某个定值，也就是说，我们必须给其大小一个周旋的空间。

不妨进行如下规定：任何红黑树的大小必须处于 {1 \over 2} \log w 和 2\log w 中间。那么在插入删除时进行动态调整即可。

插入时：如果超过 2\log n，裂成两半。

删除时：如果小于 {1 \over 2} \log n，找前面或者后面的合并（前提是存在前面或者后面，毕竟一开始也会经历这个阶段），如果大小又太大了，就再分裂一次。

由于单次合并或分裂复杂度为 O(\log w)，同时至少经过 O(\log w) 次操作才会触发一次分裂或合并，因此复杂度可以被均摊掉。

综上所述，一个天生支持动态开点，易于理解（不需要 vEB 那样逆天的 lazytag 和分讨)，常数也不算很大（照样跑不过朴素 01 trie，别想了）的优秀复杂度数据结构就诞生了。

参考代码。