↩ back to Array-Backed Trees

Persistent Segment Tree

A plain segment tree only ever has one state: "right now." Update index 3 and the array's old value at index 3 is gone — there's no way to ask what a range sum looked like three updates ago without having saved a copy yourself. A persistent segment tree keeps every version that ever existed queryable forever, the same promise Persistent Union-Find makes for disjoint sets — but here the mechanism can't be "one small record per element," because segment tree nodes hold values that change, not parent pointers that are set at most once. What survives instead is structural sharing: an update allocates only the O(log n) nodes on the path from root to the changed leaf, and every other node in the tree — the vast majority of it — is the literal same object, pointed to by both the old version's root and the new one.

Try it

Same 8-value array as the plain Segment Tree page, now tracking range sum instead of range minimum. Pick an index and a value and press Update to create a new version — every version ever created stays in the strip below; click any chip to view that version's tree exactly as it looked the moment it was made, nothing rewound or replayed. Nodes outlined in the accent color were created in the version you're viewing; plain nodes are older, shared unchanged with an earlier version. Pick a range and press Query Sum to sum over whichever version is currently being viewed, then step through to see the same fully-inside / no-overlap / partial-overlap decomposition the plain segment tree uses, just walked top-down by range instead of bottom-up by array index.

Why it works

Every node here is an immutable object holding its own [lo, hi] range, a sum, and pointers to its two children — the recursive, top-down shape the plain segment tree page's Pitfalls section calls out as the alternative to that page's flat, iterative array. That alternative form isn't just a style choice here — it's the only one that can be persistent. A flat array indexes children implicitly by position (2i, 2i+1): changing one slot means the array itself has changed, so keeping an old version means copying the whole array. Pointer-based nodes index children by reference, and a reference can point at an object that already exists — so a node whose subtree wasn't touched by an update doesn't need copying, it just gets pointed to again.

Update. Setting index i to a new value walks down from the previous version's root exactly like a query would, but on the way back up, instead of mutating each node it visited, it allocates a new node at every level: a new leaf at the bottom, then a new internal node whose two children are — one newly-created child (the one on the path to i) and one untouched child, the exact same object as before (whichever side i didn't go). On the default 8-element array [5, 2, 8, 1, 9, 3, 7, 4], setting index 3 from 1 to 6 allocates exactly 4 new nodes — the leaf for index 3, then its 3 ancestors up to the root — while every one of the other 11 nodes in the 15-node tree is reused, unchanged, by reference. The new root points at 1 new child and 1 old child; that old child points at its own 1 new and 1 old child; and so on, until the recursion bottoms out at a whole reused subtree that both the old and new version now share.

Query just walks whichever version's root you hand it, the same three-way decomposition as any top-down segment tree: a node whose range has no overlap with the query contributes nothing; a node whose range sits fully inside the query contributes its whole precomputed sum with no further recursion; and a node that straddles the query's edge recurses into both children. Nothing about querying cares whether a node is old or brand new — that's exactly the point. The version you're viewing determines only which root you start from; from there it's an ordinary segment tree walk over whatever nodes that root happens to reach.

Reference implementation

Matches the demo above. nodes is an append-only store — nothing already in it is ever mutated — and each version is nothing more than the id of its root:

class PersistentSegmentTree {
  #nodes = [];   // append-only: { lo, hi, sum, left, right }
  #roots = [];   // roots[v] = node id of version v's root

