Persistent Segment Trees

A persistent segment tree preserves all historical versions. After an update, you can query both the old and new versions.

Notice: updates only affect $O(\log n)$ nodes (the path from root to leaf). Create new nodes only for this path; share all unchanged nodes with previous version.

def update(oldRoot, idx, val):
    # Create new root
    newRoot = copy of oldRoot
    # Recurse, creating new nodes along the path
    # Unchanged subtrees point to same nodes as old version
    return newRoot

Space per update: $O(\log n)$ new nodes.

Total space for $m$ updates: $O(n + m \log n)$.

Use case: answer queries about the array state after the $k$-th update.