Versioning Concept for Persistent Structures

Versioning in data structures means queries refer to a specific point in history—immutable nodes or copy-on-write enable safe sharing.

Why this shows up in the real world

Time-series dashboards, game leaderboards, and competitive programming interval problems all need fast answers on changing arrays.

Core idea (explained for students)

Functional programming and undo systems use the same idea—segment tree is a teaching path to persistent treaps and ropes.

Try this in Python

# Immutable-style: each update returns new root; old root still valid.
old_root = 1
new_root = 2  # after update path copy
assert old_root != new_root

Common mistakes

• Thinking persistence is only for segment trees.
• Ignoring memory: O(n log n) total for n updates typical.

Key takeaways

• Draw two versions sharing left subtree.
• Relate to git branches metaphor (shared commits).