PK

PKBytes

Explore tracks
Chapter 29: Fenwick Trees and Segment Trees
29.05Intermediate / Advanced6 topics17 min6 interactive animations

Advanced segment trees

Richer node contents: minimum with its index, GCD, the maximum subarray tuple and k-th one, plus persistent and dynamic sparse trees.

Learning goals

  • Store an index next to a minimum and keep ties consistent
  • Use GCD as the combine operation with 0 as its neutral element
  • Combine the four numbers of the maximum-subarray node
  • Find the k-th one by descent and build persistent and sparse trees

Prerequisites

Segment tree fundamentalsKadane's algorithmGCD

The shape of a segment tree never changes; only what each node remembers does. Choose the right summary and the same code answers questions that look unrelated: where is the minimum, what is the best subarray, which position holds the 5th one.

29.05.1

Min/max with index

To find where the minimum lies, not only its value, store the index of the smallest element in each node and compare the elements at the two candidate indices. Choose a tie rule and keep it everywhere: taking the left index on equal values returns the leftmost minimum. The neutral element is 'no index', represented by -1.

In the preset "Minimum with index" (5 2 8 2 9 4, positions 1..4) the minimum 2 occurs at indices 1 and 3; the tree reports index 1, the left one. Nodes are labelled value@index in the animation. A maximum works the same with the comparison reversed.

Java
1class MinIndexTree {
2    private final int n;
3    private final int[] a;
4    private final int[] idx;                     // idx[node]: index of the smallest value in the node's range
5    MinIndexTree(int[] values) {
6        a = values.clone();
7        n = a.length;
8        idx = new int[4 * n];
9        build(1, 0, n - 1);
10    }
11    private int better(int i, int j) {           // the index with the smaller value; ties keep the left one
12        if (i < 0) return j;
13        if (j < 0) return i;
14        return a[j] < a[i] ? j : i;
15    }
16    private void build(int node, int lo, int hi) {
17        if (lo == hi) { idx[node] = lo; return; }
18        int mid = lo + (hi - lo) / 2;
19        build(2 * node, lo, mid);
20        build(2 * node + 1, mid + 1, hi);
21        idx[node] = better(idx[2 * node], idx[2 * node + 1]);
22    }
23    int argMin(int l, int r) { return query(1, 0, n - 1, l, r); }
24    private int query(int node, int lo, int hi, int l, int r) {
25        if (r < lo || hi < l) return -1;         // no index: the neutral element
26        if (l <= lo && hi <= r) return idx[node];
27        int mid = lo + (hi - lo) / 2;
28        return better(query(2 * node, lo, mid, l, r), query(2 * node + 1, mid + 1, hi, l, r));
29    }
30}

Segment tree nodes beyond sums: min+index, GCD, max subarray, k-th one, merge-sort tree

Interactive · edit the input

Your input

Try

segment tree; each node shows min@index · 11 nodes

2@1

[0, 5]

2@1

[0, 2]

2@1

[0, 1]

5@0

[0, 0]

2@1

[1, 1]

8@2

[2, 2]

2@3

[3, 5]

2@3

[3, 4]

2@3

[3, 3]

9@4

[4, 4]

4@5

[5, 5]

Partly inside: recurseFully inside: use itOutside: neutral elementOn the descent pathCandidate

a[]

50
21
82
23
94
45
Setup

Each node stores the minimum of its range and WHERE it is (value@index). Combining two nodes keeps the smaller value; on a tie the left index wins.

Step 1 / 15
Java
1record Min(int val, int idx) {}                              // minimum with its index
2static Min combine(Min x, Min y) { return y.val < x.val ? y : x; }   // ties keep the left index
3static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }  // combine for GCD, neutral element 0
4record Seg(long sum, long pref, long suf, long best) {}      // maximum subarray node
5static Seg combine(Seg x, Seg y) {
6    return new Seg(x.sum + y.sum,
7                   Math.max(x.pref, x.sum + y.pref),         // best prefix may run into the right part
8                   Math.max(y.suf, y.sum + x.suf),
9                   Math.max(Math.max(x.best, y.best), x.suf + y.pref));   // best crossing the middle
10}
11int kthOne(int node, int lo, int hi, int k) {                // k-th 1, counting from 1
12    if (lo == hi) return lo;
13    int mid = lo + (hi - lo) / 2;
14    if (cnt[2 * node] >= k) return kthOne(2 * node, lo, mid, k);         // it is in the left half
15    return kthOne(2 * node + 1, mid + 1, hi, k - cnt[2 * node]);        // skip the left ones
16}
17int countAtMost(int node, int lo, int hi, int l, int r, int x) {         // merge-sort tree
18    if (r < lo || hi < l) return 0;
19    if (l <= lo && hi <= r) return upperBound(sorted[node], x);          // binary search in the node's sorted list
20    int mid = lo + (hi - lo) / 2;
21    return countAtMost(2 * node, lo, mid, l, r, x) + countAtMost(2 * node + 1, mid + 1, hi, l, r, x);
22}

