PK

PKBytes

Explore tracks
Chapter 29: Fenwick Trees and Segment Trees
29.06Intermediate / Advanced4 topics16 min2 interactive animations

Segment tree extensions

Heavier segment-tree designs: merge-sort trees for counting in a range, segment tree beats for range minimum assignments, 2D trees and implicit trees over huge ranges.

Learning goals

  • Count values at most x in a range with a merge-sort tree
  • Explain how segment tree beats bounds the work of range chmin
  • Build a 2D segment tree for point updates and rectangle sums
  • Use an implicit tree for lazy updates on a huge index range

Prerequisites

Advanced segment treesLazy propagationBinary search

Some range questions need more than a number per node: a sorted list, a second maximum, or a tree inside a tree. These designs cost more memory or time per query, and knowing the price tells you when they are worth it.

29.06.1

Merge-sort tree

A **merge-sort tree** stores, in every node, the sorted list of the values in its range. It is built exactly like merge sort, merging the two children's lists, so building takes O(n log n) time and O(n log n) space. A fully covered node answers 'how many values are at most x' by binary search in its list.

A query decomposes [l, r] into O(log n) nodes and does one binary search in each, so it costs O(log² n). The tree does not support cheap updates (a change would have to fix a list at each level). In the preset "Merge-sort tree count" (5 2 8 2 9 4, positions 1..4, x = 4) the nodes show their sorted lists and the answer is 2 (the two 2s).

Java
1class MergeSortTree {
2    private final int n;
3    private final int[][] sorted;
4    MergeSortTree(int[] a) {
5        n = a.length;
6        sorted = new int[4 * n][];
7        build(a, 1, 0, n - 1);
8    }
9    private void build(int[] a, int node, int lo, int hi) {
10        if (lo == hi) { sorted[node] = new int[]{a[lo]}; return; }
11        int mid = lo + (hi - lo) / 2;
12        build(a, 2 * node, lo, mid);
13        build(a, 2 * node + 1, mid + 1, hi);
14        sorted[node] = merge(sorted[2 * node], sorted[2 * node + 1]);
15    }
16    private static int[] merge(int[] x, int[] y) {
17        int[] out = new int[x.length + y.length];
18        for (int i = 0, j = 0, k = 0; k < out.length; k++)
19            out[k] = j >= y.length || (i < x.length && x[i] <= y[j]) ? x[i++] : y[j++];
20        return out;
21    }
22    int countAtMost(int l, int r, int x) { return count(1, 0, n - 1, l, r, x); }
23    private int count(int node, int lo, int hi, int l, int r, int x) {
24        if (r < lo || hi < l) return 0;
25        if (l <= lo && hi <= r) return upperBound(sorted[node], x);       // binary search in the node's list
26        int mid = lo + (hi - lo) / 2;
27        return count(2 * node, lo, mid, l, r, x) + count(2 * node + 1, mid + 1, hi, l, r, x);
28    }
29    private static int upperBound(int[] s, int x) {   // number of elements <= x
30        int lo = 0, hi = s.length;
31        while (lo < hi) {
32            int mid = lo + (hi - lo) / 2;
33            if (s[mid] <= x) lo = mid + 1; else hi = mid;
34        }
35        return lo;
36    }
37}

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.06.2

Segment tree beats

**Segment tree beats** handles updates like a[i] = min(a[i], x) over a range (range chmin) together with range sums. A node stores its maximum, the number of times the maximum occurs, the strict second maximum and the sum. If x is larger than the second maximum but smaller than the maximum, the update changes only the maximum elements, and the node's sum can be fixed in O(1) as sum -= (max - x) × count, with the new maximum left as a tag for the children.

If x is not larger than the second maximum, the node cannot be fixed directly and the update recurses. The surprising result, from the literature, is that the total number of such extra recursions stays small: range chmin with range sum runs in O(log n) amortised time per operation (O(log² n) when combined with range add). The tests below check the code against brute force, but this course does not reproduce the amortised proof.

