y-fast trie 简介

· · 个人记录

推荐阅读。看了这个东西之后决定来写个学习笔记。实际上比想象中的清纯。

y-fast trie 是一种使用线性空间，O(\log\omega) 时间支持插入，删除，查最大值，查最小值，查前驱，查后继，查找的数据结构，其中 \omega=64。

我们将分两部分介绍这个东西。

  1. x-fast trie

y-fast trie 的前身，或者说本体。

x-fast trie 是一种使用 O(n\omega) 空间，O(\log\omega) 时间支持查最大值，查最小值，查前驱，查后继，O(\omega) 时间插入，删除，O(1) 查找的数据结构，其中 \omega=64。

首先我们对所有存进来的值维护一个有序链表。十分显然，现在我们要做的事情变成了这样：O(\log\omega) 时间支持查和给定数排名差不超过一的任意一个数，O(\omega) 时间插入，删除，O(1) 查存在性。

然后我们 x-fast trie 的本质是字典树，然后每一层维护了所有节点（对应二进制前缀）的哈希表（前缀映射到节点）。对于插入和删除我们考虑先调前驱后继维护好链表，然后就是字典树板板。我们现在实际上只需要解决 O(\log\omega) 时间支持查和给定数排名差不超过一的任意一个数了。

考虑通过乌姆尼克迭代法求出给定数在 trie 上匹配的最长前缀。如果我们直接找到了 x 那就做完了，否则一定是这个点有俩儿子但只有其中一个儿子有值。那我们再对所有没有左子树的点存它右子树的最小值，没有右子树的点存它左子树的最大值，然后就做完了。

（当然有一个摆子方法是对每个点都维护子树内的最小值和最大值，应该也是可以的。）

  1. y-fast trie

底层分块高光时刻。

考虑把元素按 O(\omega) 分块（需要保证每一块都是排名连续的若干数，要是操作破坏了这一性质就重构），块间 x-fast trie，块内平衡树。然后每一块出一个代表元素。这个代表元素不一定要在块里，但它需要满足比下一块的最小值和下一块的代表元素小，比上一块的最大值和上一块的代表元素大。把所有代表元素全部丢进 x-fast trie。显然空间是线性的。

对于查找，我们注意到一个元素可能出现的块只有两个，分别是在 x-fast trie 上找的前驱和后继（如果直接找到的话，那就只能在那里）。然后在块内的平衡树上一查就行。

（虽然这个其实也可以直接维护个哈希表？）

upd：感谢 grg 指出，保证代表元素在一块的最大值和下一块的最小值之间的话比较好写。这样涉及到的块比较好找，就是在代表元素上查后继，直接就是有。

对于前驱和后继，和查找没有本质区别，一样做就行。最大最小值也同理。

对于插入，我们找到它的后继所在块完成插入就行。如果这个时候块太大了那我们就把它一分为二，重建平衡树和代表元素。我们注意到这里的复杂度瓶颈在于一分为二的部分，但是这部分实际上需要块非常大，每 O(\omega) 次插入才会触发一次，可以摊掉。

对于删除同理。这部分为了维护块长进行的操作是和相邻块合并（然后如果新块块长又炸了那就再一分为二），复杂度摊出来是一样的。

以上。