Live state

0 nodes visited

n

6

No condition evaluated on this step
Execution trace (dry run table)Show 15 steps
StepLineStateWhat happens
1L2n=6Each node stores the minimum of its range and WHERE it is (value@index). Combining two nodes keeps the smaller value; on a tie the left index wins.
2L2node=1 range=[0, 5] kind=partial[0, 5] is partly inside: recurse into both children.
3L2node=2 range=[0, 2] kind=partial[0, 2] is partly inside: recurse into both children.
4L2node=4 range=[0, 1] kind=partial[0, 1] is partly inside: recurse into both children.
5L2node=8 range=[0, 0] kind=disjoint[0, 0] is outside [1, 4]: neutral element.
6L2node=9 range=[1, 1] kind=inside[1, 1] is inside: use its stored value 2@1.
7L2node=4 result=2@1Combine the answers for [0, 1]: 2@1.
8L2node=5 range=[2, 2] kind=inside[2, 2] is inside: use its stored value 8@2.
9L2node=2 result=2@1Combine the answers for [0, 2]: 2@1.
10L2node=3 range=[3, 5] kind=partial[3, 5] is partly inside: recurse into both children.
11L2node=6 range=[3, 4] kind=inside[3, 4] is inside: use its stored value 2@3.
12L2node=7 range=[5, 5] kind=disjoint[5, 5] is outside [1, 4]: neutral element.
13L2node=3 result=2@3Combine the answers for [3, 5]: 2@3.
14L2node=1 result=2@1Combine the answers for [0, 5]: 2@1.
15L2return=2@1 nodes visited=9Minimum over a[1..4] = 2 at index 1, after 9 node visits.
29.05.2

GCD

The GCD is associative and commutative, so it is a valid combine operation. Its neutral element is 0, because gcd(0, x) = x, so a disjoint node can return 0. A point update changes one leaf and recomputes the GCD along the path; GCD does not have an inverse (you cannot 'subtract' a value out of a GCD), so a Fenwick tree cannot do this job.

A range GCD costs O(log n) node visits plus the cost of each GCD computation, which is O(log(max value)) by the Euclidean algorithm. In the preset "GCD of a range" (12 18 8 24 36 9, positions 0..3) the answer is 2 after 7 node visits, and the animation shows the GCD of each node.

Java
1class GcdTree {
2    private final int n;
3    private final int[] tree;
4    GcdTree(int[] a) {
5        n = a.length;
6        tree = new int[4 * n];
7        build(a, 1, 0, n - 1);
8    }
9    private static int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); }
10    private void build(int[] a, int node, int lo, int hi) {
11        if (lo == hi) { tree[node] = a[lo]; return; }
12        int mid = lo + (hi - lo) / 2;
13        build(a, 2 * node, lo, mid);
14        build(a, 2 * node + 1, mid + 1, hi);
15        tree[node] = gcd(tree[2 * node], tree[2 * node + 1]);
16    }
17    void update(int i, int v) { update(1, 0, n - 1, i, v); }
18    private void update(int node, int lo, int hi, int i, int v) {
19        if (lo == hi) { tree[node] = v; return; }
20        int mid = lo + (hi - lo) / 2;
21        if (i <= mid) update(2 * node, lo, mid, i, v); else update(2 * node + 1, mid + 1, hi, i, v);
22        tree[node] = gcd(tree[2 * node], tree[2 * node + 1]);
23    }
24    int query(int l, int r) { return query(1, 0, n - 1, l, r); }
25    private int query(int node, int lo, int hi, int l, int r) {
26        if (r < lo || hi < l) return 0;          // gcd(0, x) = x
27        if (l <= lo && hi <= r) return tree[node];
28        int mid = lo + (hi - lo) / 2;
29        return gcd(query(2 * node, lo, mid, l, r), query(2 * node + 1, mid + 1, hi, l, r));
30    }
31}

Segment tree nodes beyond sums: min+index, GCD, max subarray, k-th one, merge-sort tree

Interactive · edit the input

Your input

Try

segment tree; each node shows min@index · 11 nodes

2@1

[0, 5]

2@1

[0, 2]

2@1

[0, 1]

5@0

[0, 0]

2@1

[1, 1]

8@2

[2, 2]

2@3

[3, 5]

2@3

[3, 4]

2@3

[3, 3]

9@4

[4, 4]

4@5

[5, 5]

Partly inside: recurseFully inside: use itOutside: neutral elementOn the descent pathCandidate

a[]

50
21
82
23
94
45
Setup

