Exotic Structures

Structures that are theoretically important, occasionally decisive, and almost never written in a contest. Worth recognising by name.

van Emde Boas tree

A recursive structure over a universe of size $U=2^w$, splitting each key into a high half and a low half. Supports insert, delete, predecessor, successor, min, max all in $O(\log \log U)$.

• Memory: $O(U)$ naively; $O(n)$ with hashing (a “y-fast trie”-style implementation).
• The $\log \log U$ comes from the recursion $T(U)=T(\sqrt{U})+O(1)$.
• Beats a balanced BST when $U$ is small: for $U=2^{32}$, $\log \log U=5$ versus $\log n\approx 20$.

In practice: a bitset with _Find_next is faster for small universes, and a hash set plus a BIT usually beats both in code length.

x-fast trie and y-fast trie

• x-fast trie — a binary trie over the keys plus a hash table of every prefix. Predecessor/successor in $O(\log \log U)$ by binary searching the prefix length. Memory $O(n\log U)$.
• y-fast trie — group keys into buckets of size $\Theta (\log U)$, store one representative per bucket in an x-fast trie, and keep each bucket in a small BST. Memory drops to $O(n)$, operations stay $O(\log \log U)$ amortized.

Fusion tree

A $B$-tree with branching factor $w^{1/5}$, where each node compares a key against $O(w^{1/5})$ stored keys in $O(1)$ using a “sketch and multiply” word trick. Gives $O({\log }_{w}n)=O(\log n/\log w)$ predecessor search — beating comparison-based bounds by exploiting word-level parallelism.

Combined with integer sorting, fusion trees give $O(n\log n/\log \log n)$ sorting.

Tango tree

A binary search tree that is $O(\log \log n)$-competitive: its total cost is within a $\log \log n$ factor of the optimal offline BST for any access sequence.

Relevant to the dynamic optimality conjecture: is a splay tree $O(1)$-competitive? Open since 1985. Tango trees, multi-splay trees and chain-splay trees are the best known competitive ratios.

Soft heap

A priority queue with $O(1)$ amortized operations that is allowed to corrupt at most an $\epsilon$ fraction of keys (their stored values may increase). Trading exactness for constant time is what lets Chazelle’s MST algorithm reach $O(m\alpha (m,n))$, and it gives an elegant linear-time selection algorithm.

Brodal queue

Achieves the theoretical optimum for a meldable priority queue: $O(1)$ worst case for insert, meld, find-min and decrease-key, with $O(\log n)$ delete-min. Enormously complicated; a proof of possibility rather than a usable structure. The hollow heap (2015) achieves the same amortized bounds far more simply.

Retroactive data structures

Support “insert an operation into the past” and see the effect on the present. Partially retroactive (query only the present) and fully retroactive (query any point in time) variants exist. Related to, but stronger than, persistence: persistence lets you read the past, retroactivity lets you change it.

Succinct and compressed structures

Represent data in space close to the information-theoretic minimum while still supporting fast queries:

• Rank/select bit vectors — $n+o(n)$ bits, $O(1)$ queries;
• Wavelet trees — $n\log \sigma$ bits, $O(\log \sigma )$ queries;
• FM-index — a compressed full-text index; what DNA aligners use;
• Succinct trees — $2n+o(n)$ bits with $O(1)$ navigation.

Genuinely used in bioinformatics and search engines, where the data does not otherwise fit in memory.

What to take from this page

Two transferable ideas that do show up in contests:

1. Word-level parallelism. Packing many small values into one machine word and operating on them together is exactly what fusion trees, bitset DP and Bitap all do. The $/64$ speedup is real and often decisive.
2. Trading exactness for speed. Soft heaps, approximate counting and randomised structures all buy performance by relaxing a guarantee. Ask whether your problem actually needs the exact answer at every step.

See also: Advanced Heaps · Bitset Optimization · Wavelet Tree