🗂️Data StructureAdvanced

Persistent Segment Tree

Key Points

•
A persistent segment tree stores every historical version of an array-like data while supporting queries and updates in O(log n) time.
•
Updates do not mutate old nodes; instead they copy only the nodes on the root-to-leaf path (path copying), so each update costs O(log n) extra memory.
•
You can branch from any previous version, creating a version tree useful for undo/redo and time-travel queries.
•
Prefix-persistent frequency trees enable K-th smallest queries in a subarray with O(log n) time using two roots and a downward walk.
•
2D rectangle counting can be solved by sorting on one axis and persisting a 1D segment tree on the other axis.
•
The total memory after m updates is O(n + m log n), where n is the base size and m is the number of updates.
•
Coordinate compression is essential when values are large or sparse; it maps values to ranks in [1..U].
•
Persistence is functional: each version is identified by a root pointer; queries and updates are pure with no side effects.

Prerequisites

→Segment Tree (ephemeral) — Persistent trees extend the standard segment tree; knowing build/update/query on ranges is essential.
→Binary Search — K-th queries and coordinate compression rely on ordered search and descending decisions.
→Coordinate Compression — Mapping large or sparse values to a dense domain [1..U] is necessary for frequency-based persistence.
→Asymptotic Analysis (Big-O) — Understanding O(log n) per operation and O(n + m log n) space is key to applying PST effectively.
→Pointers and Dynamic Memory in C++ — Implementations allocate new nodes per update and reuse subtrees using pointers.
→Recursion and Divide-and-Conquer — Segment tree operations are naturally recursive along tree segments.
→Order Statistics — K-th smallest queries require understanding counts and rank-based navigation.

Detailed Explanation

Tap terms for definitions

01Overview

A persistent segment tree is a data structure that keeps all historical versions of a segment tree after each update. Instead of modifying nodes in place, it creates new nodes only along the path from the root to the updated leaf (path copying) while reusing all unaffected nodes. As a result, both updates and queries run in O(log n) time, and each update adds only O(log n) new nodes in memory, so the total space after m updates is O(n + m log n). Because every version is available by its own root pointer, you can run queries on past states, branch new versions from any older version, and compare two versions to answer powerful queries like how many elements ≤ v between indices l and r.

This persistence paradigm enables classic applications: K-th smallest in a subarray using prefix versions of frequency trees; dynamic offline rectangle counting by sorting on x and persisting frequencies over y; and version control–like undo/redo operations. In competitive programming, persistent segment trees provide deterministic O(log n) time and small constant factors, making them a staple for range statistics and time-travel queries on arrays. They complement ephemeral segment trees (which mutate in place) by trading a small memory overhead for the ability to revisit any prior state exactly.

02Intuition & Analogies

Imagine keeping a diary where you never erase old pages; every time you want to change a line, you write a fresh page that copies most lines from the previous page but rewrites only the lines you changed. That is the persistent segment tree: each page is a version; the unchanged lines are shared, and the changed lines are newly written.

A normal (ephemeral) segment tree mutates nodes when you update a value—like erasing and rewriting parts of a page. In persistence, we duplicate only the nodes along the path from the root to the leaf being updated. All other nodes are safely reused. Because a balanced segment tree has height about log2(n), we copy only O(log n) nodes per update.

Another everyday analogy: think of a directory of shortcuts. Every version is a root shortcut pointing to a tree of folders (nodes). When you update an item at position i, you don’t rebuild the whole directory; you create new shortcuts only along the unique path leading to that item. All other subfolders remain the same and are shared. Now, if you want to answer questions about the past—like “what was the sum on day 5?”—you follow the root pointer for day 5 and query exactly as if it were the current structure.

This sharing makes powerful tricks easy. For example, if you build a prefix array of versions—where version t represents the first t elements—then the difference between two versions encodes what changed between ranges. That lets you count frequencies in [l, r] by subtracting two version roots, and even walk down the tree to find the K-th smallest by deciding at each node whether the K-th element lies in the left or right child.

03Formal Definition

Let A be an array over index domain [1, n]. A persistent segment tree is a rooted binary tree where each internal node represents a segment [L, R] and stores an aggregate (e.g., sum, count, min) of its children. Version v is identified by a root pointer

r_{v}

. The build procedure constructs version

v = 0

from A in O(n). An update op(v, i, val) produces a new version u with root

r_{u}

defined by path copying: along the unique path covering index i, create new nodes whose children are either (1) the unchanged child pointer from

r_{v}

, or (2) the new child pointer produced by recursively updating the corresponding child. All nodes not on the path are shared between versions v and u. If the segment tree is balanced over a static domain [1, n], the height h =

⌈