Each node stores the minimum of its range and WHERE it is (value@index). Combining two nodes keeps the smaller value; on a tie the left index wins.

Step 1 / 15
Java
1record Min(int val, int idx) {}                              // minimum with its index
2static Min combine(Min x, Min y) { return y.val < x.val ? y : x; }   // ties keep the left index
3static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }  // combine for GCD, neutral element 0
4record Seg(long sum, long pref, long suf, long best) {}      // maximum subarray node
5static Seg combine(Seg x, Seg y) {
6    return new Seg(x.sum + y.sum,
7                   Math.max(x.pref, x.sum + y.pref),         // best prefix may run into the right part
8                   Math.max(y.suf, y.sum + x.suf),
9                   Math.max(Math.max(x.best, y.best), x.suf + y.pref));   // best crossing the middle
10}
11int kthOne(int node, int lo, int hi, int k) {                // k-th 1, counting from 1
12    if (lo == hi) return lo;
13    int mid = lo + (hi - lo) / 2;
14    if (cnt[2 * node] >= k) return kthOne(2 * node, lo, mid, k);         // it is in the left half
15    return kthOne(2 * node + 1, mid + 1, hi, k - cnt[2 * node]);        // skip the left ones
16}
17int countAtMost(int node, int lo, int hi, int l, int r, int x) {         // merge-sort tree
18    if (r < lo || hi < l) return 0;
19    if (l <= lo && hi <= r) return upperBound(sorted[node], x);          // binary search in the node's sorted list
20    int mid = lo + (hi - lo) / 2;
21    return countAtMost(2 * node, lo, mid, l, r, x) + countAtMost(2 * node + 1, mid + 1, hi, l, r, x);
22}

Live state

0 nodes visited

n

6

No condition evaluated on this step
Execution trace (dry run table)Show 15 steps
StepLineStateWhat happens
1L2n=6Each node stores the minimum of its range and WHERE it is (value@index). Combining two nodes keeps the smaller value; on a tie the left index wins.
2L2node=1 range=[0, 5] kind=partial[0, 5] is partly inside: recurse into both children.
3L2node=2 range=[0, 2] kind=partial[0, 2] is partly inside: recurse into both children.
4L2node=4 range=[0, 1] kind=partial[0, 1] is partly inside: recurse into both children.
5L2node=8 range=[0, 0] kind=disjoint[0, 0] is outside [1, 4]: neutral element.
6L2node=9 range=[1, 1] kind=inside[1, 1] is inside: use its stored value 2@1.
7L2node=4 result=2@1Combine the answers for [0, 1]: 2@1.
8L2node=5 range=[2, 2] kind=inside[2, 2] is inside: use its stored value 8@2.
9L2node=2 result=2@1Combine the answers for [0, 2]: 2@1.
10L2node=3 range=[3, 5] kind=partial[3, 5] is partly inside: recurse into both children.
11L2node=6 range=[3, 4] kind=inside[3, 4] is inside: use its stored value 2@3.
12L2node=7 range=[5, 5] kind=disjoint[5, 5] is outside [1, 4]: neutral element.
13L2node=3 result=2@3Combine the answers for [3, 5]: 2@3.
14L2node=1 result=2@1Combine the answers for [0, 5]: 2@1.
15L2return=2@1 nodes visited=9Minimum over a[1..4] = 2 at index 1, after 9 node visits.
29.05.3

Maximum subarray

The maximum subarray sum inside a range cannot be built from the two children's maxima alone, because the best subarray may cross the middle. Store four numbers per node: the sum of the range, the best pref (prefix sum), the best suf (suffix sum) and the best subarray. Combining a left node x and a right node y gives: sum = x.sum + y.sum, pref = max(x.pref, x.sum + y.pref), suf = max(y.suf, y.sum + x.suf), and best = max(x.best, y.best, x.suf + y.pref).

The last term is the best subarray that crosses the middle: it ends in the left half (best suffix of x) and starts in the right half (best prefix of y). In the animation each node shows sum/prefix/suffix/best. For the preset "Maximum subarray" (-2 1 -3 4 -1 2 1 -5, positions 1..6) the answer is 6, from 4 -1 2 1.

