Y-fast trie

ordered dictionary

successor(x) returns the smallest element of S greater than x, ①=1
x000①0｜
（⇒）

predecessor(x) returns the largest element of S smaller than x, ①=1
｜010①0x
（⇒）

---

An X-fast Trie is a binary trie where leaves are stored in a doubly-linked list and where all nodes in each level are stored in a hash table. It is O(1).

The successor(x) is O(log log U).

You add new nodes to the trie and update thread pointers to include x.

Y-fast trie has predecessor or successor queries in O(log log U) by using O(n). It contains at least (log U)/4 and at most 2 log U elements in X-fast trie. X-fast trie stores O(n / log U) representatives. You can see where Y is because of comparison.