Persistent structures and augmentation

Persistent structures preserve old versions after updates. Path copying duplicates only the changed root-to-leaf path and shares untouched immutable subtrees. Partial persistence reads old versions; full persistence permits branching updates from them.

A persistent segment-tree point update creates O(log n) nodes. Root references represent snapshots; comparing versions enables historical range queries. Track version lifetimes, since immutability does not eliminate memory growth.

Augmentation stores local metadata such as size, sum or maximum interval endpoint. Interval trees use maximum endpoints to prune overlap searches. O(1) recomputation from children keeps rotations cheap. Mutating a shared old node destroys historical correctness.

# Minimal immutable node; unchanged children may be shared.
from dataclasses import dataclass
@dataclass(frozen=True)
class Tree:
    total: int
    left: object = None
    right: object = None
old = Tree(3, Tree(1), Tree(2))
new = Tree(7, Tree(5), old.right)
assert old.total == 3 and new.right is old.right