Java
1class MaxSubTree {
2    record Seg(long sum, long pref, long suf, long best) {
3        static Seg of(long v) { return new Seg(v, v, v, v); }
4        Seg then(Seg y) {                        // this = left part, y = right part
5            return new Seg(sum + y.sum,
6                           Math.max(pref, sum + y.pref),
7                           Math.max(y.suf, y.sum + suf),
8                           Math.max(Math.max(best, y.best), suf + y.pref));   // best crossing the middle
9        }
10    }
11    private final int n;
12    private final Seg[] tree;
13    MaxSubTree(int[] a) {
14        n = a.length;
15        tree = new Seg[4 * n];
16        build(a, 1, 0, n - 1);
17    }
18    private void build(int[] a, int node, int lo, int hi) {
19        if (lo == hi) { tree[node] = Seg.of(a[lo]); return; }
20        int mid = lo + (hi - lo) / 2;
21        build(a, 2 * node, lo, mid);
22        build(a, 2 * node + 1, mid + 1, hi);
23        tree[node] = tree[2 * node].then(tree[2 * node + 1]);
24    }
25    long best(int l, int r) { return query(1, 0, n - 1, l, r).best(); }
26    private Seg query(int node, int lo, int hi, int l, int r) {
27        if (l <= lo && hi <= r) return tree[node];
28        int mid = lo + (hi - lo) / 2;
29        if (r <= mid) return query(2 * node, lo, mid, l, r);             // only the left child overlaps
30        if (l > mid) return query(2 * node + 1, mid + 1, hi, l, r);      // only the right child overlaps
31        return query(2 * node, lo, mid, l, r).then(query(2 * node + 1, mid + 1, hi, l, r));
32    }
33}

Segment tree nodes beyond sums: min+index, GCD, max subarray, k-th one, merge-sort tree

Interactive · edit the input

Your input

Try

segment tree; each node shows min@index · 11 nodes

2@1

[0, 5]

2@1

[0, 2]

2@1

[0, 1]

5@0

[0, 0]

2@1

[1, 1]

8@2

[2, 2]

2@3

[3, 5]

2@3

[3, 4]

2@3

[3, 3]

9@4

[4, 4]

4@5

[5, 5]

Partly inside: recurseFully inside: use itOutside: neutral elementOn the descent pathCandidate

a[]

50
21
82
23
94
45
Setup

Each node stores the minimum of its range and WHERE it is (value@index). Combining two nodes keeps the smaller value; on a tie the left index wins.

Step 1 / 15
Java
1record Min(int val, int idx) {}                              // minimum with its index
2static Min combine(Min x, Min y) { return y.val < x.val ? y : x; }   // ties keep the left index
3static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }  // combine for GCD, neutral element 0
4record Seg(long sum, long pref, long suf, long best) {}      // maximum subarray node
5static Seg combine(Seg x, Seg y) {
6    return new Seg(x.sum + y.sum,
7                   Math.max(x.pref, x.sum + y.pref),         // best prefix may run into the right part
8                   Math.max(y.suf, y.sum + x.suf),
9                   Math.max(Math.max(x.best, y.best), x.suf + y.pref));   // best crossing the middle
10}
11int kthOne(int node, int lo, int hi, int k) {                // k-th 1, counting from 1
12    if (lo == hi) return lo;
13    int mid = lo + (hi - lo) / 2;
14    if (cnt[2 * node] >= k) return kthOne(2 * node, lo, mid, k);         // it is in the left half
15    return kthOne(2 * node + 1, mid + 1, hi, k - cnt[2 * node]);        // skip the left ones
16}
17int countAtMost(int node, int lo, int hi, int l, int r, int x) {         // merge-sort tree
18    if (r < lo || hi < l) return 0;
19    if (l <= lo && hi <= r) return upperBound(sorted[node], x);          // binary search in the node's sorted list
20    int mid = lo + (hi - lo) / 2;
21    return countAtMost(2 * node, lo, mid, l, r, x) + countAtMost(2 * node + 1, mid + 1, hi, l, r, x);
22}

Live state

0 nodes visited

n

6

No condition evaluated on this step
Execution trace (dry run table)Show 15 steps
StepLineStateWhat happens
1L2n=6Each node stores the minimum of its range and WHERE it is (value@index). Combining two nodes keeps the smaller value; on a tie the left index wins.
2L2node=1 range=[0, 5] kind=partial[0, 5] is partly inside: recurse into both children.
3L2node=2 range=[0, 2] kind=partial[0, 2] is partly inside: recurse into both children.
4L2node=4 range=[0, 1] kind=partial[0, 1] is partly inside: recurse into both children.
5L2node=8 range=[0, 0] kind=disjoint[0, 0] is outside [1, 4]: neutral element.
6L2node=9 range=[1, 1] kind=inside[1, 1] is inside: use its stored value 2@1.
7L2node=4 result=2@1Combine the answers for [0, 1]: 2@1.
8L2node=5 range=[2, 2] kind=inside[2, 2] is inside: use its stored value 8@2.
9L2node=2 result=2@1Combine the answers for [0, 2]: 2@1.
10L2node=3 range=[3, 5] kind=partial[3, 5] is partly inside: recurse into both children.
11L2node=6 range=[3, 4] kind=inside[3, 4] is inside: use its stored value 2@3.
12L2node=7 range=[5, 5] kind=disjoint[5, 5] is outside [1, 4]: neutral element.
13L2node=3 result=2@3Combine the answers for [3, 5]: 2@3.
14L2node=1 result=2@1Combine the answers for [0, 5]: 2@1.
15L2return=2@1 nodes visited=9Minimum over a[1..4] = 2 at index 1, after 9 node visits.
29.05.4