lo g_{2}

⌉

, and exactly O(h) = O(

lo g

n) nodes are newly allocated per update. Queries (e.g., range sum) on a version v are evaluated as in an ordinary segment tree but start from

r_{v}

. For differential queries between two versions u and v (e.g., frequency counts in a value-compressed domain), the aggregate over a range [L, R] can be computed by subtracting node values seen while descending from

r_{v}

and

r_{u}

, since both trees share structure and represent prefix states. Space after m updates is O(n + m

lo g

n), because the base tree has O(n) nodes and each update adds O(

lo g

n) nodes. Time per query and per point update is O(

lo g

n).

04When to Use

Use a persistent segment tree when you need to query past states or compare different states efficiently without recomputation. Classic scenarios include:

K-th smallest in a subarray: Build prefix versions of a frequency segment tree over coordinate-compressed values. To answer [l, r], compare versions r and l−1 while descending to locate the K-th rank.
Offline 2D rectangle counting: Sort points by x, build versions as you sweep x and update frequencies over compressed y. Then query counts in [x1, x2] × [y1, y2] via two prefix roots.
Undo/redo or branching timelines: Maintain multiple timelines of updates without side effects. Each new update branches a new version from any chosen ancestor.
Time-travel statistics: Support queries like sum/min/max on a version from earlier steps; compare aggregates between two times.
Batched updates with future queries: If updates are known ahead (or not too many), persistence lets you cache all intermediate states and answer many queries quickly.

Avoid PST if you need heavy range updates that modify large portions (e.g., lazy propagation with range assignments) under strict memory limits; while possible, persistent lazy trees are more complex and memory intensive. For purely online K-th or order statistics with frequent insert/erase on a multiset, a balanced BST or Fenwick tree might suffice. Use PST when you specifically need multi-version access or differential queries between versions.

⚠️Common Mistakes

Forgetting coordinate compression: K-th and rectangle queries rely on frequency trees over ranks 1..U. Without compression, the value domain might be huge, causing excessive memory or incorrect indexing.
Mixing 0-based and 1-based indices: Persistent segment trees are usually implemented on [1..n]. Off-by-one errors in build/update/query boundaries are a frequent source of bugs.
Not reusing nodes: Accidentally rebuilding subtrees instead of copying only the root-to-leaf path leads to O(n) per update and memory blow-up. Ensure only O(log n) nodes are created per update.
Incorrect difference logic for two versions: For K-th queries, the left-count is left(vRoot) − left(uRoot). Using the wrong pair of versions (e.g., r vs. l) or subtracting in the wrong order will misplace K and produce wrong answers.
Overflow in aggregates: Sums can exceed 32-bit range. Use 64-bit types (long long) for counts/sums. For count trees, sums still fit in 32-bit if n ≤ 2e9? Prefer 64-bit to be safe.
Excessive recursion depth or heap fragmentation: In extremely large inputs, stack recursion depth log2(n) is safe, but custom memory pools (arrays) avoid new/delete overhead and reduce fragmentation.
Building from arbitrary values in K-th queries: The PST for K-th should be built as prefix frequency versions, not as prefix sums of original values. Each update should increment the frequency of the rank at position i by +1, not assign the raw value.

Key Formulas

Tree Height

h = ⌈ lo g_{2} n ⌉

Explanation: A complete segment tree over n leaves has height h. This bounds the number of nodes touched on any root-to-leaf path.

Per-operation Time

T_{update} (n) = T_{query} (n) = O (lo g n)

Explanation: Both updates (by path copying) and queries (by descending through relevant segments) visit O(log n) nodes.

Total Space

S (m, n) = O (n + m lo g n)

Explanation: The initial build uses O(n) nodes; each of the m updates allocates O(log n) new nodes along a path.

Nodes Added per Update

N_{new per update} \leq c \cdot ⌈ lo g_{2} n ⌉

Explanation: A constant number of nodes (typically 1) are created at each level on the path to a leaf, yielding O(log n) new nodes.

Prefix Difference Count

count_{[l, r]} (\leq v) = Q (r, v) - Q (l - 1, v)

Explanation: If Q(t, v) returns the number of $e l e m e n t s \leq v$ among the first t elements using version t, then counts over [l, r] are differences of two prefixes.

K-th Descent Rule

Kth (l, r, k) : go left if (L_{r} - L_{l - 1}) \geq k, else k \leftarrow k - (L_{r} - L_{l - 1}) and go right

Explanation: At each node, L_* denotes the left-child count at that version. Compare counts between r and l−1 to choose the branch and adjust k.

Rectangle Counting via Prefix Roots

