Persistent Trees: Immutable BSTs, Treaps & Segment Trees via Path Copying

1. Introduction & Motivation

Every data structure covered so far in this series is ephemeral: it has exactly one current state, and any update — insert, delete, set a value — mutates that state in place. Once you call insert(root, 5) on a normal binary search tree, the tree as it existed one line earlier is gone. If you needed that earlier shape for anything, you should have copied it first, and a full copy costs $O(n)$.

A persistent data structure removes that tradeoff. Every update produces a brand-new version of the structure, and every version that ever existed — including the very first one — remains fully valid and queryable forever. Calling insert on a persistent BST does not destroy the old root; it returns a new root, and both roots keep working correctly, independently, for as long as your program holds a reference to either one.

This lesson is about how that is possible without paying $O(n)$ per update. The technique is called path copying, and it applies to any structure built out of nodes connected by pointers in a tree shape: binary search trees, treaps, segment trees, and tries all qualify, and the same idea is the reason purely functional programming languages can treat "update a data structure" as an ordinary, cheap expression rather than a dangerous in-place mutation.

2. Prerequisites

This lesson builds directly on two earlier pieces of the curriculum and assumes you are comfortable with both:

• Standard (ephemeral) BST insert — see BST Operations in the BST/AVL/Red-Black lesson (Part 10). Persistent BST insert is the same recursive descent, with one change: instead of mutating a child pointer, it returns a new node.
• Standard (ephemeral) Segment Tree — see the Segment Tree section of the Advanced Structures lesson, which covers the recursive build/update/query pattern this lesson assumes and only modifies at the node-allocation level.

Neither prerequisite is re-derived here. If the ordinary recursive insert or the ordinary build/update/query pattern is unfamiliar, read those sections first — everything below is the same recursion with a persistence twist layered on top.

3. Core Insight: Path Copying

Take any tree-shaped structure and any update that changes a single node deep inside it. The naive way to persist that update is to deep-copy the entire structure before mutating the copy — correct, but $O(n)$ in both time and space, since it duplicates every node even though only one node actually changed.

Because a balanced BST, treap, or segment tree has height $O(\log n)$, path copying clones $O(\log n)$ new nodes per update and shares the rest — giving $O(\log n)$ extra time and extra space per update, not $O(n)$. The old root is never touched, so it, and everything reachable from it, is exactly as valid after the update as before it.

4. A Concrete Example

5. Persistent BST

Applying the recipe from Section 3 to a BST gives an insert that returns a new root instead of mutating in place. Each language below keeps a growing list of historical roots and then queries an old root after a later insert has happened, to demonstrate that the old version is unaffected.

class Node:
    __slots__ = ("val", "left", "right")
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def insert(root, val):
    """Return the root of a NEW version with val inserted.
    The old 'root' and every node reachable from it are left untouched."""
    if root is None:
        return Node(val)
    if val < root.val:
        return Node(root.val, insert(root.left, val), root.right)
    elif val > root.val:
        return Node(root.val, root.left, insert(root.right, val))
    return root  # duplicate value: this version is identical to the input

def contains(root, val):
    """Ordinary BST search; works on ANY historical root."""
    node = root
    while node:
        if val == node.val:
            return True
        node = node.left if val < node.val else node.right
    return False

# Keep every historical root; roots[i] is the tree after i inserts.
roots = [None]
for value in [5, 3, 8, 4]:
    roots.append(insert(roots[-1], value))

print(contains(roots[3], 4))   # False: version 3 (after 5, 3, 8) has no 4 yet
print(contains(roots[4], 4))   # True:  version 4 (after 5, 3, 8, 4) has it
print(contains(roots[3], 8))   # True:  version 3 already had 8

#include <iostream>
#include <memory>
#include <vector>

struct Node {
    int val;
    std::shared_ptr<Node> left, right;
    Node(int v, std::shared_ptr<Node> l = nullptr, std::shared_ptr<Node> r = nullptr)
        : val(v), left(l), right(r) {}
};
using NodePtr = std::shared_ptr<Node>;

// Returns the root of a NEW version; every node on the search path is
// cloned, every other subtree is shared (shared_ptr reference, no copy).
NodePtr insert(const NodePtr& root, int val) {
    if (!root) return std::make_shared<Node>(val);
    if (val < root->val) return std::make_shared<Node>(root->val, insert(root->left, val), root->right);
    if (val > root->val) return std::make_shared<Node>(root->val, root->left, insert(root->right, val));
    return root; // duplicate value: no new node needed
}

