Keep earlier versions available
Maintain range sums for an array containing one through eight while preserving previous versions. Version zero totals thirty-six. Replacing the value three at index two with thirty creates version one totaling sixty-three; replacing index seven with eighty creates version two totaling 135. Queries on version zero must still return its original answers after both changes.
Copying the whole array per update would preserve versions but cost linear space each time. A persistent segment tree instead copies only the root-to-leaf update path and shares unchanged subtrees. Persistent here means earlier data-structure versions remain accessible during program execution. It does not mean durable storage across power loss. This in-memory example has no file serialization, transaction commit protocol or crash-recovery guarantee.
Store sums on half-open intervals
Each node stores the sum for a half-open interval. The root covers [0,8), with children [0,4) and [4,8). A length-one interval becomes a leaf. To query [2,6), reuse sums for fully covered subtrees, return zero for disjoint subtrees and descend only where a boundary crosses. Recomputing every leaf is unnecessary.
The implementation uses tuples containing a total and two child references. Existing tuples are never modified. That helps preserve old versions, but a tuple containing mutable nested objects would not automatically provide deep immutability. Here leaves are integers and children follow the same immutable-node rule. Version separation depends on both node values and reference-update discipline, not simply on calling the outer container immutable.
Copy only the changed path
Updating index two creates new nodes for [0,8), [0,4), [2,4) and [2,3). The right subtree [4,8) is unchanged and shared by versions zero and one. Recompute new parent totals while returning from the new leaf. Never overwrite an old parent's child reference. Retaining one root reference keeps the whole corresponding version reachable.
The subsequent update at index seven changes a right-side path, so versions one and two can share their left subtree. Sharing means reference identity, not merely equal values in independent copies. Included identity assertions check that distinction. Correct query results alone would not distinguish path copying from a wasteful full-tree copy. Validate semantic answers and structural sharing separately because both are part of the intended data-structure behavior.
| Version | Change | Root sum | New nodes | Shared with previous version |
|---|---|---|---|---|
| v0 | Build values 1..8 | 36 | 15 | None |
| v1 | Index 2: 3 → 30 | 63 | 4 | All [4,8); unaffected nodes on left also shared |
| v2 | Index 7: 8 → 80 | 135 | 4 | All [0,4); unaffected nodes on right also shared |
Check every interval of every version
The code builds an eight-element tree and retains three roots after two updates. For each version, all forty-five valid half-open intervals, including empty intervals, are compared with ordinary sums over the corresponding reference array. That gives 135 comparisons and checks that later changes did not alter earlier answers. Reference arrays are separate simple values, not queries through the same tree implementation.
This small implementation builds only nonempty fixed-length arrays and uses valid query bounds. Update validates that its index belongs to the current interval. A public API would also define empty initialization, invalid ranges, type requirements and version retention limits. The example teaches recursive path copying; it does not silently claim to implement every input-validation and resource policy of a production persistent-array library.
def build(a,lo,hi):
if hi-lo==1:return (a[lo],None,None)
mid=(lo+hi)//2;left=build(a,lo,mid);right=build(a,mid,hi)
return (left[0]+right[0],left,right)
def change(node,lo,hi,index,value):
if not lo<=index<hi:raise IndexError(index)
if hi-lo==1:return (value,None,None)
mid=(lo+hi)//2;left,right=node[1:]
if index<mid:left=change(left,lo,mid,index,value)
else:right=change(right,mid,hi,index,value)
return (left[0]+right[0],left,right)
def query(node,lo,hi,start,end):
if end<=lo or hi<=start:return 0
if start<=lo and hi<=end:return node[0]
mid=(lo+hi)//2
return query(node[1],lo,mid,start,end)+query(node[2],mid,hi,start,end)
a=list(range(1,9));v0=build(a,0,8);v1=change(v0,0,8,2,30);v2=change(v1,0,8,7,80)
assert v0[2] is v1[2] and v1[1] is v2[1]
for root,values in [(v0,a),(v1,a[:2]+[30]+a[3:]),(v2,a[:2]+[30]+a[3:7]+[80])]:
for start in range(9):
for end in range(start,9):assert query(root,0,8,start,end)==sum(values[start:end])
assert [v[0] for v in [v0,v1,v2]]==[36,63,135]
print('3 versions; totals=36,63,135; all135 intervals passed')
Count nodes as well as operations
A balanced interval split gives logarithmic height. A point update allocates one root-to-leaf path, or O(log n) new nodes, after O(n) initial construction. Retaining k updates therefore uses O(n plus k log n) logical nodes. Range-sum queries decompose around interval boundaries and take the usual O(log n) time under constant-cost sum operations.
Keeping every root still grows memory indefinitely. Dropping an old root makes exclusively reachable nodes eligible for reclamation, while nodes shared with other versions remain live. Follow the language's lifetime mechanism, such as garbage collection or reference counting. Freeing an old version's whole apparent subtree without accounting for shared references can corrupt newer versions. Storage sharing saves allocation but creates a corresponding ownership and retention responsibility.
Distinguish branching from merging
The example builds version one from zero and version two from one, but passing the old zero root into change creates a separate branch. Earlier versions can be update starting points, so version history need not be a single chain. The implementation does not automatically merge branches. Merging requires an additional policy for conflicting changes.
Version history is also not transaction conflict detection or authorization. Two users can create different roots from one prior state without deciding which root should become the application's current public state. Keep the scope to persistent array versions. When comparing with MVCC or storage snapshots, identify shared objects, root ownership and actual durable state separately. Similar vocabulary does not make their concurrency and recovery guarantees identical.
Change the aggregate and identity together
Zero is the identity for adding disjoint range sums. A range-minimum adaptation cannot keep returning zero for every disjoint subtree: positive input would acquire an invented smaller result. Change aggregation, identity and query combination consistently.
Path copying can be reused conceptually, but range updates introduce more state. Writing a lazy-propagation tag into a shared node can mutate earlier versions. Define which nodes are copied and how tags are propagated before adding such an optimization. Structural similarity does not preserve immutability automatically when mutable deferred state enters the representation.
Exercise: draw the copied path and shared branches
Change index zero from one to ten in the initial one-through-eight array. Create four new nodes covering [0,8), [0,4), [0,2) and [0,1). Share the opposite branches [4,8), [2,4) and [1,2) with the old root. The new total is forty-five while the old total remains thirty-six. Draw only the changed path anew rather than duplicating the whole diagram.
If the new root is discarded and only the old root remains, the four exclusively new nodes become reclaimable candidates. Discarding the old root instead must preserve old nodes still shared by the new version. Explain reachability from roots, not just numeric totals. That combines the benefit of historical versions with the memory-retention obligation created by structural sharing.