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.
SOLVE IT YOURSELF
Solve it: keep every old version of the tree
Undo, time-travel queries, git — all the same problem: query the data as it was k edits ago. Copying the whole structure per edit is O(n) each time. Copy only the path you touched and share everything else, and a version costs O(log n). Python or TypeScript.
YOUR TASK
Implement PersistentSegmentTree over an array: update(version, index, value) returns a new version number, and query(version, lo, hi) sums that range as it was in that version. Old versions must never change.
HINTS — 8 IDEAS
Nodes are immutable. Nothing is ever written to an existing node — that is the single rule the whole structure rests on.
An update walks from the root to one leaf. Every node on that path gets a fresh copy; the child that was not on the path is reused by pointer.
So a new version allocates only the path length — about log₂ n nodes — no matter how large the array is.
Each version is just its own root. Keep a list of roots; version v is the tree reachable from root v.
Query is an ordinary segment-tree query that happens to start from an old root. Nothing about it knows versions exist.
Sharing is what makes this safe and cheap at once: an old version cannot observe a later edit, because none of its reachable nodes were ever written to.
Count your allocations to see it. Building n=16 costs 31 nodes; each update after that costs exactly 5, not 31.
The same path-copying trick underlies persistent maps in functional languages — this is not a niche competitive-programming device.