Kth one

For a 0/1 array that changes over time, store in each node how many ones its range holds. The k-th one is then found by descent: at a node, if the left child has at least k ones, the answer is in the left half; otherwise subtract the left count from k and go right. The descent stops at a leaf, so a query is O(log n) with no scanning. Flipping a bit is a point update.

This is the same idea as the Fenwick descent for order statistics, but works with any node contents and any update. In the preset "k-th one" (0 1 1 0 1 0 1 1, k = 4) the animation walks from the root, skipping the left half when it has fewer than 4 ones, and ends at index 6.

Java
1class KthOneTree {
2    private final int n;
3    private final int[] cnt;
4    KthOneTree(int[] bits) {
5        n = bits.length;
6        cnt = new int[4 * n];
7        build(bits, 1, 0, n - 1);
8    }
9    private void build(int[] bits, int node, int lo, int hi) {
10        if (lo == hi) { cnt[node] = bits[lo]; return; }
11        int mid = lo + (hi - lo) / 2;
12        build(bits, 2 * node, lo, mid);
13        build(bits, 2 * node + 1, mid + 1, hi);
14        cnt[node] = cnt[2 * node] + cnt[2 * node + 1];
15    }
16    void set(int i, int bit) { set(1, 0, n - 1, i, bit); }
17    private void set(int node, int lo, int hi, int i, int bit) {
18        if (lo == hi) { cnt[node] = bit; return; }
19        int mid = lo + (hi - lo) / 2;
20        if (i <= mid) set(2 * node, lo, mid, i, bit); else set(2 * node + 1, mid + 1, hi, i, bit);
21        cnt[node] = cnt[2 * node] + cnt[2 * node + 1];
22    }
23    int ones() { return cnt[1]; }
24    int kth(int k) {                             // index of the k-th 1 (k counts from 1), or -1
25        if (k < 1 || k > cnt[1]) return -1;
26        int node = 1, lo = 0, hi = n - 1;
27        while (lo < hi) {
28            int mid = lo + (hi - lo) / 2;
29            if (cnt[2 * node] >= k) { node = 2 * node; hi = mid; }                // it is in the left half
30            else { k -= cnt[2 * node]; node = 2 * node + 1; lo = mid + 1; }      // skip the left ones
31        }
32        return lo;
33    }
34}

Segment tree nodes beyond sums: min+index, GCD, max subarray, k-th one, merge-sort tree

Interactive · edit the input

Your input

Try

segment tree; each node shows min@index · 11 nodes

2@1

[0, 5]

2@1

[0, 2]

2@1

[0, 1]

5@0

[0, 0]

2@1

[1, 1]

8@2

[2, 2]

2@3

[3, 5]

2@3

[3, 4]

2@3

[3, 3]

9@4

[4, 4]

4@5

[5, 5]

Partly inside: recurseFully inside: use itOutside: neutral elementOn the descent pathCandidate

a[]

50
21
82
23
94
45
Setup

Each node stores the minimum of its range and WHERE it is (value@index). Combining two nodes keeps the smaller value; on a tie the left index wins.

Step 1 / 15
Java
1record Min(int val, int idx) {}                              // minimum with its index
2static Min combine(Min x, Min y) { return y.val < x.val ? y : x; }   // ties keep the left index
3static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }  // combine for GCD, neutral element 0
4record Seg(long sum, long pref, long suf, long best) {}      // maximum subarray node
5static Seg combine(Seg x, Seg y) {
6    return new Seg(x.sum + y.sum,
7                   Math.max(x.pref, x.sum + y.pref),         // best prefix may run into the right part
8                   Math.max(y.suf, y.sum + x.suf),
9                   Math.max(Math.max(x.best, y.best), x.suf + y.pref));   // best crossing the middle
10}
11int kthOne(int node, int lo, int hi, int k) {                // k-th 1, counting from 1
12    if (lo == hi) return lo;
13    int mid = lo + (hi - lo) / 2;
14    if (cnt[2 * node] >= k) return kthOne(2 * node, lo, mid, k);         // it is in the left half
15    return kthOne(2 * node + 1, mid + 1, hi, k - cnt[2 * node]);        // skip the left ones
16}
17int countAtMost(int node, int lo, int hi, int l, int r, int x) {         // merge-sort tree
18    if (r < lo || hi < l) return 0;
19    if (l <= lo && hi <= r) return upperBound(sorted[node], x);          // binary search in the node's sorted list
20    int mid = lo + (hi - lo) / 2;
21    return countAtMost(2 * node, lo, mid, l, r, x) + countAtMost(2 * node + 1, mid + 1, hi, l, r, x);
22}