  #newLeaf(lo, hi, val) {
    return this.#nodes.push({ lo, hi, sum: val, left: null, right: null }) - 1;
  }
  #newInternal(lo, hi, leftId, rightId) {
    const sum = this.#nodes[leftId].sum + this.#nodes[rightId].sum;
    return this.#nodes.push({ lo, hi, sum, left: leftId, right: rightId }) - 1;
  }

  constructor(values) {
    const build = (lo, hi) => {
      if (lo === hi) return this.#newLeaf(lo, hi, values[lo]);
      const mid = (lo + hi) >> 1;
      return this.#newInternal(lo, hi, build(lo, mid), build(mid + 1, hi));
    };
    this.#roots[0] = build(0, values.length - 1);
  }

  // returns the new version number; every earlier version is untouched
  update(i, val) {
    const rec = (nodeId) => {
      const n = this.#nodes[nodeId];
      if (n.lo === n.hi) return this.#newLeaf(n.lo, n.hi, val);
      const mid = (n.lo + n.hi) >> 1;
      return i <= mid
        ? this.#newInternal(n.lo, n.hi, rec(n.left), n.right)   // right REUSED
        : this.#newInternal(n.lo, n.hi, n.left, rec(n.right));  // left REUSED
    };
    this.#roots.push(rec(this.#roots[this.#roots.length - 1]));
    return this.#roots.length - 1;
  }

  querySum(version, l, r) {
    const rec = (nodeId) => {
      const n = this.#nodes[nodeId];
      if (r < n.lo || n.hi < l) return 0;
      if (l <= n.lo && n.hi <= r) return n.sum;
      return rec(n.left) + rec(n.right);
    };
    return rec(this.#roots[version]);
  }
}

Pitfalls

Mutating a node in place instead of allocating a new one doesn't just corrupt the current version — it silently corrupts every earlier one too, verified with real numbers. Build the default 8-element array (version 0, full sum 39), then run a deliberately broken update that walks the path to index 3 the right way but writes each node's new sum directly onto the existing object instead of allocating a fresh one. Querying version 0's full sum after that "update" returns 138, not 39 — because version 0's root was never a separate object to begin with, just a pointer to the same nodes the "new" version also points to. There's no way to tell, from a corrupted node alone, whether it was ever meant to be shared — the bug is invisible until something asks an old version a question and gets today's answer.

This is partial persistence, the same named boundary Persistent Union-Find draws around itself. Every version that has ever existed stays queryable forever, but a new update always extends the current latest version — there's no way to branch a second, alternate future off some older version without touching the versions built on top of it since. That's a real limit for a use case that needs branching timelines, and a non-issue for the offline "what did this look like as of version v" queries this structure is built for.

Unlike Persistent Union-Find, persistence here is not close to free. Persistent Union-Find gets full history for O(1) amortized extra space per union, because each of its nodes changes its one fact — its parent — at most once in its entire lifetime. A segment tree node's sum can change on every single update that touches its range, and the root's range is the whole array — so the root, and everything on the path to it, is genuinely reallocated every time. O(log n) new nodes per update is the ordinary, expected cost of persistence for a structure whose values actually change, not a bug to optimize away; Union-Find is the unusual case, not this one.

Complexity

Time: O(log n) for both update and querySum(version, l, r) — identical bounds to the plain segment tree, since both walk exactly one root-to-leaf path (update) or at most two nodes per level (query); persistence changes nothing about how many nodes get visited. Building from an existing array is O(n), same as the plain tree's single backward pass, just built top-down here instead of bottom-up. Space: O(n) for the very first version, exactly like a plain segment tree — but every subsequent update adds O(log n) new nodes on top of that, rather than reusing O(n) forever. After m updates the structure holds O(n + m log n) nodes total: for the demo's 8-leaf tree that's 15 nodes for version 0 plus exactly 4 more per update, verified directly against the reference implementation above — 4 updates in sequence produced 4, 4, 4, and 4 new nodes, 31 nodes total, and every one of the 5 versions still answers every range-sum query correctly when cross-checked against a from-scratch array replay (256 range/version combinations checked for the demo's default sequence, zero mismatches). If updates never happen at all, paying even O(log n) for them is wasted — see Sparse Table for the same kind of range query answered in O(1) once the array is frozen for good.

This site's guide, Choosing a Range Query Structure, compares this entry against the other five Array-Backed Trees structures that answer the same kind of question side by side.