~/home/persistent segment tree: every version kept
Algorithms · Data Structures
Every Version Kept.
A normal data structure forgets: once you update it, the old state is gone. A persistent one remembers every version, letting you query the structure as it was at any past moment. The naive way — copy the whole tree on each update — would cost O(n) memory per version. The persistent segment tree does it in O(log n) with path copying: since a point update only changes the nodes on one root-to-leaf path, you copy just those O(log n) nodes into a new version, and the new tree shares every untouched subtree with the old one. Each version gets its own root; the rest is shared. Do an update and watch exactly one path get copied.
O(log n) time & extra memory per update · path copying · query any historical version
version
A snapshot of the structure, identified by its own root node.
path copying
An update copies only the nodes on the one changed root-to-leaf path.
structural sharing
Unchanged subtrees are pointed to by both old and new versions — not duplicated.
immutable nodes
Nodes are never modified in place, so old versions stay valid forever.
persistent.js — copy the path, share the rest
Ready
A segment tree over 8 values. A point update creates a new version by copying only the nodes on the path from root to the changed leaf — everything else is shared with the previous version. Update a value to see.
0
versions
–
new nodes / update
15
total nodes
How it works
The reason path copying works is that a segment-tree point update only touches nodes along a single root-to-leaf path — every other node’s value is unaffected. Persistence exploits this by treating nodes as immutable: instead of modifying nodes in place, the update builds a fresh copy of each node on that path, with its pointers redirected — a copied node points to its one new child (also on the path) and to its old, untouched other child, which is shared with the previous version. The result is a brand-new root for the new version whose tree overlaps almost entirely with the old one. Each update thus adds only O(log n) nodes and takes O(log n) time, while both versions remain fully queryable — the old root sees the old data, the new root sees the update.
1
Keep nodes immutable
Never modify a node in place. Every version is reachable from its own root, and shared nodes must stay valid for older versions, so updates only create new nodes.
2
Copy the update path
A point update walks one root-to-leaf path. Create a new copy of each node along it, from the leaf back up to a new root.
3
Redirect pointers, share the rest
Each copied node points to its newly-copied child on the path and to the previous version’s untouched child on the other side — sharing that whole subtree.
✓
A new root per version
The update returns a new root for the new version. Query any version by starting from its root; older versions are unchanged. Cost: O(log n) time and O(log n) new nodes per update.
Update
O(log n)
Memory / update
O(log n)
Query any version
O(log n)
Technique
path copying
The code
# persistent point update: returns a NEW root, shares subtreesdef update(node, lo, hi, pos, val):
if lo == hi:
return Node(val) # new leaf
mid = (lo + hi) // 2
if pos <= mid:
left = update(node.left, lo, mid, pos, val) # copy path left
right = node.right # SHARE right subtreeelse:
left = node.left # SHARE left subtree
right = update(node.right, mid+1, hi, pos, val)
return Node(left.sum + right.sum, left, right) # new node on path
Quick check
1. How does a persistent segment tree keep every version cheaply?
A point update only changes nodes along one root-to-leaf path. Path copying duplicates just those O(log n) nodes into a new version, while every other subtree is shared with the previous version — so each version costs only O(log n) extra memory.
2. What must be true of nodes for persistence to work?
Nodes are immutable: an update never mutates an existing node, because older versions still point to it. Instead it creates new nodes along the path, keeping every past version valid.
3. After an update, how do you query an old version?
Each version has its own root. Querying from the old root traverses the old (unchanged, possibly shared) nodes, giving the data exactly as it was at that version — while the new root reflects the update.
FAQ
What is a persistent segment tree?
A segment tree that preserves all previous versions after updates, so you can query it as it existed at any past point. It uses path copying: each point update copies only the O(log n) nodes on the changed path and shares the rest, at O(log n) extra time and memory per update.
What is path copying and structural sharing?
Path copying copies only the nodes along the updated root-to-leaf path when modifying an immutable tree. Structural sharing means the new nodes point to the old version’s untouched subtrees rather than duplicating them. Together they make each new version cost only O(log n) memory.
What problems do persistent segment trees solve?
They query the array’s state at past moments and enable offline techniques. A classic use is "k-th smallest in a range": build persistent trees over prefixes so version i minus version j is a subarray’s multiset, then descend the tree. They also handle range-distinct counts and sweep-based geometry.
How much memory does persistence add?
Each update adds O(log n) new nodes (the copied path), so m updates use O(n + m log n) memory instead of O(n·m) for full copies. That modest overhead makes keeping every version practical — the same immutability-and-sharing idea used throughout functional programming.