RectCount ([x_{1}, x_{2}] \times [y_{1}, y_{2}]) = Q (R, y_{1}, y_{2}) - Q (L - 1, y_{1}, y_{2})

Explanation: After sorting by x and building prefix versions, the number of points inside the rectangle is the difference between two range-sum queries on y using the appropriate prefix indices.

Build Time

T_{build} (n) = O (n)

Explanation: Building the initial segment tree over n leaves takes linear time when done bottom-up or via recursion.

Complexity Analysis

Let n be the size of the indexed domain [1..n], and let m be the number of updates (versions beyond the base). A persistent segment tree is a perfectly balanced binary tree, so its height is h = ⌈log2 n⌉. Each point update copies exactly one node per level along a root-to-leaf path, so it creates O(h) = O(log n) new nodes. Queries (e.g., range sum or count) visit at most two nodes per level and thus also cost O(log n) time. Space usage is dominated by the sum of newly created nodes. The base build needs O(n) nodes. After m updates, the total number of nodes is O(n + m log n), assuming constant-size node payloads (aggregate plus two pointers). In practical implementations, constants are small: each update adds roughly one node per level. For prefix-persistent constructions (e.g., K-th queries), building versions for all prefixes

i = 1

..N requires O(N log U) nodes, where U is the number of compressed distinct values. For K-th smallest in [l, r], the query uses two roots (r and l−1) and descends h levels, computing left

C o u n t = s u m (l e f t_{r}

) − sum(

l e f t_{l - 1}

) at each step; the time is O(log U) and space per query is O(1). For 2D rectangle counting with M points, sorting by x is O(M log M), building prefix versions is O(M log

U_{y}

), and each rectangle query is O(log

U_{y}

). If versions branch arbitrarily, the same per-update and per-query bounds hold per branch, since each update still only copies O(log n) nodes. Memory caveats arise with large m: since total nodes scale linearly with m log n, a tight memory limit may require using custom memory pools, pointer compression, or iterative commands that free unused versions (if acceptable).

Code Examples

Persistent Segment Tree for Range Sum with Branching Versions

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Persistent Segment Tree (range sum, point update)
5 // Demonstrates: building, updating from any version (branching), querying sums on versions
6 
7 struct Node {
8     long long sum;
9     Node *l, *r;
10     Node(long long s = 0, Node* L = nullptr, Node* R = nullptr) : sum(s), l(L), r(R) {}
11 };
12 
13 // Build initial tree from array a[tl..tr]
14 Node* build(const vector<long long>& a, int tl, int tr) {
15     if (tl == tr) return new Node(a[tl], nullptr, nullptr);
16     int tm = (tl + tr) >> 1;
17     Node* left = build(a, tl, tm);
18     Node* right = build(a, tm + 1, tr);
19     return new Node(left->sum + right->sum, left, right);
20 }
21 
22 // Persistent point update: set position pos to new value val (or do delta logic if desired)
23 Node* update_set(Node* v, int tl, int tr, int pos, long long val) {
24     if (tl == tr) {
25         // Create a new leaf with updated value; old leaf remains intact
26         return new Node(val, nullptr, nullptr);
27     }
28     int tm = (tl + tr) >> 1;
29     if (pos <= tm) {
30         // Copy this node; update left child persistently; reuse right child
31         Node* newLeft = update_set(v->l, tl, tm, pos, val);
32         return new Node(newLeft->sum + v->r->sum, newLeft, v->r);
33     } else {
34         Node* newRight = update_set(v->r, tm + 1, tr, pos, val);
35         return new Node(v->l->sum + newRight->sum, v->l, newRight);
36     }
37 }
38 
39 // Range sum query on version root v over [l, r]
40 long long query_sum(Node* v, int tl, int tr, int l, int r) {
41     if (!v || l > r) return 0; // safety
42     if (l == tl && r == tr) return v->sum;
43     int tm = (tl + tr) >> 1;
44     return query_sum(v->l, tl, tm, l, min(r, tm)) +
45            query_sum(v->r, tm + 1, tr, max(l, tm + 1), r);
46 }
47 
48 int main() {
49     ios::sync_with_stdio(false);
50     cin.tie(nullptr);
51 
52     // Example array (1-indexed for simplicity)
53     int n = 8;
54     vector<long long> a(n + 1);
55     for (int i = 1; i <= n; ++i) a[i] = i; // a = [1,2,3,4,5,6,7,8]
56 
57     // Build base version 0
58     Node* root0 = build(a, 1, n);
59 
60     // Create version 1 from version 0: set a[3] = 100
61     Node* root1 = update_set(root0, 1, n, 3, 100);
62 
63     // Create version 2 from version 1: set a[5] = -5
64     Node* root2 = update_set(root1, 1, n, 5, -5);
65 
66     // Branching: Create version 3 from version 0 directly: set a[4] = 40
67     Node* root3 = update_set(root0, 1, n, 4, 40);
68 
69     // Queries
70     cout << "Sum[1,8] in v0: " << query_sum(root0, 1, n, 1, 8) << "\n";     // 36
71     cout << "Sum[1,8] in v1: " << query_sum(root1, 1, n, 1, 8) << "\n";     // 36 - 3 + 100 = 133
72     cout << "Sum[4,6] in v2: " << query_sum(root2, 1, n, 4, 6) << "\n";     // 4->4,5->-5,6->6 -> 5
73     cout << "Sum[3,5] in v3: " << query_sum(root3, 1, n, 3, 5) << "\n";     // 3->3,4->40,5->5 -> 48
74 
75     // Notes:
76     // - All roots (root0, root1, root2, root3) coexist and can be queried independently.
77     // - Memory: each update created O(log n) new nodes.
78 
79     return 0;
80 }
81

