Persistent Data Structures

Structures that preserve every previous version after an update, allowing queries against any point in their history.

Versions that never die

A persistent data structure keeps all its past versions accessible after modifications. Partial persistence allows queries on any version but updates only on the latest; full persistence allows updates on any version, branching history into a tree; confluent persistence even allows merging versions. Persistence is achieved without copying the whole structure on each change.

Path copying

The standard technique for tree-shaped structures is path copying: an update creates new copies only of the nodes on the path from the root to the change, sharing all untouched subtrees with the previous version. A new root points to the new path. Each update costs O(log n) extra nodes for a balanced tree, and every old root still describes a valid past version.

Persistent segment-tree update

def update(node, lo, hi, i, val):
    if lo == hi:
        return Node(val)                 # new leaf
    mid = (lo + hi) // 2
    if i <= mid:
        return Node(left=update(node.left, lo, mid, i, val),
                    right=node.right)     # share right subtree
    else:
        return Node(left=node.left,
                    right=update(node.right, mid+1, hi, i, val))

What it powers

• Persistent segment trees answer range k-th-smallest and range-count over historical arrays.
• Persistent balanced BSTs and tries give immutable maps for functional languages.
• Version control and undo stacks that keep full history cheaply.
• Kinetic and temporal queries that ask about the state at an earlier time.

Cost model

Path copying keeps each update's extra space proportional to the modified path length, so k updates on an n-node tree use O(k log n) total space while preserving all k+1 versions, an application of the sharing that makes immutable structures practical.