Skip to content

X-Fast / Y-Fast Hot Sheet

Use this page when the real lesson is bounded-universe predecessor / successor through prefix hashing, not one ordinary ordered set and not xor greediness.

Do Not Use When

Choose By Signal

  • fixed-width bounded integer universe + predecessor / successor -> X-Fast Trie
  • same job, but you now care about fixing x-fast's space / update cost -> Y-Fast Trie
  • fixed-width integer universe + xor-max objective -> Binary Trie

Core Invariants

  • every existing prefix is stored in exactly one hash table for its depth
  • leaves stay linked in sorted order
  • one-child internal nodes carry a jump to the nearest surviving leaf on that side
  • all keys use one fixed bit width

Main Traps

  • forgetting that x-fast is O(nw) space, not one magical contest default
  • mixing predecessor / successor logic with xor-greedy trie walks
  • claiming y-fast when only x-fast machinery is implemented

Exact Starter Route

Reopen Paths