This program builds a persistent segment tree holding range sums. Each update returns a new root while older versions remain intact. We demonstrate branching by deriving one version from the base instead of the latest. Queries on different versions show how past and branched states can coexist.

Time: O(log n) per update and per querySpace: O(n) build + O(log n) additional nodes per update; total O(n + m log n)

K-th Smallest in Subarray [l, r] using Prefix-Persistent Frequency Trees

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Persistent segment tree over value ranks to store frequencies.
5 // root[i] represents frequencies of the first i elements (prefix persistence).
6 // Query K-th smallest in [l, r] by descending with two roots: root[r] and root[l-1].
7 
8 struct Node {
9     int sum; // frequency count
10     Node *l, *r;
11     Node(int s = 0, Node* L = nullptr, Node* R = nullptr) : sum(s), l(L), r(R) {}
12 };
13 
14 Node* build_zero(int tl, int tr) {
15     if (tl == tr) return new Node(0, nullptr, nullptr);
16     int tm = (tl + tr) >> 1;
17     Node* left = build_zero(tl, tm);
18     Node* right = build_zero(tm + 1, tr);
19     return new Node(0, left, right);
20 }
21 
22 Node* update_add(Node* v, int tl, int tr, int pos, int delta) {
23     if (tl == tr) return new Node(v->sum + delta, nullptr, nullptr);
24     int tm = (tl + tr) >> 1;
25     if (pos <= tm) {
26         Node* nl = update_add(v->l, tl, tm, pos, delta);
27         return new Node(nl->sum + v->r->sum, nl, v->r);
28     } else {
29         Node* nr = update_add(v->r, tm + 1, tr, pos, delta);
30         return new Node(v->l->sum + nr->sum, v->l, nr);
31     }
32 }
33 
34 int kth(Node* leftRoot, Node* rightRoot, int tl, int tr, int k) {
35     // Returns the rank (compressed value) of the k-th smallest in (right - left)
36     if (tl == tr) return tl;
37     int tm = (tl + tr) >> 1;
38     int leftCount = rightRoot->l->sum - leftRoot->l->sum;
39     if (k <= leftCount) return kth(leftRoot->l, rightRoot->l, tl, tm, k);
40     return kth(leftRoot->r, rightRoot->r, tm + 1, tr, k - leftCount);
41 }
42 
43 int range_count_le(Node* leftRoot, Node* rightRoot, int tl, int tr, int ql, int qr) {
44     // Optional helper: count of elements with rank in [ql, qr]
45     if (ql > qr) return 0;
46     if (ql == tl && qr == tr) return rightRoot->sum - leftRoot->sum;
47     int tm = (tl + tr) >> 1;
48     return range_count_le(leftRoot->l, rightRoot->l, tl, tm, ql, min(qr, tm)) +
49            range_count_le(leftRoot->r, rightRoot->r, tm + 1, tr, max(ql, tm + 1), qr);
50 }
51 
52 int main() {
53     ios::sync_with_stdio(false);
54     cin.tie(nullptr);
55 
56     // Example array
57     vector<int> a = {0, 5, 1, 2, 3, 2, 4, 1}; // 1-indexed: n = 7
58     int n = (int)a.size() - 1;
59 
60     // Coordinate compression
61     vector<int> vals;
62     vals.reserve(n);
63     for (int i = 1; i <= n; ++i) vals.push_back(a[i]);
64     sort(vals.begin(), vals.end());
65     vals.erase(unique(vals.begin(), vals.end()), vals.end());
66     auto rank_of = [&](int x) {
67         return (int)(lower_bound(vals.begin(), vals.end(), x) - vals.begin()) + 1; // ranks in [1..U]
68     };
69     int U = (int)vals.size();
70 
71     // Build prefix roots
72     vector<Node*> root(n + 1, nullptr);
73     root[0] = build_zero(1, U);
74     for (int i = 1; i <= n; ++i) {
75         int r = rank_of(a[i]);
76         root[i] = update_add(root[i - 1], 1, U, r, 1); // add frequency of a[i]
77     }
78 
79     // Query: K-th smallest in [l, r]
80     int l = 2, r = 6, k = 3;
81     int kth_rank = kth(root[l - 1], root[r], 1, U, k);
82     int kth_value = vals[kth_rank - 1];
83     cout << "K-th smallest in [" << l << ", " << r << "] for k=" << k << " is: " << kth_value << "\n";
84 
85     // Optional: Count how many elements in [l, r] lie within values [2, 4]
86     int ql = rank_of(2);
87     int qr = (int)(upper_bound(vals.begin(), vals.end(), 4) - vals.begin()); // last rank with value <=4
88     int cnt = range_count_le(root[l - 1], root[r], 1, U, ql, qr);
89     cout << "Count in [" << l << ", " << r << "] with values in [2,4] is: " << cnt << "\n";
90 
91     return 0;
92 }
93

