guest@itl:~/home/data-structures$
templates/persistent-segment-tree.cpp
compilable
$cat templates/persistent-segment-tree

Persistent Segment Tree

Segment tree preserving all versions via path copying — O(log n) per update, O(n + q log n) total memory.

#persistent#segment-tree#versioned#path-copying
Log in to track progress, save custom versions, and organize into collections.Log In
$cat source_code/
cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Node {
    ll val, pref;
    Node *L, *R;
    Node(ll v = 0) : val(v), pref(max(0LL, v)), L(this), R(this) {}
    Node(ll v, ll p, Node* l, Node* r) : val(v), pref(p), L(l), R(r) {}
};

Node* merge(Node* a, Node* b) {
    return new Node(a->val + b->val, max(a->pref, a->val + b->pref), a, b);
}

const int MAXV = 2e5 + 5;
Node* roots[MAXV];
int N;
ll Lx, Rx;

void init(int n, ll lx = 1, ll rx = -1) {
    N = n; Lx = lx; Rx = (rx < lx ? n : rx);
    for (int i = 0; i <= n; i++) roots[i] = new Node();
}

Node* build(ll a[], ll l, ll r) {
    if (l == r) return new Node(a[l]);
    ll mid = l + (r - l) / 2;
    return merge(build(a, l, mid), build(a, mid + 1, r));
}

void build(ll a[]) { roots[0] = build(a, Lx, Rx); }

Node* update(Node* nd, ll pos, ll val, ll lx, ll rx) {
    if (pos < lx || pos > rx) return nd;
    if (lx == rx) return new Node(val);
    ll mid = lx + (rx - lx) / 2;
    Node* l = update(nd->L, pos, val, lx, mid);
    Node* r = update(nd->R, pos, val, mid + 1, rx);
    return merge(l, r);
}

void insert(ll pos, ll val, int cur, int prev) {
    roots[cur] = update(roots[prev], pos, val, Lx, Rx);
}

void update(ll pos, ll val, int cur) {
    roots[cur] = update(roots[cur], pos, val, Lx, Rx);
}

Node* query(Node* nd, ll l, ll r, ll lx, ll rx) {
    if (!nd || lx > r || rx < l) return new Node();
    if (lx >= l && rx <= r) return nd;
    ll mid = (lx + rx) / 2;
    return merge(query(nd->L, l, r, lx, mid), query(nd->R, l, r, mid + 1, rx));
}

ll query(ll l, ll r, int t) { return query(roots[t], l, r, Lx, Rx)->pref; }
58 linesutf-8
$cat explanation_notes.md
notes_viewer --renderedmarkdown (math enabled)

Persistent Segment Tree

Preserves all previous versions after each update via path copying. Each update creates O(log⁡n)O(\log n) new nodes while sharing unmodified subtrees with the prior version.

How It Works

  • roots[t] points to the root of version tt

  • Point update on version tt creates a new path from root to leaf, reusing unchanged subtrees

  • Query any version at any time
  • Operations

  • build(v) — build initial version from array

  • insert(idx, val, curTime, prevTime) — create new version from previous

  • update(idx, val, curTime) — modify current version in-place

  • query(l, r, time) — range query on version tt
  • When to Use

  • kk-th smallest in a range (with coordinate compression)

  • Range queries across historical versions

  • Online queries where rollback is needed
  • Notes

  • Default combine: sum + max prefix sum (modify operation() for your needs)

  • Supports implicit coordinates with range [−109,109][-10^9, 10^9]

  • Self-referencing default node avoids null checks
  • Complexity

  • Build — O(n)O(n)

  • Update — O(log⁡n)O(\log n) time and space per version

  • Query — O(log⁡n)O(\log n)

  • Total space — O(n+qlog⁡n)O(n + q \log n)