# How to Implement Persistent Segment Trees for Versioned Data Queries

> Learn to implement persistent segment trees for efficient versioned data queries. Store historical array versions and query past states in O(log n) time. Master this advanced data structure.

- Repository: [hzwer/shareoi](https://github.com/hzwer/shareoi)
- Tags: how-to-guide
- Published: 2026-03-03

---

**A persistent segment tree creates immutable copies of nodes during updates, allowing you to store every historical version of an array and query any past state in O(log n) time.**

A persistent segment tree (also called a functional segment tree) is essential for problems requiring **versioned data queries**—where you must access the state of a dataset at specific points in time. According to the lecture materials in the `hzwer/shareoi` repository, this data structure achieves persistence through copy-on-write semantics, ensuring that each update generates a new root while sharing unchanged subtrees with previous versions.

## Core Architecture for Persistent Segment Trees

The implementation relies on path copying rather than modifying nodes in place. When you update a single element, you create new nodes only along the path from the root to that leaf, while reusing pointers to existing subtrees.

| Component | Purpose | Implementation Details |
|-----------|---------|------------------------|
| **Node structure** | Stores segment range aggregates and child pointers. | As illustrated in `数据结构/线段树_方泓杰.pdf`, nodes contain `sum` (or min/max), `left` pointer, and `right` pointer. |
| **Version roots array** | `roots[v]` stores the root pointer for version `v`. | The concept of maintaining multiple versions is detailed in `数据结构/线段树_翁家翌 & 黄哲威.pdf`, which discusses versioned segment tree techniques. |
| **Copy-on-write update** | Creates new nodes only along the update path. | This mirrors the merging patterns shown in `数据结构/线段树的合并.pptx`, where subtrees are shared rather than duplicated. |
| **Query operation** | Standard range query executed on a specific version root. | Identical to standard segment tree queries; you simply pass the desired version's root pointer. |

## Step-by-Step Implementation Guide

### Node Structure and Version Management

Define a node class with aggregate values and child pointers. Maintain a vector or array of root pointers where each index represents a version number.

```cpp
struct Node {
    long long sum;
    Node *l, *r;
    Node(long long v = 0, Node* L = nullptr, Node* R = nullptr)
        : sum(v), l(L), r(R) {}
};

vector<Node*> roots;  // roots[0] = initial version, roots[1] = first update, etc.

```

### Building the Initial Version

Construct the tree recursively from the initial array. This creates the base version (version 0) that all subsequent versions will reference.

```cpp
Node* build(int lo, int hi, const vector<long long>& a) {
    if (lo == hi) return new Node(a[lo]);
    int mid = (lo + hi) / 2;
    Node* left = build(lo, mid, a);
    Node* right = build(mid + 1, hi, a);
    return new Node(left->sum + right->sum, left, right);
}

```

### Copy-on-Write Updates

When updating a position, create new nodes along the path from root to leaf. Reuse unchanged child pointers to share subtrees with the previous version.

```cpp
Node* update(Node* cur, int lo, int hi, int pos, long long val) {
    if (lo == hi) return new Node(val);  // new leaf node
    
    int mid = (lo + hi) / 2;
    if (pos <= mid) {
        Node* newLeft = update(cur->l, lo, mid, pos, val);
        return new Node(newLeft->sum + cur->r->sum, newLeft, cur->r);
    } else {
        Node* newRight = update(cur->r, mid + 1, hi, pos, val);
        return new Node(cur->l->sum + newRight->sum, cur->l, newRight);
    }
}

```

### Querying Historical Versions

Execute standard segment tree range queries by passing the specific version's root pointer.

```cpp
long long query(Node* cur, int lo, int hi, int L, int R) {
    if (!cur || R < lo || hi < L) return 0;
    if (L <= lo && hi <= R) return cur->sum;
    int mid = (lo + hi) / 2;
    return query(cur->l, lo, mid, L, R) + 
           query(cur->r, mid + 1, hi, L, R);
}

```

## Complete Working Examples

### C++ Implementation

This complete example demonstrates versioned range sum queries with point updates:

```cpp
#include <bits/stdc++.h>
using namespace std;

struct Node {
    long long sum;
    Node *l, *r;
    Node(long long v = 0, Node* L = nullptr, Node* R = nullptr)
        : sum(v), l(L), r(R) {}
};

vector<Node*> roots;

Node* build(int lo, int hi, const vector<long long>& a) {
    if (lo == hi) return new Node(a[lo]);
    int mid = (lo + hi) / 2;
    Node* left = build(lo, mid, a);
    Node* right = build(mid + 1, hi, a);
    return new Node(left->sum + right->sum, left, right);
}

Node* update(Node* cur, int lo, int hi, int pos, long long val) {
    if (lo == hi) return new Node(val);
    int mid = (lo + hi) / 2;
    if (pos <= mid)
        return new Node(cur->l->sum + cur->r->sum,
                       update(cur->l, lo, mid, pos, val), cur->r);
    else
        return new Node(cur->l->sum + cur->r->sum,
                       cur->l, update(cur->r, mid + 1, hi, pos, val));
}

long long query(Node* cur, int lo, int hi, int L, int R) {
    if (!cur || R < lo || hi < L) return 0;
    if (L <= lo && hi <= R) return cur->sum;
    int mid = (lo + hi) / 2;
    return query(cur->l, lo, mid, L, R) + query(cur->r, mid + 1, hi, L, R);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, q;
    cin >> n >> q;
    vector<long long> a(n);
    for (auto &x : a) cin >> x;
    
    roots.push_back(build(0, n - 1, a));
    
    for (int i = 0; i < q; ++i) {
        int type;
        cin >> type;
        if (type == 1) {
            int ver, idx;
            long long val;
            cin >> ver >> idx >> val;
            roots.push_back(update(roots[ver], 0, n - 1, idx, val));
        } else {
            int ver, l, r;
            cin >> ver >> l >> r;
            cout << query(roots[ver], 0, n - 1, l, r) << '\n';
        }
    }
}

```

### Python Implementation

For Python implementations of persistent segment trees for versioned data queries:

```python
class Node:
    __slots__ = ('val', 'l', 'r')
    def __init__(self, val=0, l=None, r=None):
        self.val, self.l, self.r = val, l, r

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

def update(node, lo, hi, pos, v):
    if lo == hi:
        return Node(v)
    mid = (lo + hi) // 2
    if pos <= mid:
        left = update(node.l, lo, mid, pos, v)
        return Node(left.val + node.r.val, left, node.r)
    else:
        right = update(node.r, mid+1, hi, pos, v)
        return Node(node.l.val + right.val, node.l, right)

def query(node, lo, hi, L, R):
    if not node or R < lo or hi < L:
        return 0
    if L <= lo and hi <= R:
        return node.val
    mid = (lo + hi) // 2
    return query(node.l, lo, mid, L, R) + query(node.r, mid+1, hi, L, R)

```

### Java Skeleton

```java
class PSTNode {
    long sum;
    PSTNode left, right;
    PSTNode(long s, PSTNode l, PSTNode r) { 
        sum = s; left = l; right = r; 
    }
}

public class PersistentSegmentTree {
    int n;
    java.util.List<PSTNode> versions = new java.util.ArrayList<>();
    
    PSTNode build(long[] a, int l, int r) { 
        if (l == r) return new PSTNode(a[l], null, null);
        int mid = (l + r) / 2;
        PSTNode left = build(a, l, mid);
        PSTNode right = build(a, mid + 1, r);
        return new PSTNode(left.sum + right.sum, left, right);
    }
    
    PSTNode update(PSTNode cur, int l, int r, int pos, long val) {
        if (l == r) return new PSTNode(val, null, null);
        int mid = (l + r) / 2;
        if (pos <= mid) {
            PSTNode newLeft = update(cur.left, l, mid, pos, val);
            return new PSTNode(newLeft.sum + cur.right.sum, newLeft, cur.right);
        } else {
            PSTNode newRight = update(cur.right, mid + 1, r, pos, val);
            return new PSTNode(cur.left.sum + newRight.sum, cur.left, newRight);
        }
    }
    
    long query(PSTNode cur, int l, int r, int ql, int qr) {
        if (cur == null || qr < l || r < ql) return 0;
        if (ql <= l && r <= qr) return cur.sum;
        int mid = (l + r) / 2;
        return query(cur.left, l, mid, ql, qr) + 
               query(cur.right, mid + 1, r, ql, qr);
    }
}

```

## Key Resources from hzwer/shareoi

The `hzwer/shareoi` repository contains lecture materials that provide the theoretical foundation for implementing persistent segment trees for versioned data queries. While the repository does not contain direct source code implementations, these documents explain the underlying mechanics:

- **`数据结构/线段树_方泓杰.pdf`**: Provides detailed coverage of segment tree construction, node structures, and recursive update patterns. The node layout described here forms the basis for the immutable nodes used in persistent implementations.

- **`数据结构/线段树_翁家翌 & 黄哲威.pdf`**: Discusses techniques for maintaining multiple versions of segment trees, which directly aligns with the persistence concept of storing historical states.

- **`数据结构/线段树的合并.pptx`**: Explains subtree sharing and merging strategies. The copy-on-write approach in persistent segment trees applies similar pointer reuse logic to minimize memory consumption.

- **[`README.md`](https://github.com/hzwer/shareoi/blob/main/README.md)**: Lists available lecture topics and provides navigation to the specific segment tree resources mentioned above.

## Summary

Implementing **persistent segment trees for versioned data queries** requires these key techniques:

- **Immutable nodes**: Never modify existing nodes; create new copies along the update path while sharing unchanged subtrees.
- **Version root tracking**: Store each version's root pointer in an array (`roots[v]`) to enable O(1) access to any historical state.
- **Copy-on-write updates**: During `update()`, recursively descend the tree and allocate new nodes only where the path intersects the target position, reusing existing pointers for the other child.
- **O(log n) complexity**: Both updates and queries operate in logarithmic time relative to array size, with each update creating exactly O(log n) new nodes.
- **Memory efficiency**: Total memory usage is O(n + m·log n) for m updates, achieved through structural sharing between versions.

## Frequently Asked Questions

### What is the memory overhead of persistent segment trees?

Each point update creates O(log n) new nodes along the path from root to leaf, while reusing existing subtrees. For an array of size n with m updates, total memory consumption is O(n + m·log n) nodes. This is significantly more efficient than storing m complete copies of the array, which would require O(m·n) memory.

### How do persistent segment trees differ from regular segment trees?

Standard segment trees modify nodes in place, destroying previous states. **Persistent segment trees** treat nodes as immutable—every update creates a new root and new nodes along the modification path, while sharing unchanged branches with previous versions. This immutability enables time-travel queries where you can ask "what was the sum of range [l,r] at version v?" without affecting current data.

### Can persistent segment trees handle range updates instead of point updates?

Yes, but with modifications. For pure **range updates** (like adding a value to every element in [l,r]), you typically use lazy propagation. However, standard lazy propagation conflicts with persistence because pending updates modify node values. To support persistent range updates, you must either use a **persistent lazy segment tree** (where lazy tags are also copied and pushed down during queries) or convert range updates into point updates using difference arrays if the query pattern allows.

### What are common applications of versioned data queries with persistent segment trees?

Persistent segment trees excel in scenarios requiring historical data access: **offline queries** where you process events in chronological order and answer questions about past states; **k-th order statistics** in subarrays (finding the k-th smallest element in range [l,r] by building a persistent segment tree over value frequencies); **undo/redo functionality** in editors or databases; and **tree path queries** where each root-to-leaf path represents a version, enabling efficient queries on historical tree states.