We build one persistent frequency tree per array prefix. To answer a subarray query [l, r], we subtract the frequencies at version l−1 from those at version r while descending the tree. At each node, the difference of left child counts tells whether the K-th lies left or right. Coordinate compression maps values to ranks.

Time: Build O(n log U); each K-th or count query O(log U)Space: O(n log U) nodes for prefix versions

2D Rectangle Counting via Persistence on y after Sorting by x

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // We have points (x, y). Sort by x and build a persistent segment tree over compressed y.
5 // root[i] := frequencies of y among the first i points in x-sorted order.
6 // Query rectangle [x1, x2] x [y1, y2] by difference of two prefix roots.
7 
8 struct Node {
9     int sum; Node *l, *r;
10     Node(int s = 0, Node* L = nullptr, Node* R = nullptr) : sum(s), l(L), r(R) {}
11 };
12 
13 Node* build_zero(int tl, int tr) {
14     if (tl == tr) return new Node(0, nullptr, nullptr);
15     int tm = (tl + tr) >> 1;
16     Node* L = build_zero(tl, tm);
17     Node* R = build_zero(tm + 1, tr);
18     return new Node(0, L, R);
19 }
20 
21 Node* update_add(Node* v, int tl, int tr, int pos, int delta) {
22     if (tl == tr) return new Node(v->sum + delta, nullptr, nullptr);
23     int tm = (tl + tr) >> 1;
24     if (pos <= tm) {
25         Node* nl = update_add(v->l, tl, tm, pos, delta);
26         return new Node(nl->sum + v->r->sum, nl, v->r);
27     } else {
28         Node* nr = update_add(v->r, tm + 1, tr, pos, delta);
29         return new Node(v->l->sum + nr->sum, v->l, nr);
30     }
31 }
32 
33 int range_query(Node* L, Node* R, int tl, int tr, int ql, int qr) {
34     // Returns count in [ql, qr] within (R - L)
35     if (ql > qr) return 0;
36     if (ql == tl && qr == tr) return R->sum - L->sum;
37     int tm = (tl + tr) >> 1;
38     return range_query(L->l, R->l, tl, tm, ql, min(qr, tm)) +
39            range_query(L->r, R->r, tm + 1, tr, max(ql, tm + 1), qr);
40 }
41 
42 int main() {
43     ios::sync_with_stdio(false);
44     cin.tie(nullptr);
45 
46     // Sample points
47     vector<pair<int,int>> pts = { {1,5}, {2,1}, {2,4}, {3,3}, {5,2}, {5,5} };
48     int M = (int)pts.size();
49 
50     // Coordinate-compress y
51     vector<int> ys; ys.reserve(M);
52     for (auto &p: pts) ys.push_back(p.second);
53     sort(ys.begin(), ys.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end());
54     auto y_rank = [&](int y) { return (int)(lower_bound(ys.begin(), ys.end(), y) - ys.begin()) + 1; };
55     int Uy = (int)ys.size();
56 
57     // Sort by x (stable w.r.t y is fine)
58     sort(pts.begin(), pts.end());
59 
60     // Prepare prefix roots
61     vector<Node*> root(M + 1, nullptr);
62     root[0] = build_zero(1, Uy);
63     vector<int> xs(M);
64     for (int i = 1; i <= M; ++i) {
65         xs[i-1] = pts[i-1].first;
66         int yr = y_rank(pts[i-1].second);
67         root[i] = update_add(root[i-1], 1, Uy, yr, 1);
68     }
69 
70     auto idx_le = [&](int x) {
71         // number of points with coordinate <= x
72         return (int)(upper_bound(xs.begin(), xs.end(), x) - xs.begin());
73     };
74 
75     auto rect_count = [&](int x1, int x2, int y1, int y2) {
76         if (x1 > x2 || y1 > y2) return 0;
77         int R = idx_le(x2); // prefix including x2
78         int L = idx_le(x1 - 1); // prefix strictly before x1
79         int ql = (int)(lower_bound(ys.begin(), ys.end(), y1) - ys.begin()) + 1;
80         int qr = (int)(upper_bound(ys.begin(), ys.end(), y2) - ys.begin());
81         if (ql > qr) return 0;
82         return range_query(root[L], root[R], 1, Uy, ql, qr);
83     };
84 
85     // Example queries
86     cout << "Count in rect x:[2,5], y:[2,5] = " << rect_count(2,5,2,5) << "\n"; // expect 4
87     cout << "Count in rect x:[1,2], y:[1,3] = " << rect_count(1,2,1,3) << "\n"; // expect 2
88     cout << "Count in rect x:[3,3], y:[3,3] = " << rect_count(3,3,3,3) << "\n"; // expect 1
89 
90     return 0;
91 }
92

