Versions that never disappear
A persistent segment tree lets you query not just the current array but any past version of it. Every update produces a new version while keeping all previous ones intact and accessible. The trick is to avoid copying the whole tree on each change.
Path copying
When an update changes one leaf, only the nodes on the path from root to that leaf change. So we create new copies of just those nodes, a logarithmic number, and let the new nodes point back at the old, unchanged subtrees. Each version has its own root; together the versions share most of their structure.
- Update: clone the affected root to leaf path, splice in the change, return the new root.
- Query a version: start from that version's saved root and descend normally.
- Space: each update adds only a logarithmic number of new nodes.
A classic use
Storing one version per array prefix turns a range query into a difference of two versions. This solves the kth smallest in a range problem elegantly: build a version after inserting each element, then compare two versions while walking the tree.
Key idea
Copy only the root to leaf path on each update and share everything else, so all versions stay queryable while space grows only logarithmically per change.