Persistent structures preserve all versions. Techniques:
-
Path copying: Copy modified nodes only
-
Fat nodes: Store version history per node Common Structures:
-
Persistent array: access
-
Persistent segment tree: Version-aware range queries
-
Persistent treap: Ordered set with versions Key Pattern: New version shares unmodified nodes with old versions.
Applications: Undo/redo, version control, time-travel queries. Space: per update.