Persistent Data Structures

Why Persistent Data Structures Matters

In traditional ephemeral data structures, modifying a value overwrites existing memory. Once an update completes, the previous state is lost forever. When applications require time-travel debugging, historical range queries, rollback capabilities, or functional immutability, copying the entire data structure for every update demands $O(N)$ time and $O(N)$ space per change—a strategy that quickly consumes gigabytes of memory and stalls execution.

Persistent Data Structures solve this challenge by preserving access to all historical versions while supporting updates in optimal time and space. Instead of copying the entire structure, persistent techniques like Path Copying reallocate only the path of nodes modified by an update ($O(\log N)$ nodes in a balanced tree), while linking unchanged child pointers back to existing subtrees from previous versions. This mechanism—known as structural sharing—enables querying any version $V_i$ in $O(\log N)$ time while using only $O(\log N)$ additional space per update, transforming time-travel operations into efficient pointer lookups.

Core Concepts and Terminology

Persistence techniques vary based on how historical versions can be accessed and modified:

1. Partial Persistence: All past versions can be queried, but updates are restricted exclusively to the latest version, creating a linear history timeline.
2. Full Persistence: Any historical version can be both queried and updated, forming a branching tree history of versions.
3. Confluent Persistence: Multiple historical versions can be merged together (e.g., melding two persistent heaps or merging git branches) to form a Directed Acyclic Graph (DAG) history.
4. Path Copying: The core structural technique where updating a node $u$ creates duplicate copies of all ancestors on the path from the root down to $u$, leaving the original nodes untouched.
5. Structural Sharing: Reusing unchanged subtrees across multiple versions without copying them, allowing old and new version roots to share memory safely.

How Persistent Data Structures Works, Step by Step

To perform a persistent point update on a binary tree (such as a Persistent Segment Tree or Persistent BST):

Update Control Flow ($O(\log N)$ Time & Space)

1. Receive Parameters: Target version root prev_root, search range $[L, R]$, update index idx, and new value val.
2. Allocate Node Copy: Create a new node curr copying properties from prev_root (or initializing defaults if creating from scratch).
3. Base Case (Leaf Node Reached): If $L = R$, update curr.val = val and return curr.
4. Recursive Step & Path Copying: Calculate midpoint $mid = \lfloor (L + R) / 2 \rfloor$. If idx <= mid: The updated index falls in the left subtree. Recurse left: curr.left = update(prev_root.left, L, mid, idx, val). * Share Right Subtree: Direct pointer curr.right = prev_root.right (structural sharing).

• Else (idx > mid):
• The updated index falls in the right subtree.
• Recurse right: curr.right = update(prev_root.right, mid + 1, R, idx, val).
• Share Left Subtree: Direct pointer curr.left = prev_root.left (structural sharing).

1. Reaggregate: Compute curr.val = combine(curr.left.val, curr.right.val).
2. Return New Node: Return curr pointer and append it to roots[].

The control flow diagram below illustrates the decision and recursive execution structure for persistent updates:

flowchart TD
A[Start: update prev_node, L, R, idx, val] --> B[Allocate new_node copy of prev_node]
B --> C{Is L == R?}
C -- Yes (Leaf) --> D[new_node.val = val]
D --> E[Return new_node]
C -- No --> F[Compute mid = L + R / 2]
F --> G{Is idx <= mid?}
G -- Yes --> H[new_node.left = update prev_node.left, L, mid, idx, val]
H --> I[new_node.right = prev_node.right SHARE]
G -- No --> J[new_node.right = update prev_node.right, mid+1, R, idx, val]
J --> K[new_node.left = prev_node.left SHARE]
I --> L[new_node.val = combine new_node.left.val, new_node.right.val]
K --> L
L --> E

Worked Example with a Full Trace

Consider a persistent segment tree built over an initial array of size $N = 4$:

$$\text{Array } A = [1, 3, 5, 7]$$

Initial Tree ($V_0$) Construction

• Range $[0, 3]$ sum = $16$ (Root $V_0$).
• Left child $[0, 1]$ sum = $4$ (Leaf $0 = 1$, Leaf $1 = 3$).
• Right child $[2, 3]$ sum = $12$ (Leaf $2 = 5$, Leaf $3 = 7$).

Sequence of Updates