Live state

0 nodes visited

n

6

No condition evaluated on this step
Execution trace (dry run table)Show 15 steps
StepLineStateWhat happens
1L2n=6Each node stores the minimum of its range and WHERE it is (value@index). Combining two nodes keeps the smaller value; on a tie the left index wins.
2L2node=1 range=[0, 5] kind=partial[0, 5] is partly inside: recurse into both children.
3L2node=2 range=[0, 2] kind=partial[0, 2] is partly inside: recurse into both children.
4L2node=4 range=[0, 1] kind=partial[0, 1] is partly inside: recurse into both children.
5L2node=8 range=[0, 0] kind=disjoint[0, 0] is outside [1, 4]: neutral element.
6L2node=9 range=[1, 1] kind=inside[1, 1] is inside: use its stored value 2@1.
7L2node=4 result=2@1Combine the answers for [0, 1]: 2@1.
8L2node=5 range=[2, 2] kind=inside[2, 2] is inside: use its stored value 8@2.
9L2node=2 result=2@1Combine the answers for [0, 2]: 2@1.
10L2node=3 range=[3, 5] kind=partial[3, 5] is partly inside: recurse into both children.
11L2node=6 range=[3, 4] kind=inside[3, 4] is inside: use its stored value 2@3.
12L2node=7 range=[5, 5] kind=disjoint[5, 5] is outside [1, 4]: neutral element.
13L2node=3 result=2@3Combine the answers for [3, 5]: 2@3.
14L2node=1 result=2@1Combine the answers for [0, 5]: 2@1.
15L2return=2@1 nodes visited=9Minimum over a[1..4] = 2 at index 1, after 9 node visits.
29.05.5

Persistent segment tree

A **persistent** tree keeps every old version. Instead of changing a node, an update creates new copies of the nodes on the root-to-leaf path and shares every other subtree with the previous version. Each update therefore adds O(log n) nodes and gives a new root; all old roots stay valid and answer queries about their own version.

Run the preset "Persistent: versions" (u2=9 u5=0 q1:0:5 q0:0:5 on 4 2 7 1 5 3): the animation shows each version with the new (copied) nodes highlighted. Version 0 has 11 nodes, the two updates add 3 and 3 more (17 in total, against 33 for three full copies), and the queries read version 1 and the untouched version 0 separately.

Java
1class PersistentSegmentTree {
2    record Node(Node left, Node right, long sum) {}
3    private final int n;
4    private final List<Node> roots = new ArrayList<>();
5    int created;                                 // nodes allocated so far
6    PersistentSegmentTree(int[] a) { n = a.length; roots.add(build(a, 0, n - 1)); }
7    private Node make(Node l, Node r, long s) { created++; return new Node(l, r, s); }
8    private Node build(int[] a, int lo, int hi) {
9        if (lo == hi) return make(null, null, a[lo]);
10        int mid = lo + (hi - lo) / 2;
11        Node l = build(a, lo, mid), r = build(a, mid + 1, hi);
12        return make(l, r, l.sum() + r.sum());
13    }
14    int update(int version, int i, long v) {     // returns the new version number
15        roots.add(update(roots.get(version), 0, n - 1, i, v));
16        return roots.size() - 1;
17    }
18    private Node update(Node node, int lo, int hi, int i, long v) {
19        if (lo == hi) return make(null, null, v);
20        int mid = lo + (hi - lo) / 2;
21        if (i <= mid) {
22            Node l = update(node.left(), lo, mid, i, v);
23            return make(l, node.right(), l.sum() + node.right().sum());
24        }
25        Node r = update(node.right(), mid + 1, hi, i, v);
26        return make(node.left(), r, node.left().sum() + r.sum());        // the other child is shared
27    }
28    long sum(int version, int l, int r) { return sum(roots.get(version), 0, n - 1, l, r); }
29    private long sum(Node node, int lo, int hi, int l, int r) {
30        if (r < lo || hi < l) return 0;
31        if (l <= lo && hi <= r) return node.sum();
32        int mid = lo + (hi - lo) / 2;
33        return sum(node.left(), lo, mid, l, r) + sum(node.right(), mid + 1, hi, l, r);
34    }
35}

Persistent and dynamic sparse segment trees

Interactive · edit the input

Your input

Try

version 0 · 11 nodes

22

[0,5]#11

13

[0,2]#5

6

[0,1]#3

4

[0,0]#1

2

[1,1]#2

7

[2,2]#4

9

[3,5]#10

6

[3,4]#8

1

[3,3]#6

