Y-Fast Tries¶

Bounded-universe integer ordered-set family where x-fast stores all prefixes for doubly-logarithmic predecessor / successor search, and y-fast refines the family with sampled representatives and balanced buckets.

Topic slug: data-structures/x-fast-y-fast-tries
Tutorial page: Open tutorial
Ladder page: Open ladder
Repo problems currently tagged here: 1
Repo companion pages: 5
Curated external problems: 1

Microtopics¶

bounded-universe
prefix-hashing
deepest-existing-prefix
leaf-linked-order
jump-pointer
y-fast-buckets

Learning Sources¶

Source	Type
Open Data Structures - Data Structures for Integers	`Reference`
Open Data Structures (C++) PDF	`Reference`

Repo Companion Material¶

Material	Type
X-Fast / Y-Fast hot sheet	`quick reference`
Template Library exact starter route	`starter route`
X-Fast Dictionary note	`anchor note`
Binary Trie / XOR Queries tutorial	`compare point`
PBDS / Order Statistics Tree tutorial	`compare point`

Curated External Problems¶

Core¶

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
X-Fast Dictionary Benchmark	`Open Data Structures`	`Hard`	X-Fast Trie, Textbook Breadth	Data-Structure-Heavy; Implementation-Heavy	Bounded Universe; Deepest Existing Prefix; Leaf Linked Order	Bounded-Universe; Prefix-Hashing; Predecessor-Successor	A clean breadth benchmark where the whole lesson is bounded-universe predecessor / successor through deepest-existing-prefix search and leaf-linked order, before y-fast bucket sampling is layered in.

Repo Problems¶

Code	Title	Fit	Difficulty	Pattern	Note	Solution
`XFASTDICTIONARY`	X-Fast Dictionary	`primary`	`hard`	-	Note	Code

Regeneration¶

python3 scripts/generate_problem_catalog.py