bool contains(const NodePtr& root, int val) {
    Node* node = root.get();
    while (node) {
        if (val == node->val) return true;
        node = (val < node->val) ? node->left.get() : node->right.get();
    }
    return false;
}

int main() {
    std::vector<NodePtr> roots{nullptr};
    for (int value : {5, 3, 8, 4}) {
        roots.push_back(insert(roots.back(), value));
    }
    std::cout << std::boolalpha;
    std::cout << contains(roots[3], 4) << "\n";  // false
    std::cout << contains(roots[4], 4) << "\n";  // true
    std::cout << contains(roots[3], 8) << "\n";  // true
}

import java.util.ArrayList;
import java.util.List;

public class PersistentBST {
    static final class Node {
        final int val;
        final Node left, right;
        Node(int val, Node left, Node right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    // Returns the root of a NEW version; nodes on the path are cloned,
    // every other subtree is shared by reference with the old version.
    static Node insert(Node root, int val) {
        if (root == null) return new Node(val, null, null);
        if (val < root.val) return new Node(root.val, insert(root.left, val), root.right);
        if (val > root.val) return new Node(root.val, root.left, insert(root.right, val));
        return root; // duplicate value: no new node needed
    }

    static boolean contains(Node root, int val) {
        Node node = root;
        while (node != null) {
            if (val == node.val) return true;
            node = (val < node.val) ? node.left : node.right;
        }
        return false;
    }

    public static void main(String[] args) {
        List<Node> roots = new ArrayList<>();
        roots.add(null);
        for (int value : new int[]{5, 3, 8, 4}) {
            roots.add(insert(roots.get(roots.size() - 1), value));
        }
        System.out.println(contains(roots.get(3), 4)); // false
        System.out.println(contains(roots.get(4), 4)); // true
        System.out.println(contains(roots.get(3), 8)); // true
    }
}

Persistent Treap

A treap keeps its BST-ordering property alongside a randomly assigned heap priority, and its two workhorse operations, split and merge, are already written as recursive functions that rebuild a small number of nodes on their way back up the call stack — see the Treap, Splay Tree & Cartesian Tree lesson for the full derivation of split/merge, which is not repeated here. That shape is exactly what path copying wants: instead of mutating left/right pointers while unwinding the recursion, allocate a new node with the recursive result plugged in, and return it. No new algorithmic idea is required, only the same node-return-instead-of-mutate substitution already used for the BST above:

# Ephemeral merge mutates: left.right = merge(left.right, right); return left
# Persistent merge instead allocates a new node on the way back up:
def merge(left, right):
    if left is None: return right
    if right is None: return left
    if left.priority > right.priority:
        return Node(left.val, left.priority, left.left, merge(left.right, right))
    return Node(right.val, right.priority, merge(left, right.left), right.right)

Because split and merge together implement treap insert and delete, persisting those two functions persists the whole treap for free.

6. Persistent Segment Tree

The base recursive build/update/query pattern is not re-derived here; see the Segment Tree Implementation section of the Advanced Structures lesson for the ephemeral version this extends.

class SegNode:
    __slots__ = ("sum", "left", "right")
    def __init__(self, sum_=0, left=None, right=None):
        self.sum = sum_
        self.left = left
        self.right = right

def build(arr, lo, hi):
    if lo == hi:
        return SegNode(arr[lo])
    mid = (lo + hi) // 2
    left = build(arr, lo, mid)
    right = build(arr, mid + 1, hi)
    return SegNode(left.sum + right.sum, left, right)

def update(prev, lo, hi, idx, val):
    """Return the root of a NEW version with arr[idx] = val.
    Nodes off the path to idx are shared with 'prev', not copied."""
    if lo == hi:
        return SegNode(val)
    mid = (lo + hi) // 2
    if idx <= mid:
        new_left = update(prev.left, lo, mid, idx, val)
        return SegNode(new_left.sum + prev.right.sum, new_left, prev.right)
    else:
        new_right = update(prev.right, mid + 1, hi, idx, val)
        return SegNode(prev.left.sum + new_right.sum, prev.left, new_right)

def query(node, lo, hi, ql, qr):
    """Range sum [ql, qr] against ANY historical root. O(log n)."""
    if qr < lo or hi < ql:
        return 0
    if ql <= lo and hi <= qr:
        return node.sum
    mid = (lo + hi) // 2
    return query(node.left, lo, mid, ql, qr) + query(node.right, mid + 1, hi, ql, qr)

arr = [1, 3, 5, 7, 9, 11]
n = len(arr)
roots = [build(arr, 0, n - 1)]                    # version 0: the original array
roots.append(update(roots[0], 0, n - 1, 1, 10))   # version 1: index 1 set to 10

print(query(roots[0], 0, n - 1, 1, 3))   # 15 = 3+5+7  (old version, untouched)
print(query(roots[1], 0, n - 1, 1, 3))   # 22 = 10+5+7 (new version)

#include <iostream>
#include <memory>
#include <vector>

struct SegNode {
    long long sum;
    std::shared_ptr<SegNode> left, right;
    SegNode(long long s, std::shared_ptr<SegNode> l = nullptr, std::shared_ptr<SegNode> r = nullptr)
        : sum(s), left(l), right(r) {}
};
using SegPtr = std::shared_ptr<SegNode>;

SegPtr build(const std::vector<int>& arr, int lo, int hi) {
    if (lo == hi) return std::make_shared<SegNode>(arr[lo]);
    int mid = (lo + hi) / 2;
    auto left = build(arr, lo, mid);
    auto right = build(arr, mid + 1, hi);
    return std::make_shared<SegNode>(left->sum + right->sum, left, right);
}

// Returns the root of a NEW version; prev is left completely untouched.
SegPtr update(const SegPtr& prev, int lo, int hi, int idx, int val) {
    if (lo == hi) return std::make_shared<SegNode>(val);
    int mid = (lo + hi) / 2;
    if (idx <= mid) {
        auto newLeft = update(prev->left, lo, mid, idx, val);
        return std::make_shared<SegNode>(newLeft->sum + prev->right->sum, newLeft, prev->right);
    }
    auto newRight = update(prev->right, mid + 1, hi, idx, val);
    return std::make_shared<SegNode>(prev->left->sum + newRight->sum, prev->left, newRight);
}

long long query(const SegPtr& node, int lo, int hi, int ql, int qr) {
    if (qr < lo || hi < ql) return 0;
    if (ql <= lo && hi <= qr) return node->sum;
    int mid = (lo + hi) / 2;
    return query(node->left, lo, mid, ql, qr) + query(node->right, mid + 1, hi, ql, qr);
}

int main() {
    std::vector<int> arr{1, 3, 5, 7, 9, 11};
    int n = arr.size();
    std::vector<SegPtr> roots;
    roots.push_back(build(arr, 0, n - 1));               // version 0
    roots.push_back(update(roots[0], 0, n - 1, 1, 10));  // version 1

    std::cout << query(roots[0], 0, n - 1, 1, 3) << "\n"; // 15
    std::cout << query(roots[1], 0, n - 1, 1, 3) << "\n"; // 22
}

import java.util.ArrayList;
import java.util.List;

public class PersistentSegmentTree {
    static final class SegNode {
        final long sum;
        final SegNode left, right;
        SegNode(long sum, SegNode left, SegNode right) {
            this.sum = sum;
            this.left = left;
            this.right = right;
        }
    }