5

[4,4]#7

3

[5,5]#9

New node (copied or created)Shared with an older versionUsed by a queryOn the path

versions (root sums)

22v0
Setup

Version 0 is an ordinary segment tree of 11 nodes. A persistent tree never changes a node: an update copies just the nodes on the root-to-leaf path and shares every other subtree with the old version.

Step 1 / 6
Java
1record Node(Node left, Node right, long sum) {}
2Node build(int[] a, int lo, int hi) {
3    if (lo == hi) return new Node(null, null, a[lo]);
4    int mid = lo + (hi - lo) / 2;
5    Node l = build(a, lo, mid), r = build(a, mid + 1, hi);
6    return new Node(l, r, l.sum + r.sum);
7}
8Node update(Node n, int lo, int hi, int i, long v) {        // returns the NEW root; n stays untouched
9    if (lo == hi) return new Node(null, null, v);
10    int mid = lo + (hi - lo) / 2;
11    if (i <= mid) { Node l = update(n.left, lo, mid, i, v); return new Node(l, n.right, l.sum + n.right.sum); }
12    Node r = update(n.right, mid + 1, hi, i, v);
13    return new Node(n.left, r, n.left.sum + r.sum);          // the other child is shared with the old version
14}
15Node add(Node n, int lo, int hi, int i, long v) {           // dynamic sparse tree: a missing child means all zeros
16    if (n == null) n = new Node();
17    n.sum += v;
18    if (lo == hi) return n;
19    int mid = lo + (hi - lo) / 2;
20    if (i <= mid) n.left = add(n.left, lo, mid, i, v); else n.right = add(n.right, mid + 1, hi, i, v);
21    return n;
22}
23long sum(Node n, int lo, int hi, int l, int r) {
24    if (n == null || r < lo || hi < l) return 0;            // missing node = zeros
25    if (l <= lo && hi <= r) return n.sum;
26    int mid = lo + (hi - lo) / 2;
27    return sum(n.left, lo, mid, l, r) + sum(n.right, mid + 1, hi, l, r);
28}

Live state

11 nodes created1 versions

nodes

11

No condition evaluated on this step
Execution trace (dry run table)Show 6 steps
StepLineStateWhat happens
1L2nodes=11Version 0 is an ordinary segment tree of 11 nodes. A persistent tree never changes a node: an update copies just the nodes on the root-to-leaf path and shares every other subtree with the old version.
2L8op=u2=9 copied=3 shared=8 total nodes=14u2=9: set a[2] = 9. 3 nodes copied along the path (shown as new); the other 8 nodes of this version are shared with version 0, which still answers its own queries unchanged.
3L8op=u5=0 copied=3 shared=8 total nodes=17u5=0: set a[5] = 0. 3 nodes copied along the path (shown as new); the other 8 nodes of this version are shared with version 1, which still answers its own queries unchanged.
4L25op=q1:0:5 return=24q1:0:5: in version 1, the sum of a[0..5] is 24. The old version is intact, so history can be queried.
5L25op=q0:0:5 return=22q0:0:5: in version 0, the sum of a[0..5] is 22. The old version is intact, so history can be queried.
6L13return=17 versions=33 versions for 17 nodes in total. Storing a full copy per version would take 33; path copying adds only O(log n) nodes per update.
29.05.6

Dynamic sparse segment tree

When the index range is huge (say 0 to 10^9) but only a few positions are ever used, a tree stored in an array is impossible. A **dynamic sparse** tree starts with only the root and creates a child the first time an update walks through it. A missing child means 'everything below is zero', which needs no memory and answers queries instantly.

Each update creates at most one node per level, about 31 nodes (one per level, including the root) for 10^9 positions, so memory grows with the number of updates rather than with the size of the universe. The presets "Dynamic sparse: few points" and "Dynamic sparse: same path reused" show it over indices 0..15: updates at 3 and 12 create 9 nodes in total (a full tree would have 31), and updates at 8, 9 and 10 reuse most of the same path (8 nodes).

Java
1class SparseSegmentTree {
2    private static class Node { long sum; Node left, right; }
3    private final int size;                      // indices 0..size-1; size may be 10^9
4    private final Node root = new Node();
5    int nodes = 1;
6    SparseSegmentTree(int size) { this.size = size; }
7    void add(int i, long v) {
8        Node n = root;
9        int lo = 0, hi = size - 1;
10        n.sum += v;
11        while (lo < hi) {
12            int mid = lo + (hi - lo) / 2;
13            if (i <= mid) {
14                if (n.left == null) { n.left = new Node(); nodes++; }      // created on first use
15                n = n.left; hi = mid;
16            } else {
17                if (n.right == null) { n.right = new Node(); nodes++; }
18                n = n.right; lo = mid + 1;
19            }
20            n.sum += v;
21        }
22    }
23    long sum(int l, int r) { return sum(root, 0, size - 1, l, r); }
24    private long sum(Node n, int lo, int hi, int l, int r) {
25        if (n == null || r < lo || hi < l) return 0;       // a missing node is all zeros
26        if (l <= lo && hi <= r) return n.sum;
27        int mid = lo + (hi - lo) / 2;
28        return sum(n.left, lo, mid, l, r) + sum(n.right, mid + 1, hi, l, r);
29    }
30}

