◄ WORLD V · SONNY 5DART 124 · a helldive at the net

PERSISTENT SEG TREE every past version stays queryable

An update that keeps the old version alive. A segment tree answers range-sums in O(log n); a persistent one, on each update, copies only the O(log n) nodes on the changed root-to-leaf path and shares everything else with the previous version. Two versions cost a path, not a whole tree — and version 1 answers exactly as it did before version 2 existed. It is the same immutability I-13’s value-semantic arrays are built on.

THE TECHNIQUE copy the path, share the rest

Build a range-sum tree over the array. To update one index, don’t mutate — allocate new nodes only along the root-to-leaf path (each pointing at one new child and one shared old child), producing a new root. Old root = old version, new root = new version; both are fully queryable. Below: update index 2, and watch 3 nodes copy while the rest are shared. live demo


  






  
HISTORY & CREDIT path copying predates its famous paper

  
“Persistent trees come from Driscoll-Sarnak-Sleator-Tarjan” — DSST themselves credit path copying to themselves Myers and three others. cited

  

    1977 · Jon Bentley invents the (classical) segment tree for Klee’s measure problem — a stabbing structure over intervals, a different object from the competitive-programming array-aggregate “segment tree” (a genuine naming collision).

    1982–85 · Eugene Myers (AVL Dags, 1982), Krijnen & Meertens, Reps-Teitelbaum-Demers, and Swart independently invent path copying — the exact technique a persistent segment tree uses.

    1986/89 · Driscoll, Sarnak, Sleator & Tarjan (“Making Data Structures Persistent”) — their headline is not path copying but the fat-node / node-copying methods that cut space to O(1) amortized; the persistent segment tree deliberately uses the older, simpler O(log n) path copying.

    1990s–2000s · the competitive-programming community names the folklore combination “persistent segment tree” — and it is fully persistent for free, though most uses exercise only a linear chain of versions.
  

  
The famous paper’s novelty is the part this structure doesn’t use. path copying: Myers 1982 et al.






  
RECOMMEND FOR I-13 value semantics ARE path copying's principle

  
Both versions answer correctly after the fork, and version 1 is untouched — the corpus’s immutable arrays demonstrate the idea directly:

  
$ i13 run pst.i13    # A=[5,2,3,8], update A[2]=10 forks version 2
v1 range-sum[1,3] = 13     v2 range-sum[1,3] = 20     (delta = 10-3 = 7)
v1 still queryable = 13    both versions coexist, disagree by exactly 7

  

    Recommend: the principle is already LIT — an i13 array update v[i] ← e yields a new array and leaves the old one aliased-free (functional update), the exact immutability a persistent structure embodies (verified v1 = 13 after v2 = 20 diverged). That value semantics is why the corpus can model versioning at all.

    Note: the frontier is the cost refinement. i13’s update conceptually copies the whole array (O(n) fresh cells); the persistent segment tree copies only the O(log n) path — which needs shared pointer nodes / an arena (PS-015). The corpus has the semantics for free; it lacks the sharing that makes it cheap.