Java
1class ChminTree {
2    private final int n;
3    private final long[] sum, max1, max2, cnt;   // max2 is the strict second maximum (Long.MIN_VALUE if none)
4    ChminTree(int[] a) {
5        n = a.length;
6        sum = new long[4 * n]; max1 = new long[4 * n]; max2 = new long[4 * n]; cnt = new long[4 * n];
7        build(a, 1, 0, n - 1);
8    }
9    private void build(int[] a, int node, int lo, int hi) {
10        if (lo == hi) { sum[node] = max1[node] = a[lo]; max2[node] = Long.MIN_VALUE; cnt[node] = 1; return; }
11        int mid = lo + (hi - lo) / 2;
12        build(a, 2 * node, lo, mid);
13        build(a, 2 * node + 1, mid + 1, hi);
14        pull(node);
15    }
16    private void pull(int node) {
17        int L = 2 * node, R = L + 1;
18        sum[node] = sum[L] + sum[R];
19        if (max1[L] > max1[R]) { max1[node] = max1[L]; cnt[node] = cnt[L]; max2[node] = Math.max(max2[L], max1[R]); }
20        else if (max1[L] < max1[R]) { max1[node] = max1[R]; cnt[node] = cnt[R]; max2[node] = Math.max(max1[L], max2[R]); }
21        else { max1[node] = max1[L]; cnt[node] = cnt[L] + cnt[R]; max2[node] = Math.max(max2[L], max2[R]); }
22    }
23    private void applyMin(int node, long x) {    // lower the maximum of this node to x (needs max2 < x)
24        if (x >= max1[node]) return;
25        sum[node] -= (max1[node] - x) * cnt[node];
26        max1[node] = x;
27    }
28    private void push(int node) { applyMin(2 * node, max1[node]); applyMin(2 * node + 1, max1[node]); }
29    void chmin(int l, int r, long x) { chmin(1, 0, n - 1, l, r, x); }
30    private void chmin(int node, int lo, int hi, int l, int r, long x) {
31        if (r < lo || hi < l || max1[node] <= x) return;                  // nothing to cut
32        if (l <= lo && hi <= r && max2[node] < x) { applyMin(node, x); return; }   // only the maximum values change
33        push(node);
34        int mid = lo + (hi - lo) / 2;
35        chmin(2 * node, lo, mid, l, r, x);
36        chmin(2 * node + 1, mid + 1, hi, l, r, x);
37        pull(node);
38    }
39    long sum(int l, int r) { return sum(1, 0, n - 1, l, r); }
40    private long sum(int node, int lo, int hi, int l, int r) {
41        if (r < lo || hi < l) return 0;
42        if (l <= lo && hi <= r) return sum[node];
43        push(node);
44        int mid = lo + (hi - lo) / 2;
45        return sum(2 * node, lo, mid, l, r) + sum(2 * node + 1, mid + 1, hi, l, r);
46    }
47    long max(int l, int r) { return max(1, 0, n - 1, l, r); }
48    private long max(int node, int lo, int hi, int l, int r) {
49        if (r < lo || hi < l) return Long.MIN_VALUE;
50        if (l <= lo && hi <= r) return max1[node];
51        push(node);
52        int mid = lo + (hi - lo) / 2;
53        return Math.max(max(2 * node, lo, mid, l, r), max(2 * node + 1, mid + 1, hi, l, r));
54    }
55}
29.06.3

2D segment tree