We sort points by x and build prefix versions of a persistent segment tree over compressed y values. Each prefix root counts how many points with y-rank in each bucket have appeared up to a given x. A rectangle query [x1, x2] × [y1, y2] is answered by subtracting two prefix roots and querying the y-range.

Time: Build O(M log Uy) after sorting O(M log M); each rectangle query O(log Uy)Space: O(M log Uy) nodes for prefix versions

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Persistent Segment Tree (range sum, point update)
5	// Demonstrates: building, updating from any version (branching), querying sums on versions
6
7	struct Node {
8	long long sum;
9	Node l, r;
10	Node(long long s = 0, Node* L = nullptr, Node* R = nullptr) : sum(s), l(L), r(R) {}
11	};
12
13	// Build initial tree from array a[tl..tr]
14	Node* build(const vector<long long>& a, int tl, int tr) {
15	if (tl == tr) return new Node(a[tl], nullptr, nullptr);
16	int tm = (tl + tr) >> 1;
17	Node* left = build(a, tl, tm);
18	Node* right = build(a, tm + 1, tr);
19	return new Node(left->sum + right->sum, left, right);
20	}
21
22	// Persistent point update: set position pos to new value val (or do delta logic if desired)
23	Node* update_set(Node* v, int tl, int tr, int pos, long long val) {
24	if (tl == tr) {
25	// Create a new leaf with updated value; old leaf remains intact
26	return new Node(val, nullptr, nullptr);
27	}
28	int tm = (tl + tr) >> 1;
29	if (pos <= tm) {
30	// Copy this node; update left child persistently; reuse right child
31	Node* newLeft = update_set(v->l, tl, tm, pos, val);
32	return new Node(newLeft->sum + v->r->sum, newLeft, v->r);
33	} else {
34	Node* newRight = update_set(v->r, tm + 1, tr, pos, val);
35	return new Node(v->l->sum + newRight->sum, v->l, newRight);
36	}
37	}
38
39	// Range sum query on version root v over [l, r]
40	long long query_sum(Node* v, int tl, int tr, int l, int r) {
41	if (!v \|\| l > r) return 0; // safety
42	if (l == tl && r == tr) return v->sum;
43	int tm = (tl + tr) >> 1;
44	return query_sum(v->l, tl, tm, l, min(r, tm)) +
45	query_sum(v->r, tm + 1, tr, max(l, tm + 1), r);
46	}
47
48	int main() {
49	ios::sync_with_stdio(false);
50	cin.tie(nullptr);
51
52	// Example array (1-indexed for simplicity)
53	int n = 8;
54	vector<long long> a(n + 1);
55	for (int i = 1; i <= n; ++i) a[i] = i; // a = [1,2,3,4,5,6,7,8]
56
57	// Build base version 0
58	Node* root0 = build(a, 1, n);
59
60	// Create version 1 from version 0: set a[3] = 100
61	Node* root1 = update_set(root0, 1, n, 3, 100);
62
63	// Create version 2 from version 1: set a[5] = -5
64	Node* root2 = update_set(root1, 1, n, 5, -5);
65
66	// Branching: Create version 3 from version 0 directly: set a[4] = 40
67	Node* root3 = update_set(root0, 1, n, 4, 40);
68
69	// Queries
70	cout << "Sum[1,8] in v0: " << query_sum(root0, 1, n, 1, 8) << "\n"; // 36
71	cout << "Sum[1,8] in v1: " << query_sum(root1, 1, n, 1, 8) << "\n"; // 36 - 3 + 100 = 133
72	cout << "Sum[4,6] in v2: " << query_sum(root2, 1, n, 4, 6) << "\n"; // 4->4,5->-5,6->6 -> 5
73	cout << "Sum[3,5] in v3: " << query_sum(root3, 1, n, 3, 5) << "\n"; // 3->3,4->40,5->5 -> 48
74
75	// Notes:
76	// - All roots (root0, root1, root2, root3) coexist and can be queried independently.
77	// - Memory: each update created O(log n) new nodes.
78
79	return 0;
80	}
81

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Persistent segment tree over value ranks to store frequencies.
5	// root[i] represents frequencies of the first i elements (prefix persistence).
6	// Query K-th smallest in [l, r] by descending with two roots: root[r] and root[l-1].
7
8	struct Node {
9	int sum; // frequency count
10	Node l, r;
11	Node(int s = 0, Node* L = nullptr, Node* R = nullptr) : sum(s), l(L), r(R) {}
12	};
13
14	Node* build_zero(int tl, int tr) {
15	if (tl == tr) return new Node(0, nullptr, nullptr);
16	int tm = (tl + tr) >> 1;
17	Node* left = build_zero(tl, tm);
18	Node* right = build_zero(tm + 1, tr);
19	return new Node(0, left, right);
20	}
21
22	Node* update_add(Node* v, int tl, int tr, int pos, int delta) {
23	if (tl == tr) return new Node(v->sum + delta, nullptr, nullptr);
24	int tm = (tl + tr) >> 1;
25	if (pos <= tm) {
26	Node* nl = update_add(v->l, tl, tm, pos, delta);
27	return new Node(nl->sum + v->r->sum, nl, v->r);
28	} else {
29	Node* nr = update_add(v->r, tm + 1, tr, pos, delta);
30	return new Node(v->l->sum + nr->sum, v->l, nr);
31	}
32	}
33
34	int kth(Node* leftRoot, Node* rightRoot, int tl, int tr, int k) {
35	// Returns the rank (compressed value) of the k-th smallest in (right - left)
36	if (tl == tr) return tl;
37	int tm = (tl + tr) >> 1;
38	int leftCount = rightRoot->l->sum - leftRoot->l->sum;
39	if (k <= leftCount) return kth(leftRoot->l, rightRoot->l, tl, tm, k);
40	return kth(leftRoot->r, rightRoot->r, tm + 1, tr, k - leftCount);
41	}
42
43	int range_count_le(Node* leftRoot, Node* rightRoot, int tl, int tr, int ql, int qr) {
44	// Optional helper: count of elements with rank in [ql, qr]
45	if (ql > qr) return 0;
46	if (ql == tl && qr == tr) return rightRoot->sum - leftRoot->sum;
47	int tm = (tl + tr) >> 1;
48	return range_count_le(leftRoot->l, rightRoot->l, tl, tm, ql, min(qr, tm)) +
49	range_count_le(leftRoot->r, rightRoot->r, tm + 1, tr, max(ql, tm + 1), qr);
50	}
51
52	int main() {
53	ios::sync_with_stdio(false);
54	cin.tie(nullptr);
55
56	// Example array
57	vector<int> a = {0, 5, 1, 2, 3, 2, 4, 1}; // 1-indexed: n = 7
58	int n = (int)a.size() - 1;
59
60	// Coordinate compression
61	vector<int> vals;
62	vals.reserve(n);
63	for (int i = 1; i <= n; ++i) vals.push_back(a[i]);
64	sort(vals.begin(), vals.end());
65	vals.erase(unique(vals.begin(), vals.end()), vals.end());
66	auto rank_of = [&](int x) {
67	return (int)(lower_bound(vals.begin(), vals.end(), x) - vals.begin()) + 1; // ranks in [1..U]
68	};
69	int U = (int)vals.size();
70
71	// Build prefix roots
72	vector<Node*> root(n + 1, nullptr);
73	root[0] = build_zero(1, U);
74	for (int i = 1; i <= n; ++i) {
75	int r = rank_of(a[i]);
76	root[i] = update_add(root[i - 1], 1, U, r, 1); // add frequency of a[i]
77	}
78
79	// Query: K-th smallest in [l, r]
80	int l = 2, r = 6, k = 3;
81	int kth_rank = kth(root[l - 1], root[r], 1, U, k);
82	int kth_value = vals[kth_rank - 1];
83	cout << "K-th smallest in [" << l << ", " << r << "] for k=" << k << " is: " << kth_value << "\n";
84
85	// Optional: Count how many elements in [l, r] lie within values [2, 4]
86	int ql = rank_of(2);
87	int qr = (int)(upper_bound(vals.begin(), vals.end(), 4) - vals.begin()); // last rank with value <=4
88	int cnt = range_count_le(root[l - 1], root[r], 1, U, ql, qr);
89	cout << "Count in [" << l << ", " << r << "] with values in [2,4] is: " << cnt << "\n";
90
91	return 0;
92	}
93

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// We have points (x, y). Sort by x and build a persistent segment tree over compressed y.
5	// root[i] := frequencies of y among the first i points in x-sorted order.
6	// Query rectangle [x1, x2] x [y1, y2] by difference of two prefix roots.
7
8	struct Node {
9	int sum; Node l, r;
10	Node(int s = 0, Node* L = nullptr, Node* R = nullptr) : sum(s), l(L), r(R) {}
11	};
12
13	Node* build_zero(int tl, int tr) {
14	if (tl == tr) return new Node(0, nullptr, nullptr);
15	int tm = (tl + tr) >> 1;
16	Node* L = build_zero(tl, tm);
17	Node* R = build_zero(tm + 1, tr);
18	return new Node(0, L, R);
19	}
20
21	Node* update_add(Node* v, int tl, int tr, int pos, int delta) {
22	if (tl == tr) return new Node(v->sum + delta, nullptr, nullptr);
23	int tm = (tl + tr) >> 1;
24	if (pos <= tm) {
25	Node* nl = update_add(v->l, tl, tm, pos, delta);
26	return new Node(nl->sum + v->r->sum, nl, v->r);
27	} else {
28	Node* nr = update_add(v->r, tm + 1, tr, pos, delta);
29	return new Node(v->l->sum + nr->sum, v->l, nr);
30	}
31	}
32
33	int range_query(Node* L, Node* R, int tl, int tr, int ql, int qr) {
34	// Returns count in [ql, qr] within (R - L)
35	if (ql > qr) return 0;
36	if (ql == tl && qr == tr) return R->sum - L->sum;
37	int tm = (tl + tr) >> 1;
38	return range_query(L->l, R->l, tl, tm, ql, min(qr, tm)) +
39	range_query(L->r, R->r, tm + 1, tr, max(ql, tm + 1), qr);
40	}
41
42	int main() {
43	ios::sync_with_stdio(false);
44	cin.tie(nullptr);
45
46	// Sample points
47	vector<pair<int,int>> pts = { {1,5}, {2,1}, {2,4}, {3,3}, {5,2}, {5,5} };
48	int M = (int)pts.size();
49
50	// Coordinate-compress y
51	vector<int> ys; ys.reserve(M);
52	for (auto &p: pts) ys.push_back(p.second);
53	sort(ys.begin(), ys.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end());
54	auto y_rank = [&](int y) { return (int)(lower_bound(ys.begin(), ys.end(), y) - ys.begin()) + 1; };
55	int Uy = (int)ys.size();
56
57	// Sort by x (stable w.r.t y is fine)
58	sort(pts.begin(), pts.end());
59
60	// Prepare prefix roots
61	vector<Node*> root(M + 1, nullptr);
62	root[0] = build_zero(1, Uy);
63	vector<int> xs(M);
64	for (int i = 1; i <= M; ++i) {
65	xs[i-1] = pts[i-1].first;
66	int yr = y_rank(pts[i-1].second);
67	root[i] = update_add(root[i-1], 1, Uy, yr, 1);
68	}
69
70	auto idx_le = [&](int x) {
71	// number of points with coordinate <= x
72	return (int)(upper_bound(xs.begin(), xs.end(), x) - xs.begin());
73	};
74
75	auto rect_count = [&](int x1, int x2, int y1, int y2) {
76	if (x1 > x2 \|\| y1 > y2) return 0;
77	int R = idx_le(x2); // prefix including x2
78	int L = idx_le(x1 - 1); // prefix strictly before x1
79	int ql = (int)(lower_bound(ys.begin(), ys.end(), y1) - ys.begin()) + 1;
80	int qr = (int)(upper_bound(ys.begin(), ys.end(), y2) - ys.begin());
81	if (ql > qr) return 0;
82	return range_query(root[L], root[R], 1, Uy, ql, qr);
83	};
84
85	// Example queries
86	cout << "Count in rect x:[2,5], y:[2,5] = " << rect_count(2,5,2,5) << "\n"; // expect 4
87	cout << "Count in rect x:[1,2], y:[1,3] = " << rect_count(1,2,1,3) << "\n"; // expect 2
88	cout << "Count in rect x:[3,3], y:[3,3] = " << rect_count(3,3,3,3) << "\n"; // expect 1
89
90	return 0;
91	}
92