Persistent and dynamic sparse segment trees

Interactive · edit the input

Your input

Try

version 0 · 11 nodes

22

[0,5]#11

13

[0,2]#5

6

[0,1]#3

4

[0,0]#1

2

[1,1]#2

7

[2,2]#4

9

[3,5]#10

6

[3,4]#8

1

[3,3]#6

5

[4,4]#7

3

[5,5]#9

New node (copied or created)Shared with an older versionUsed by a queryOn the path

versions (root sums)

22v0
Setup

Version 0 is an ordinary segment tree of 11 nodes. A persistent tree never changes a node: an update copies just the nodes on the root-to-leaf path and shares every other subtree with the old version.

Step 1 / 6
Java
1record Node(Node left, Node right, long sum) {}
2Node build(int[] a, int lo, int hi) {
3    if (lo == hi) return new Node(null, null, a[lo]);
4    int mid = lo + (hi - lo) / 2;
5    Node l = build(a, lo, mid), r = build(a, mid + 1, hi);
6    return new Node(l, r, l.sum + r.sum);
7}
8Node update(Node n, int lo, int hi, int i, long v) {        // returns the NEW root; n stays untouched
9    if (lo == hi) return new Node(null, null, v);
10    int mid = lo + (hi - lo) / 2;
11    if (i <= mid) { Node l = update(n.left, lo, mid, i, v); return new Node(l, n.right, l.sum + n.right.sum); }
12    Node r = update(n.right, mid + 1, hi, i, v);
13    return new Node(n.left, r, n.left.sum + r.sum);          // the other child is shared with the old version
14}
15Node add(Node n, int lo, int hi, int i, long v) {           // dynamic sparse tree: a missing child means all zeros
16    if (n == null) n = new Node();
17    n.sum += v;
18    if (lo == hi) return n;
19    int mid = lo + (hi - lo) / 2;
20    if (i <= mid) n.left = add(n.left, lo, mid, i, v); else n.right = add(n.right, mid + 1, hi, i, v);
21    return n;
22}
23long sum(Node n, int lo, int hi, int l, int r) {
24    if (n == null || r < lo || hi < l) return 0;            // missing node = zeros
25    if (l <= lo && hi <= r) return n.sum;
26    int mid = lo + (hi - lo) / 2;
27    return sum(n.left, lo, mid, l, r) + sum(n.right, mid + 1, hi, l, r);
28}

Live state

11 nodes created1 versions

nodes

11

No condition evaluated on this step
Execution trace (dry run table)Show 6 steps
StepLineStateWhat happens
1L2nodes=11Version 0 is an ordinary segment tree of 11 nodes. A persistent tree never changes a node: an update copies just the nodes on the root-to-leaf path and shares every other subtree with the old version.
2L8op=u2=9 copied=3 shared=8 total nodes=14u2=9: set a[2] = 9. 3 nodes copied along the path (shown as new); the other 8 nodes of this version are shared with version 0, which still answers its own queries unchanged.
3L8op=u5=0 copied=3 shared=8 total nodes=17u5=0: set a[5] = 0. 3 nodes copied along the path (shown as new); the other 8 nodes of this version are shared with version 1, which still answers its own queries unchanged.
4L25op=q1:0:5 return=24q1:0:5: in version 1, the sum of a[0..5] is 24. The old version is intact, so history can be queried.
5L25op=q0:0:5 return=22q0:0:5: in version 0, the sum of a[0..5] is 22. The old version is intact, so history can be queried.
6L13return=17 versions=33 versions for 17 nodes in total. Storing a full copy per version would take 33; path copying adds only O(log n) nodes per update.

Practice ladder

Now try it yourself

Easy

  • Range Sum Query - Mutable

Medium

  • Online Majority Element In Subarray
  • Range Frequency Queries
  • My Calendar II

Advanced

  • Longest Substring of One Repeating Character
  • Count Integers in Intervals
  • Kth Smallest Number in Multiplication Table

Key takeaways

  • Change what a node stores, not the tree: min@index, GCD (neutral element 0), or sum/prefix/suffix/best for maximum subarray.
  • A k-th query descends by node counts; it is O(log n) with no scan.
  • Persistent trees copy one path per update; sparse trees create a node only when an update walks through it.