Versions that never disappear
A persistent data structure preserves every previous version after an update, so you can still query the structure as it looked at any earlier point. An ordinary structure overwrites the old state; a persistent one keeps it accessible.
Path copying with sharing
The naive way to keep old versions is to copy the whole structure on every change, which is wasteful. The efficient way is path copying: when you change a node in a tree, copy only the nodes on the path from the root to that node, and share all the untouched subtrees with the previous version.
- A new root is created for the new version.
- Nodes along the changed path are fresh copies.
- Everything else points back into the old version, unchanged.
Because only one root to leaf path is duplicated, each update adds a small amount of new memory rather than a full copy.
What it enables
Persistence powers queries across versions, such as asking about an array as it was after the third of many updates, or answering range questions on historical snapshots. A persistent segment tree, for instance, can answer questions about any prefix of a sequence of updates.
Key idea
Copy only the path you change and share everything else, so each update yields a new version cheaply while old versions remain.