Data Structures -> Persistent Data Structures

Path-copying data structures where updates create new version roots and old snapshots remain queryable.

• Topic slug: data-structures/persistent-data-structures
• Tutorial page: Open tutorial
• Ladder page: Open ladder
• Repo problems currently tagged here: 1
• Repo companion pages: 5
• Curated external problems: 3

Microtopics

• path-copying
• version-roots
• persistent-segment-tree
• copy-on-write
• snapshot-query
• branching-versions

Learning Sources

Source	Type
cp-algorithms segment tree persistent section	Reference
USACO Guide persistent data structures	Reference
CSES Range Queries and Copies	Practice

Practice Sources

Source	Type
SPOJ MKTHNUM	Practice
Library Checker Persistent Union Find	Practice

Repo Companion Material

Material	Type
Persistent Data Structures hot sheet	quick reference
Range Queries and Copies note	anchor note
Persistent starter route	starter route
Segment Tree tutorial	adjacent tutorial
DSU Rollback tutorial	compare point

Curated External Problems

Core

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Range Queries and Copies	CSES	Hard	Persistent Segment Tree	Data-Structure-Heavy; Versioned Queries	Segment Tree; Point Update; Path Copying	Path-Copying; Version-Roots; Range-Sum	The cleanest first exact benchmark where each point update creates a new segment-tree root and old versions stay queryable.

Stretch

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
K-th Number	SPOJ	Hard	Order Statistics, Persistent Segment Tree	Data-Structure-Heavy; Value Compression	Coordinate Compression; Prefix Version Difference	Prefix-Versions	The classic stretch problem once path copying is trusted and the persistent tree stores frequencies instead of plain sums.

Challenge

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Persistent Union Find	Library Checker	Hard	Persistent Union Find	Verification; Versioned Queries	Persistence Worldview; Version Handles; DSU Basics	Persistence; Versioned Connectivity	A family-broadening verifier showing that the persistent worldview is larger than segment-tree snapshots alone.

Repo Problems

Code	Title	Fit	Difficulty	Pattern	Note	Solution
RANGEQUERIESANDCOPIES	Range Queries and Copies	primary	hard	persistent segment tree; path copying; versioned range sum	Note	Code

Regeneration

python3 scripts/generate_problem_catalog.py