    static SegNode build(int[] arr, int lo, int hi) {
        if (lo == hi) return new SegNode(arr[lo], null, null);
        int mid = (lo + hi) / 2;
        SegNode left = build(arr, lo, mid);
        SegNode right = build(arr, mid + 1, hi);
        return new SegNode(left.sum + right.sum, left, right);
    }

    // Returns the root of a NEW version; prev is left completely untouched.
    static SegNode update(SegNode prev, int lo, int hi, int idx, int val) {
        if (lo == hi) return new SegNode(val, null, null);
        int mid = (lo + hi) / 2;
        if (idx <= mid) {
            SegNode newLeft = update(prev.left, lo, mid, idx, val);
            return new SegNode(newLeft.sum + prev.right.sum, newLeft, prev.right);
        }
        SegNode newRight = update(prev.right, mid + 1, hi, idx, val);
        return new SegNode(prev.left.sum + newRight.sum, prev.left, newRight);
    }

    static long query(SegNode node, int lo, int hi, int ql, int qr) {
        if (qr < lo || hi < ql) return 0;
        if (ql <= lo && hi <= qr) return node.sum;
        int mid = (lo + hi) / 2;
        return query(node.left, lo, mid, ql, qr) + query(node.right, mid + 1, hi, ql, qr);
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        int n = arr.length;
        List<SegNode> roots = new ArrayList<>();
        roots.add(build(arr, 0, n - 1));                     // version 0
        roots.add(update(roots.get(0), 0, n - 1, 1, 10));    // version 1

        System.out.println(query(roots.get(0), 0, n - 1, 1, 3)); // 15
        System.out.println(query(roots.get(1), 0, n - 1, 1, 3)); // 22
    }
}

The classic competitive-programming use of this structure is answering "how many elements $\le x$ appear in the subarray $[l, r]$" across many historical versions at once: build version $i$ as a segment tree over the value domain after inserting the first $i$ array elements, so roots[i] represents "counts so far, as of position $i$". Querying roots[r] and roots[l-1] for the range of values $\le x$ and subtracting the two counts — the same telescoping trick as a 1D prefix sum, just applied to persistent-tree roots instead of a running total — answers the question in $O(\log(\text{value range}))$ per query. This "persistent segment tree of prefix counts" pattern is exactly what the Hard exercise below asks you to build.

Persistent Trie

Tries are trees too, so nothing new is required: see the Trie Variants lesson for the base trie mechanics (or the Advanced Structures lesson's Trie section if that page is not yet part of your reading list). Inserting a key clones only the $O(\text{key length})$ nodes along the path spelled out by that key's characters, and shares every other branch of the trie with the previous version:

# Ephemeral: node.children[ch] = child; recurse; mutate in place.
# Persistent: clone the node with an updated children map instead:
def insert(node, key, i=0):
    node = node.clone() if node else TrieNode()
    if i == len(key):
        node.is_end = True
        return node
    ch = key[i]
    node.children = dict(node.children)      # shallow copy of the map
    node.children[ch] = insert(node.children.get(ch), key, i + 1)
    return node

This is the identical clone-the-path, share-the-rest pattern already shown twice above for the BST and the segment tree — a full re-implementation would not teach anything new.

7. Finger Trees

8. Complexity Analysis

9. Applications & Alternatives

The alternative to path copying is fat nodes or path copying with node-level versioning (storing a small history of values per node instead of cloning whole nodes), which can reduce memory further for update-heavy workloads at the cost of a more complex query. For most applications, plain path copying as shown above is simpler to implement correctly and is the default choice.

10. Exercises & Mastery

Easy

1. Given the sequence of inserts 7, 3, 9, 1, 5 into an initially empty persistent BST, state, for each insert, exactly which nodes are newly cloned and which nodes (if any) are shared with the previous version.
2. For the same sequence, state how many total node objects exist after all five inserts, and compare that to how many would exist if every insert instead deep-copied the whole tree.

Medium

1. Given the persistent segment tree's build and query functions from Section 6, implement update yourself before looking at the solution, and verify that querying an old root after your update still returns the pre-update values.
2. Extend the persistent BST in Section 5 with a persistent delete that also returns a new root, reasoning about which nodes on the deletion path must be cloned.

Hard

1. Using a persistent segment tree of prefix counts (Section 6), implement k-th smallest element in a range query: given an array and queries of the form "what is the k-th smallest value in $[l, r]$", build one version per prefix and binary-search over the value domain inside each query, using the version-subtraction trick described in Section 6. Warm up first with the plain prefix sums & difference arrays lesson if the subtract-two-prefixes idea itself is unfamiliar — that lesson is not re-derived here.

Review rhythm: tomorrow, redraw the worked example from Section 4 from memory, labeling cloned vs. shared nodes; next week, implement the persistent BST and persistent segment tree in a language you did not use here; several weeks later, find the persistence idea inside a tool you already use (a version control system or an undo stack) and explain it in those terms without looking back at this lesson.

11. Summary Cheat Sheet

• Ephemeral structures have one current state; persistent structures keep every past version fully queryable.
• Path copying: clone only the $O(\log n)$ nodes from the root to the changed node; share every other subtree by reference with the previous version.
• The old root, and everything reachable from it, is never mutated — that is what guarantees old versions stay correct forever.
• Persistent BST insert and persistent segment tree update both return a new root; keep a list of historical roots to query any version.
• Treap split/merge and trie insert persist for free once they are written as "return a new node" instead of "mutate and return void".
• Finger trees are a persistent sequence structure used in functional languages; conceptual only here, since their natural form is not imperative.
• Cost per update: $O(\log n)$ time and space, versus $O(n)$ for a naive full deep copy.
• Classic application: a persistent segment tree of prefix counts answers range rank/k-th-smallest queries across historical array versions.