Persistent Data Structures and Functional Spines
What This Concept Is
Persistence preserves old versions. Partial persistence permits updates only to the latest version; full persistence permits branching updates from any version; confluent persistence additionally combines versions under specified semantics. Path copying creates new nodes on the affected search path and shares untouched subtrees, which must remain immutable across every version that references them.
Why It Matters Here
Version history has an API and storage cost. Merely copying a root pointer does not create an independent snapshot if updates mutate shared descendants. Conversely, deep-copying every node preserves values but loses the intended sharing bound.
Concrete Examples
The lab builds a fixed-index sum tree from [1,2,3,4] as version 0.
Set index 0 to 9 from version 0, creating version 1 with sum 18. Separately,
set index 3 to -1 from version 0, creating version 2 with sum 5. Version
0 must still sum to 10 and version 1 to 18. This is a branch, not
a chain of updates on whichever root was most recent.
An update copies one root-to-leaf path, O(log(n+1)) nodes; unchanged siblings are shared by identity. The reference exposes roots and immutable nodes for inspection. With q retained updates at fixed nonempty size n, total nodes are O(n+q*log(n+1)), plus O(q) version roots. Query costs O(log(n+1)) for a range sum. Initial construction costs O(n). Empty arrays have an initial queryable version but no valid point update.
Balanced search trees can also use path copying, but copying an unbalanced height-h path costs O(h), not automatically logarithmic. Version garbage collection depends on retained roots and sharing: dropping one root does not necessarily free all nodes once reachable from it. This affects memory measurements.
Common Confusion / Misconceptions
Persistence is not the same guarantee as database transactions, crash durability or snapshot isolation. Merging two versions needs conflict semantics and is not supplied by full persistence alone. General fat-node transformation bounds have model assumptions; do not quote a universal overhead for arbitrary structures.
How To Use It
Specify version IDs, branching semantics, immutable payload assumptions and retention policy. Test every old version after each branch update against independent copied arrays. Also inspect that an untouched sibling is physically shared and the modified path is new. State node, root-list and output storage separately.
Check Yourself
What distinguishes full from partial persistence? Why is root copying alone unsafe? What assumption makes path-copy cost logarithmic?
Mini Drill or Application
Fork version 0 twice as above. Feedback: sums 10,18,5 for versions 0,1,2. An update from version 0 must not read version 1 merely because it was created most recently.
Read This Only If Stuck
Use CLRS for tree path bounds and the authored version contract for the lab. Optional local functional/persistent structure readings should be selected by explicit topic, without attributing a general theorem to an unrelated chapter.