A **2D segment tree** is a segment tree over the rows in which every node holds a segment tree over the columns. The inner tree of an outer node summarises the rows of that node, column by column. A point update walks down the outer tree; at each outer node it updates the inner tree (for a leaf row it sets the value, for an inner row it recombines the two child rows' inner values). A rectangle query decomposes the row range into O(log R) outer nodes and queries each inner tree on the column range.

Both operations cost O(log R × log C). The price is memory: a naive layout needs 16 × R × C cells (4R by 4C). A 2D Fenwick tree is simpler and smaller for sums, but a 2D segment tree supports operations without an inverse, such as 2D minimum. Updating a whole row range or column range requires lazy propagation in both dimensions, which is rarely worth the complexity.

Java
1class SegmentTree2D {
2    private final int rows, cols;
3    private final long[][] t;
4    SegmentTree2D(int rows, int cols) {
5        this.rows = rows; this.cols = cols;
6        t = new long[4 * rows][4 * cols];
7    }
8    void set(int x, int y, long v) { setX(1, 0, rows - 1, x, y, v); }
9    private void setX(int nx, int lx, int rx, int x, int y, long v) {
10        if (lx < rx) {
11            int mx = lx + (rx - lx) / 2;
12            if (x <= mx) setX(2 * nx, lx, mx, x, y, v); else setX(2 * nx + 1, mx + 1, rx, x, y, v);
13        }
14        setY(nx, lx, rx, 1, 0, cols - 1, y, v);   // after the rows below are done
15    }
16    private void setY(int nx, int lx, int rx, int ny, int ly, int ry, int y, long v) {
17        if (ly == ry) {
18            if (lx == rx) t[nx][ny] = v;                                // a leaf row: the value itself
19            else t[nx][ny] = t[2 * nx][ny] + t[2 * nx + 1][ny];        // an inner row: combine the child rows
20            return;
21        }
22        int my = ly + (ry - ly) / 2;
23        if (y <= my) setY(nx, lx, rx, 2 * ny, ly, my, y, v); else setY(nx, lx, rx, 2 * ny + 1, my + 1, ry, y, v);
24        t[nx][ny] = t[nx][2 * ny] + t[nx][2 * ny + 1];
25    }
26    long sum(int x1, int y1, int x2, int y2) { return sumX(1, 0, rows - 1, x1, x2, y1, y2); }
27    private long sumX(int nx, int lx, int rx, int x1, int x2, int y1, int y2) {
28        if (x2 < lx || rx < x1) return 0;
29        if (x1 <= lx && rx <= x2) return sumY(nx, 1, 0, cols - 1, y1, y2);
30        int mx = lx + (rx - lx) / 2;
31        return sumX(2 * nx, lx, mx, x1, x2, y1, y2) + sumX(2 * nx + 1, mx + 1, rx, x1, x2, y1, y2);
32    }
33    private long sumY(int nx, int ny, int ly, int ry, int y1, int y2) {
34        if (y2 < ly || ry < y1) return 0;
35        if (y1 <= ly && ry <= y2) return t[nx][ny];
36        int my = ly + (ry - ly) / 2;
37        return sumY(nx, 2 * ny, ly, my, y1, y2) + sumY(nx, 2 * ny + 1, my + 1, ry, y1, y2);
38    }
39}
29.06.4

Implicit segment tree

An **implicit** segment tree does not store its nodes in an array: nodes are objects that exist only when needed, and the range they cover is implied by the path from the root. It is the dynamic sparse tree of the previous lesson combined with lazy propagation, so it can handle range adds and range sums over an index range of 10^9 using memory proportional to the operations performed.

Because a range update may stop at a node whose children do not exist yet, the push-down step creates the missing children before handing them the tag. The same push is needed by queries. Each operation creates O(log size) nodes at most, so memory is O(operations × log size). The animation of the previous lesson shows the node creation; here the lazy tags are added on top.

Java
1class ImplicitTree {
2    private static class Node { long sum, add; Node left, right; }
3    private final int size;                      // indices 0..size-1
4    private final Node root = new Node();
5    int nodes = 1;
6    ImplicitTree(int size) { this.size = size; }
7    private static long len(int lo, int hi) { return (long) hi - lo + 1; }
8    private void apply(Node n, int lo, int hi, long v) { n.sum += v * len(lo, hi); n.add += v; }
9    private void push(Node n, int lo, int hi) {  // create the children if needed, then hand down the tag
10        int mid = lo + (hi - lo) / 2;
11        if (n.left == null) { n.left = new Node(); nodes++; }
12        if (n.right == null) { n.right = new Node(); nodes++; }
13        if (n.add != 0) {
14            apply(n.left, lo, mid, n.add);
15            apply(n.right, mid + 1, hi, n.add);
16            n.add = 0;
17        }
18    }
19    void rangeAdd(int l, int r, long v) { rangeAdd(root, 0, size - 1, l, r, v); }
20    private void rangeAdd(Node n, int lo, int hi, int l, int r, long v) {
21        if (r < lo || hi < l) return;
22        if (l <= lo && hi <= r) { apply(n, lo, hi, v); return; }
23        push(n, lo, hi);
24        int mid = lo + (hi - lo) / 2;
25        rangeAdd(n.left, lo, mid, l, r, v);
26        rangeAdd(n.right, mid + 1, hi, l, r, v);
27        n.sum = n.left.sum + n.right.sum;
28    }
29    long sum(int l, int r) { return sum(root, 0, size - 1, l, r); }
30    private long sum(Node n, int lo, int hi, int l, int r) {
31        if (r < lo || hi < l) return 0;
32        if (l <= lo && hi <= r) return n.sum;
33        push(n, lo, hi);
34        int mid = lo + (hi - lo) / 2;
35        return sum(n.left, lo, mid, l, r) + sum(n.right, mid + 1, hi, l, r);
36    }
37}

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

  • Count of Smaller Numbers After Self
  • Range Sum Query 2D - Mutable

Advanced

  • Rectangle Area II
  • Count Integers in Intervals
  • Booking Concert Tickets in Groups

Key takeaways

  • A merge-sort tree stores sorted lists: O(n log n) memory, O(log² n) range counting, no cheap updates.
  • Beats keep the maximum, its count and the strict second maximum so that range chmin can usually stop early.
  • A 2D tree is a tree of trees: O(log R × log C) per operation; implicit trees create nodes only where operations touch them.