1. Update 1 ($V_1$): Update index $2$ to $9$ based on Version $0$. Array becomes $[1, 3, 9, 7]$. Path copied: Root $V_1 [0, 3]$, Right child $[2, 3]$, Leaf $2$. Left child $[0, 1]$ shared from $V_0$. New Root $V_1$ sum = $4 + (9 + 7) = 20$.

1. Update 2 ($V_2$): Update index $0$ to $4$ based on Version $1$. Array becomes $[4, 3, 9, 7]$. Path copied: Root $V_2 [0, 3]$, Left child $[0, 1]$, Leaf $0$. Right child $[2, 3]$ shared from $V_1$. New Root $V_2$ sum = $(4 + 3) + 16 = 23$.

Implementation in Python, C++, and Java

The complete, copy-paste-runnable code implementations below demonstrate a Persistent Segment Tree with point updates and range sum queries across multiple versions. All three language implementations execute identical logic, use the exact same sample dataset, and print identical output.

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


def build(arr, l, r):
    if l == r:
        return Node(arr[l])
    mid = (l + r) // 2
    left_child = build(arr, l, mid)
    right_child = build(arr, mid + 1, r)
    return Node(left_child.val + right_child.val, left_child, right_child)


def update(prev_node, l, r, idx, val):
    if l == r:
        return Node(val)
    mid = (l + r) // 2
    if idx <= mid:
        new_left = update(prev_node.left, l, mid, idx, val)
        return Node(new_left.val + prev_node.right.val, new_left, prev_node.right)
    else:
        new_right = update(prev_node.right, mid + 1, r, idx, val)
        return Node(prev_node.left.val + new_right.val, prev_node.left, new_right)


def query(node, l, r, ql, qr):
    if ql <= l and r <= qr:
        return node.val
    if r < ql or l > qr:
        return 0
    mid = (l + r) // 2
    return query(node.left, l, mid, ql, qr) + query(node.right, mid + 1, r, ql, qr)


if __name__ == "__main__":
    arr = [1, 3, 5, 7]
    n = len(arr)

    roots = []
    # Version 0
    roots.append(build(arr, 0, n - 1))

    # Version 1: update index 2 to 9
    roots.append(update(roots[0], 0, n - 1, 2, 9))

    # Version 2: update index 0 to 4 based on Version 1
    roots.append(update(roots[1], 0, n - 1, 0, 4))

    print(f"Version 0, sum(0, 3): {query(roots[0], 0, n - 1, 0, 3)}")
    print(f"Version 1, sum(0, 3): {query(roots[1], 0, n - 1, 0, 3)}")
    print(f"Version 2, sum(0, 3): {query(roots[2], 0, n - 1, 0, 3)}")
    print(f"Version 0, sum(1, 2): {query(roots[0], 0, n - 1, 1, 2)}")
    print(f"Version 1, sum(1, 2): {query(roots[1], 0, n - 1, 1, 2)}")
    print(f"Version 2, sum(1, 2): {query(roots[2], 0, n - 1, 1, 2)}")

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

struct Node {
    int val;
    std::shared_ptr<Node> left;
    std::shared_ptr<Node> right;

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

std::shared_ptr<Node> build(const std::vector<int>& arr, int l, int r) {
    if (l == r) {
        return std::make_shared<Node>(arr[l]);
    }
    int mid = l + (r - l) / 2;
    auto left_child = build(arr, l, mid);
    auto right_child = build(arr, mid + 1, r);
    return std::make_shared<Node>(left_child->val + right_child->val, left_child, right_child);
}

std::shared_ptr<Node> update(std::shared_ptr<Node> prev_node, int l, int r, int idx, int val) {
    if (l == r) {
        return std::make_shared<Node>(val);
    }
    int mid = l + (r - l) / 2;
    if (idx <= mid) {
        auto new_left = update(prev_node->left, l, mid, idx, val);
        return std::make_shared<Node>(new_left->val + prev_node->right->val, new_left, prev_node->right);
    } else {
        auto new_right = update(prev_node->right, mid + 1, r, idx, val);
        return std::make_shared<Node>(prev_node->left->val + new_right->val, prev_node->left, new_right);
    }
}

int query(std::shared_ptr<Node> node, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        return node->val;
    }
    if (r < ql || l > qr) {
        return 0;
    }
    int mid = l + (r - l) / 2;
    return query(node->left, l, mid, ql, qr) + query(node->right, mid + 1, r, ql, qr);
}

int main() {
    std::vector<int> arr = {1, 3, 5, 7};
    int n = static_cast<int>(arr.size());

    std::vector<std::shared_ptr<Node>> roots;
    // Version 0
    roots.push_back(build(arr, 0, n - 1));

    // Version 1: update index 2 to 9
    roots.push_back(update(roots[0], 0, n - 1, 2, 9));

    // Version 2: update index 0 to 4 based on Version 1
    roots.push_back(update(roots[1], 0, n - 1, 0, 4));

    std::cout << "Version 0, sum(0, 3): " << query(roots[0], 0, n - 1, 0, 3) << "\n";
    std::cout << "Version 1, sum(0, 3): " << query(roots[1], 0, n - 1, 0, 3) << "\n";
    std::cout << "Version 2, sum(0, 3): " << query(roots[2], 0, n - 1, 0, 3) << "\n";
    std::cout << "Version 0, sum(1, 2): " << query(roots[0], 0, n - 1, 1, 2) << "\n";
    std::cout << "Version 1, sum(1, 2): " << query(roots[1], 0, n - 1, 1, 2) << "\n";
    std::cout << "Version 2, sum(1, 2): " << query(roots[2], 0, n - 1, 1, 2) << "\n";

    return 0;
}

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

public class Main {
    static class Node {
        int val;
        Node left;
        Node right;

        Node(int val, Node left, Node right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        Node(int val) {
            this(val, null, null);
        }
    }

    static Node build(int[] arr, int l, int r) {
        if (l == r) {
            return new Node(arr[l]);
        }
        int mid = l + (r - l) / 2;
        Node leftChild = build(arr, l, mid);
        Node rightChild = build(arr, mid + 1, r);
        return new Node(leftChild.val + rightChild.val, leftChild, rightChild);
    }

    static Node update(Node prevNode, int l, int r, int idx, int val) {
        if (l == r) {
            return new Node(val);
        }
        int mid = l + (r - l) / 2;
        if (idx <= mid) {
            Node newLeft = update(prevNode.left, l, mid, idx, val);
            return new Node(newLeft.val + prevNode.right.val, newLeft, prevNode.right);
        } else {
            Node newRight = update(prevNode.right, mid + 1, r, idx, val);
            return new Node(prevNode.left.val + newRight.val, prevNode.left, newRight);
        }
    }

    static int query(Node node, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) {
            return node->val;
        }
        if (r < ql || l > qr) {
            return 0;
        }
        int mid = l + (r - l) / 2;
        return query(node.left, l, mid, ql, qr) + query(node.right, mid + 1, r, ql, qr);
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7};
        int n = arr.length;

        List<Node> roots = new ArrayList<>();
        // Version 0
        roots.add(build(arr, 0, n - 1));

        // Version 1: update index 2 to 9
        roots.add(update(roots.get(0), 0, n - 1, 2, 9));

        // Version 2: update index 0 to 4 based on Version 1
        roots.add(update(roots.get(1), 0, n - 1, 0, 4));

        System.out.println("Version 0, sum(0, 3): " + query(roots.get(0), 0, n - 1, 0, 3));
        System.out.println("Version 1, sum(0, 3): " + query(roots.get(1), 0, n - 1, 0, 3));
        System.out.println("Version 2, sum(0, 3): " + query(roots.get(2), 0, n - 1, 0, 3));
        System.out.println("Version 0, sum(1, 2): " + query(roots.get(0), 0, n - 1, 1, 2));
        System.out.println("Version 1, sum(1, 2): " + query(roots.get(1), 0, n - 1, 1, 2));
        System.out.println("Version 2, sum(1, 2): " + query(roots.get(2), 0, n - 1, 1, 2));
    }
}

Complexity, Correctness, and Invariants

Comparing structural persistence techniques illustrates key time, space, and complexity trade-offs:

Variants, Pitfalls, and Optimizations

Common Variants

1. Persistent Segment Trees: Standard persistent tree used for dynamic range $K$-th element queries (MKTHNUM) and range frequency counts over past prefix states.
2. Persistent Treaps / Balanced Trees: Supports persistent array operations with insertions, deletions, and range splits/concatenations in $O(\log N)$ time and space per update.
3. Persistent Disjoint Set Union (DSU): Implemented using a persistent array for parent pointers. Requires disabling path compression (or using rank-based union only) to maintain $O(\log N)$ time per operation without mutating past paths.

Practice Problems and Real-World Use

Persistent data structures underpin modern version control systems, functional programming runtime libraries, and advanced geometric query algorithms: