29.03Intermediate / Advanced6 topics17 min5 interactive animations

Segment tree fundamentals

A segment tree stores an answer for every node of a recursive split of the array, so any range query combines O(log n) stored answers and any point update recomputes one root-to-leaf path.

Learning goals

Describe the recursive interval split and the node layout in an array
Build a segment tree and update one position
Answer range sum, minimum and maximum queries in O(log n)
Pick the neutral element and combine results in the right order

Prerequisites

RecursionBinary treesFenwick tree

A Fenwick tree needs an invertible operation. A segment tree works for any associative operation: minimum, maximum, GCD, even function composition. It trades a little more memory and code for much more flexibility.

29.03.1

Recursive intervals

A segment tree over a[0..n-1] is a binary tree whose root represents the whole array. A node for the range [lo, hi] with lo < hi splits at mid = lo + (hi - lo) / 2 into the left child [lo, mid] and the right child [mid + 1, hi]. A node with lo == hi is a leaf that represents one element. Every node stores a summary of its range, for example its sum.

The tree has exactly 2n - 1 nodes: n leaves and n - 1 internal nodes, because each split turns one node into two. Stored like a heap, with children of node i at 2i and 2i + 1, the largest index can reach almost 4n for awkward sizes, so the array is allocated with 4n cells; the space lesson later shows a tighter bound. The animation draws each node with its range below the value.

Java

1static int nodeCount(int n) { return nodeCount(0, n - 1); }
2private static int nodeCount(int lo, int hi) {   // nodes of the recursive tree over [lo, hi]
3    if (lo == hi) return 1;
4    int mid = lo + (hi - lo) / 2;
5    return 1 + nodeCount(lo, mid) + nodeCount(mid + 1, hi);
6}
7static int maxIndex(int n) { return maxIndex(1, 0, n - 1); }      // largest heap index in use
8private static int maxIndex(int node, int lo, int hi) {
9    if (lo == hi) return node;
10    int mid = lo + (hi - lo) / 2;
11    return Math.max(maxIndex(2 * node, lo, mid), maxIndex(2 * node + 1, mid + 1, hi));
12}

Segment tree: build, range query, point update, iterative version

Interactive · edit the input

segment tree (each node shows its range under the value) · 11 nodes

[0, 5]

[0, 2]

[0, 1]

[0, 0]

[1, 1]

[2, 2]

[3, 5]

[3, 4]

[3, 3]

[4, 4]

[5, 5]

Partly inside: recurseFully inside: use itOutside: neutral elementJust built or recomputedCandidate

a[]

Setup

Build a sum tree over 6 values: each node stores the sum of its range; a leaf stores one element. ? marks nodes not built yet.

Step 1 / 27

Java

1void build(int node, int lo, int hi) {                   // recursive segment tree
2    if (lo == hi) { tree[node] = a[lo]; return; }        // leaf
3    int mid = lo + (hi - lo) / 2;
4    build(2 * node, lo, mid);
5    build(2 * node + 1, mid + 1, hi);
6    tree[node] = tree[2 * node] + tree[2 * node + 1];     // combine
7}
8int query(int node, int lo, int hi, int l, int r) {
9    if (r < lo || hi < l) return 0;                       // disjoint: the neutral element
10    if (l <= lo && hi <= r) return tree[node];            // fully inside: use the stored value
11    int mid = lo + (hi - lo) / 2;
12    return query(2 * node, lo, mid, l, r) + query(2 * node + 1, mid + 1, hi, l, r);
13}
14void update(int node, int lo, int hi, int i, int v) {
15    if (lo == hi) { tree[node] = v; return; }
16    int mid = lo + (hi - lo) / 2;
17    if (i <= mid) update(2 * node, lo, mid, i, v); else update(2 * node + 1, mid + 1, hi, i, v);
18    tree[node] = tree[2 * node] + tree[2 * node + 1];     // recompute on the way back
19}
20int queryIterative(int l, int r) {                        // bottom-up, half-open [l, r)
21    int res = 0;
22    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
23        if ((l & 1) == 1) res += tree[l++];               // l is a right child: take it and move right
24        if ((r & 1) == 1) res += tree[--r];               // r is exclusive: its left neighbour is a right child
25    }
26    return res;
27}

Live state

0 nodes visited

No condition evaluated on this step

Execution trace (dry run table)Show 27 steps

Step	Line	State	What happens
1	L1	n=6	Build a sum tree over 6 values: each node stores the sum of its range; a leaf stores one element. ? marks nodes not built yet.
2	L2	node=8 range=[0, 0] value=2	Leaf [0]: tree[8] = a[0] = 2.
3	L2	node=9 range=[1, 1] value=5	Leaf [1]: tree[9] = a[1] = 5.
4	L6	node=4 range=[0, 1] value=7	Combine the children of [0, 1]: 2 + 5 = 7.
5	L2	node=5 range=[2, 2] value=1	Leaf [2]: tree[5] = a[2] = 1.
6	L6	node=2 range=[0, 2] value=8	Combine the children of [0, 2]: 7 + 1 = 8.
7	L2	node=12 range=[3, 3] value=4	Leaf [3]: tree[12] = a[3] = 4.
8	L2	node=13 range=[4, 4] value=9	Leaf [4]: tree[13] = a[4] = 9.
9	L6	node=6 range=[3, 4] value=13	Combine the children of [3, 4]: 4 + 9 = 13.
10	L2	node=7 range=[5, 5] value=3	Leaf [5]: tree[7] = a[5] = 3.
11	L6	node=3 range=[3, 5] value=16	Combine the children of [3, 5]: 13 + 3 = 16.
12	L6	node=1 range=[0, 5] value=24	Combine the children of [0, 5]: 8 + 16 = 24.
13	L8	l=1 r=4	Query sum(a[1..4]). Each node is outside (return 0, the neutral element), fully inside (use its stored value) or partly inside (ask both children and combine).
14	L11	node=1 range=[0, 5] kind=partial	[0, 5] overlaps [1, 4] only partly: recurse into both children.
15	L11	node=2 range=[0, 2] kind=partial	[0, 2] overlaps [1, 4] only partly: recurse into both children.
16	L11	node=4 range=[0, 1] kind=partial	[0, 1] overlaps [1, 4] only partly: recurse into both children.
17	L9	node=8 range=[0, 0] kind=disjoint	[0, 0] lies outside [1, 4]: return 0.
18	L10	node=9 range=[1, 1] kind=inside	[1, 1] lies inside [1, 4]: use the stored value 5; no need to look at its children.
19	L12	node=4 result=5	Combine the two answers below [0, 1]: 5.
20	L10	node=5 range=[2, 2] kind=inside	[2, 2] lies inside [1, 4]: use the stored value 1; no need to look at its children.
21	L12	node=2 result=6	Combine the two answers below [0, 2]: 6.
22	L11	node=3 range=[3, 5] kind=partial	[3, 5] overlaps [1, 4] only partly: recurse into both children.
23	L10	node=6 range=[3, 4] kind=inside	[3, 4] lies inside [1, 4]: use the stored value 13; no need to look at its children.
24	L9	node=7 range=[5, 5] kind=disjoint	[5, 5] lies outside [1, 4]: return 0.
25	L12	node=3 result=13	Combine the two answers below [3, 5]: 13.
26	L12	node=1 result=19	Combine the two answers below [0, 5]: 19.
27	L12	return=19 nodes visited=9	sum(a[1..4]) = 19, after visiting 9 nodes. At most four nodes per level are visited, so a query is O(log n).

29.03.2

Build

Build recursively: a leaf stores its element, and an internal node stores the combination of its two children, computed after the children are built (post-order). Every node is visited once, so the build is O(n). The animation shows nodes as ? until they are built, so you can watch the leaves appear first and the combinations rise toward the root.

The combine step is the only place that knows what the tree computes. Replace + by Math.min and the same tree answers range minima. The preset "Range sum" builds a sum tree over 2 5 1 4 9 3: the root holds 24.

Java

1class SumTree {
2    private final int n;
3    private final long[] tree;
4    SumTree(int[] a) {
5        n = a.length;
6        tree = new long[4 * n];                  // enough for every heap index of the recursive split
7        build(a, 1, 0, n - 1);
8    }
9    private void build(int[] a, int node, int lo, int hi) {
10        if (lo == hi) { tree[node] = a[lo]; return; }                  // leaf
11        int mid = lo + (hi - lo) / 2;
12        build(a, 2 * node, lo, mid);
13        build(a, 2 * node + 1, mid + 1, hi);
14        tree[node] = tree[2 * node] + tree[2 * node + 1];              // combine
15    }
16    long total() { return tree[1]; }
17}

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(n)

Segment tree: build, range query, point update, iterative version

Interactive · edit the input

segment tree (each node shows its range under the value) · 11 nodes

[0, 5]

[0, 2]

[0, 1]

[0, 0]

[1, 1]

[2, 2]

[3, 5]

[3, 4]

[3, 3]

[4, 4]

[5, 5]

Partly inside: recurseFully inside: use itOutside: neutral elementJust built or recomputedCandidate

a[]

Setup

Build a sum tree over 6 values: each node stores the sum of its range; a leaf stores one element. ? marks nodes not built yet.

Step 1 / 27

Java

1void build(int node, int lo, int hi) {                   // recursive segment tree
2    if (lo == hi) { tree[node] = a[lo]; return; }        // leaf
3    int mid = lo + (hi - lo) / 2;
4    build(2 * node, lo, mid);
5    build(2 * node + 1, mid + 1, hi);
6    tree[node] = tree[2 * node] + tree[2 * node + 1];     // combine
7}
8int query(int node, int lo, int hi, int l, int r) {
9    if (r < lo || hi < l) return 0;                       // disjoint: the neutral element
10    if (l <= lo && hi <= r) return tree[node];            // fully inside: use the stored value
11    int mid = lo + (hi - lo) / 2;
12    return query(2 * node, lo, mid, l, r) + query(2 * node + 1, mid + 1, hi, l, r);
13}
14void update(int node, int lo, int hi, int i, int v) {
15    if (lo == hi) { tree[node] = v; return; }
16    int mid = lo + (hi - lo) / 2;
17    if (i <= mid) update(2 * node, lo, mid, i, v); else update(2 * node + 1, mid + 1, hi, i, v);
18    tree[node] = tree[2 * node] + tree[2 * node + 1];     // recompute on the way back
19}
20int queryIterative(int l, int r) {                        // bottom-up, half-open [l, r)
21    int res = 0;
22    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
23        if ((l & 1) == 1) res += tree[l++];               // l is a right child: take it and move right
24        if ((r & 1) == 1) res += tree[--r];               // r is exclusive: its left neighbour is a right child
25    }
26    return res;
27}

Live state

0 nodes visited

No condition evaluated on this step

Execution trace (dry run table)Show 27 steps

Step	Line	State	What happens
1	L1	n=6	Build a sum tree over 6 values: each node stores the sum of its range; a leaf stores one element. ? marks nodes not built yet.
2	L2	node=8 range=[0, 0] value=2	Leaf [0]: tree[8] = a[0] = 2.
3	L2	node=9 range=[1, 1] value=5	Leaf [1]: tree[9] = a[1] = 5.
4	L6	node=4 range=[0, 1] value=7	Combine the children of [0, 1]: 2 + 5 = 7.
5	L2	node=5 range=[2, 2] value=1	Leaf [2]: tree[5] = a[2] = 1.
6	L6	node=2 range=[0, 2] value=8	Combine the children of [0, 2]: 7 + 1 = 8.
7	L2	node=12 range=[3, 3] value=4	Leaf [3]: tree[12] = a[3] = 4.
8	L2	node=13 range=[4, 4] value=9	Leaf [4]: tree[13] = a[4] = 9.
9	L6	node=6 range=[3, 4] value=13	Combine the children of [3, 4]: 4 + 9 = 13.
10	L2	node=7 range=[5, 5] value=3	Leaf [5]: tree[7] = a[5] = 3.
11	L6	node=3 range=[3, 5] value=16	Combine the children of [3, 5]: 13 + 3 = 16.
12	L6	node=1 range=[0, 5] value=24	Combine the children of [0, 5]: 8 + 16 = 24.
13	L8	l=1 r=4	Query sum(a[1..4]). Each node is outside (return 0, the neutral element), fully inside (use its stored value) or partly inside (ask both children and combine).
14	L11	node=1 range=[0, 5] kind=partial	[0, 5] overlaps [1, 4] only partly: recurse into both children.
15	L11	node=2 range=[0, 2] kind=partial	[0, 2] overlaps [1, 4] only partly: recurse into both children.
16	L11	node=4 range=[0, 1] kind=partial	[0, 1] overlaps [1, 4] only partly: recurse into both children.
17	L9	node=8 range=[0, 0] kind=disjoint	[0, 0] lies outside [1, 4]: return 0.
18	L10	node=9 range=[1, 1] kind=inside	[1, 1] lies inside [1, 4]: use the stored value 5; no need to look at its children.
19	L12	node=4 result=5	Combine the two answers below [0, 1]: 5.
20	L10	node=5 range=[2, 2] kind=inside	[2, 2] lies inside [1, 4]: use the stored value 1; no need to look at its children.
21	L12	node=2 result=6	Combine the two answers below [0, 2]: 6.
22	L11	node=3 range=[3, 5] kind=partial	[3, 5] overlaps [1, 4] only partly: recurse into both children.
23	L10	node=6 range=[3, 4] kind=inside	[3, 4] lies inside [1, 4]: use the stored value 13; no need to look at its children.
24	L9	node=7 range=[5, 5] kind=disjoint	[5, 5] lies outside [1, 4]: return 0.
25	L12	node=3 result=13	Combine the two answers below [3, 5]: 13.
26	L12	node=1 result=19	Combine the two answers below [0, 5]: 19.
27	L12	return=19 nodes visited=9	sum(a[1..4]) = 19, after visiting 9 nodes. At most four nodes per level are visited, so a query is O(log n).

29.03.3

Point update

To change a[i], go from the root to the leaf of i, choosing the left child when i <= mid and the right child otherwise, set the leaf, and recompute each node on the way back. Only the nodes whose ranges contain i can change, one per level, so an update is O(log n).

The preset "Point update" sets a[2] = 7 in 2 5 1 4 9 3: three nodes are recomputed, and the root changes from 24 to 30. Notice the order: the leaf is set first and the parents are recomputed from the bottom up, because a parent needs the new child values.

Java

1class SumTree {
2    private final int n;
3    private final long[] tree;
4    SumTree(int[] a) {
5        n = a.length;
6        tree = 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) { tree[node] = 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        tree[node] = tree[2 * node] + tree[2 * node + 1];
15    }
16    void update(int i, int v) { update(1, 0, n - 1, i, v); }
17    private void update(int node, int lo, int hi, int i, int v) {
18        if (lo == hi) { tree[node] = v; return; }
19        int mid = lo + (hi - lo) / 2;
20        if (i <= mid) update(2 * node, lo, mid, i, v); else update(2 * node + 1, mid + 1, hi, i, v);
21        tree[node] = tree[2 * node] + tree[2 * node + 1];             // recompute on the way back
22    }
23    long total() { return tree[1]; }
24}

Best

O(log n)

Average

O(log n)

Worst

O(log n)

Space

O(1) extra

Segment tree: build, range query, point update, iterative version

Interactive · edit the input

segment tree (each node shows its range under the value) · 11 nodes

[0, 5]

[0, 2]

[0, 1]

[0, 0]

[1, 1]

[2, 2]

[3, 5]

[3, 4]

[3, 3]

[4, 4]

[5, 5]

Partly inside: recurseFully inside: use itOutside: neutral elementJust built or recomputedCandidate

a[]

Setup

Build a sum tree over 6 values: each node stores the sum of its range; a leaf stores one element. ? marks nodes not built yet.

Step 1 / 27

Java

1void build(int node, int lo, int hi) {                   // recursive segment tree
2    if (lo == hi) { tree[node] = a[lo]; return; }        // leaf
3    int mid = lo + (hi - lo) / 2;
4    build(2 * node, lo, mid);
5    build(2 * node + 1, mid + 1, hi);
6    tree[node] = tree[2 * node] + tree[2 * node + 1];     // combine
7}
8int query(int node, int lo, int hi, int l, int r) {
9    if (r < lo || hi < l) return 0;                       // disjoint: the neutral element
10    if (l <= lo && hi <= r) return tree[node];            // fully inside: use the stored value
11    int mid = lo + (hi - lo) / 2;
12    return query(2 * node, lo, mid, l, r) + query(2 * node + 1, mid + 1, hi, l, r);
13}
14void update(int node, int lo, int hi, int i, int v) {
15    if (lo == hi) { tree[node] = v; return; }
16    int mid = lo + (hi - lo) / 2;
17    if (i <= mid) update(2 * node, lo, mid, i, v); else update(2 * node + 1, mid + 1, hi, i, v);
18    tree[node] = tree[2 * node] + tree[2 * node + 1];     // recompute on the way back
19}
20int queryIterative(int l, int r) {                        // bottom-up, half-open [l, r)
21    int res = 0;
22    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
23        if ((l & 1) == 1) res += tree[l++];               // l is a right child: take it and move right
24        if ((r & 1) == 1) res += tree[--r];               // r is exclusive: its left neighbour is a right child
25    }
26    return res;
27}

Live state

0 nodes visited

No condition evaluated on this step

Execution trace (dry run table)Show 27 steps

Step	Line	State	What happens
1	L1	n=6	Build a sum tree over 6 values: each node stores the sum of its range; a leaf stores one element. ? marks nodes not built yet.
2	L2	node=8 range=[0, 0] value=2	Leaf [0]: tree[8] = a[0] = 2.
3	L2	node=9 range=[1, 1] value=5	Leaf [1]: tree[9] = a[1] = 5.
4	L6	node=4 range=[0, 1] value=7	Combine the children of [0, 1]: 2 + 5 = 7.
5	L2	node=5 range=[2, 2] value=1	Leaf [2]: tree[5] = a[2] = 1.
6	L6	node=2 range=[0, 2] value=8	Combine the children of [0, 2]: 7 + 1 = 8.
7	L2	node=12 range=[3, 3] value=4	Leaf [3]: tree[12] = a[3] = 4.
8	L2	node=13 range=[4, 4] value=9	Leaf [4]: tree[13] = a[4] = 9.
9	L6	node=6 range=[3, 4] value=13	Combine the children of [3, 4]: 4 + 9 = 13.
10	L2	node=7 range=[5, 5] value=3	Leaf [5]: tree[7] = a[5] = 3.
11	L6	node=3 range=[3, 5] value=16	Combine the children of [3, 5]: 13 + 3 = 16.
12	L6	node=1 range=[0, 5] value=24	Combine the children of [0, 5]: 8 + 16 = 24.
13	L8	l=1 r=4	Query sum(a[1..4]). Each node is outside (return 0, the neutral element), fully inside (use its stored value) or partly inside (ask both children and combine).
14	L11	node=1 range=[0, 5] kind=partial	[0, 5] overlaps [1, 4] only partly: recurse into both children.
15	L11	node=2 range=[0, 2] kind=partial	[0, 2] overlaps [1, 4] only partly: recurse into both children.
16	L11	node=4 range=[0, 1] kind=partial	[0, 1] overlaps [1, 4] only partly: recurse into both children.
17	L9	node=8 range=[0, 0] kind=disjoint	[0, 0] lies outside [1, 4]: return 0.
18	L10	node=9 range=[1, 1] kind=inside	[1, 1] lies inside [1, 4]: use the stored value 5; no need to look at its children.
19	L12	node=4 result=5	Combine the two answers below [0, 1]: 5.
20	L10	node=5 range=[2, 2] kind=inside	[2, 2] lies inside [1, 4]: use the stored value 1; no need to look at its children.
21	L12	node=2 result=6	Combine the two answers below [0, 2]: 6.
22	L11	node=3 range=[3, 5] kind=partial	[3, 5] overlaps [1, 4] only partly: recurse into both children.
23	L10	node=6 range=[3, 4] kind=inside	[3, 4] lies inside [1, 4]: use the stored value 13; no need to look at its children.
24	L9	node=7 range=[5, 5] kind=disjoint	[5, 5] lies outside [1, 4]: return 0.
25	L12	node=3 result=13	Combine the two answers below [3, 5]: 13.
26	L12	node=1 result=19	Combine the two answers below [0, 5]: 19.
27	L12	return=19 nodes visited=9	sum(a[1..4]) = 19, after visiting 9 nodes. At most four nodes per level are visited, so a query is O(log n).

29.03.4

Range sum/min/max

A query [l, r] visits the tree recursively. A node whose range is disjoint from [l, r] returns the neutral element; a node fully inside returns its stored value without looking at its children; a node that overlaps partly asks both children and combines the answers. At most two nodes per level are partial, so a query visits O(log n) nodes (at most about four per level, counting the ones that return at once).

One class serves sum, minimum and maximum if the operation and its neutral element are parameters. Compare the presets "Range sum", "Range minimum" and "Range maximum" in the animation: the sum query over positions 1..4 of 2 5 1 4 9 3 is 19 after 9 node visits, the minimum is 1, and the maximum over positions 0..3 is 5 after 7 visits. Fully inside nodes are drawn in the 'use it' colour, disjoint ones in the 'neutral' colour.

Java

1class SegTree {
2    private final int n;
3    private final long[] tree;
4    private final LongBinaryOperator op;
5    private final long identity;                 // op(identity, x) == x for every x
6    SegTree(int[] a, LongBinaryOperator op, long identity) {
7        this.n = a.length; this.op = op; this.identity = identity;
8        tree = new long[4 * n];
9        build(a, 1, 0, n - 1);
10    }
11    private void build(int[] a, int node, int lo, int hi) {
12        if (lo == hi) { tree[node] = a[lo]; return; }
13        int mid = lo + (hi - lo) / 2;
14        build(a, 2 * node, lo, mid);
15        build(a, 2 * node + 1, mid + 1, hi);
16        tree[node] = op.applyAsLong(tree[2 * node], tree[2 * node + 1]);
17    }
18    long query(int l, int r) { return query(1, 0, n - 1, l, r); }
19    private long query(int node, int lo, int hi, int l, int r) {
20        if (r < lo || hi < l) return identity;             // disjoint: the neutral element
21        if (l <= lo && hi <= r) return tree[node];         // fully inside: use the stored value
22        int mid = lo + (hi - lo) / 2;
23        return op.applyAsLong(query(2 * node, lo, mid, l, r), query(2 * node + 1, mid + 1, hi, l, r));
24    }
25}

Best

O(log n)

Average

O(log n)

Worst

O(log n)

Space

O(n)

Segment tree: build, range query, point update, iterative version

Interactive · edit the input

segment tree (each node shows its range under the value) · 11 nodes

[0, 5]

[0, 2]

[0, 1]

[0, 0]

[1, 1]

[2, 2]

[3, 5]

[3, 4]

[3, 3]

[4, 4]

[5, 5]

Partly inside: recurseFully inside: use itOutside: neutral elementJust built or recomputedCandidate

a[]

Setup

Build a sum tree over 6 values: each node stores the sum of its range; a leaf stores one element. ? marks nodes not built yet.

Step 1 / 27

Java

1void build(int node, int lo, int hi) {                   // recursive segment tree
2    if (lo == hi) { tree[node] = a[lo]; return; }        // leaf
3    int mid = lo + (hi - lo) / 2;
4    build(2 * node, lo, mid);
5    build(2 * node + 1, mid + 1, hi);
6    tree[node] = tree[2 * node] + tree[2 * node + 1];     // combine
7}
8int query(int node, int lo, int hi, int l, int r) {
9    if (r < lo || hi < l) return 0;                       // disjoint: the neutral element
10    if (l <= lo && hi <= r) return tree[node];            // fully inside: use the stored value
11    int mid = lo + (hi - lo) / 2;
12    return query(2 * node, lo, mid, l, r) + query(2 * node + 1, mid + 1, hi, l, r);
13}
14void update(int node, int lo, int hi, int i, int v) {
15    if (lo == hi) { tree[node] = v; return; }
16    int mid = lo + (hi - lo) / 2;
17    if (i <= mid) update(2 * node, lo, mid, i, v); else update(2 * node + 1, mid + 1, hi, i, v);
18    tree[node] = tree[2 * node] + tree[2 * node + 1];     // recompute on the way back
19}
20int queryIterative(int l, int r) {                        // bottom-up, half-open [l, r)
21    int res = 0;
22    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
23        if ((l & 1) == 1) res += tree[l++];               // l is a right child: take it and move right
24        if ((r & 1) == 1) res += tree[--r];               // r is exclusive: its left neighbour is a right child
25    }
26    return res;
27}

Live state

0 nodes visited

No condition evaluated on this step

Execution trace (dry run table)Show 27 steps

Step	Line	State	What happens
1	L1	n=6	Build a sum tree over 6 values: each node stores the sum of its range; a leaf stores one element. ? marks nodes not built yet.
2	L2	node=8 range=[0, 0] value=2	Leaf [0]: tree[8] = a[0] = 2.
3	L2	node=9 range=[1, 1] value=5	Leaf [1]: tree[9] = a[1] = 5.
4	L6	node=4 range=[0, 1] value=7	Combine the children of [0, 1]: 2 + 5 = 7.
5	L2	node=5 range=[2, 2] value=1	Leaf [2]: tree[5] = a[2] = 1.
6	L6	node=2 range=[0, 2] value=8	Combine the children of [0, 2]: 7 + 1 = 8.
7	L2	node=12 range=[3, 3] value=4	Leaf [3]: tree[12] = a[3] = 4.
8	L2	node=13 range=[4, 4] value=9	Leaf [4]: tree[13] = a[4] = 9.
9	L6	node=6 range=[3, 4] value=13	Combine the children of [3, 4]: 4 + 9 = 13.
10	L2	node=7 range=[5, 5] value=3	Leaf [5]: tree[7] = a[5] = 3.
11	L6	node=3 range=[3, 5] value=16	Combine the children of [3, 5]: 13 + 3 = 16.
12	L6	node=1 range=[0, 5] value=24	Combine the children of [0, 5]: 8 + 16 = 24.
13	L8	l=1 r=4	Query sum(a[1..4]). Each node is outside (return 0, the neutral element), fully inside (use its stored value) or partly inside (ask both children and combine).
14	L11	node=1 range=[0, 5] kind=partial	[0, 5] overlaps [1, 4] only partly: recurse into both children.
15	L11	node=2 range=[0, 2] kind=partial	[0, 2] overlaps [1, 4] only partly: recurse into both children.
16	L11	node=4 range=[0, 1] kind=partial	[0, 1] overlaps [1, 4] only partly: recurse into both children.
17	L9	node=8 range=[0, 0] kind=disjoint	[0, 0] lies outside [1, 4]: return 0.
18	L10	node=9 range=[1, 1] kind=inside	[1, 1] lies inside [1, 4]: use the stored value 5; no need to look at its children.
19	L12	node=4 result=5	Combine the two answers below [0, 1]: 5.
20	L10	node=5 range=[2, 2] kind=inside	[2, 2] lies inside [1, 4]: use the stored value 1; no need to look at its children.
21	L12	node=2 result=6	Combine the two answers below [0, 2]: 6.
22	L11	node=3 range=[3, 5] kind=partial	[3, 5] overlaps [1, 4] only partly: recurse into both children.
23	L10	node=6 range=[3, 4] kind=inside	[3, 4] lies inside [1, 4]: use the stored value 13; no need to look at its children.
24	L9	node=7 range=[5, 5] kind=disjoint	[5, 5] lies outside [1, 4]: return 0.
25	L12	node=3 result=13	Combine the two answers below [3, 5]: 13.
26	L12	node=1 result=19	Combine the two answers below [0, 5]: 19.
27	L12	return=19 nodes visited=9	sum(a[1..4]) = 19, after visiting 9 nodes. At most four nodes per level are visited, so a query is O(log n).

29.03.5

Neutral element

The **neutral element** (identity) of an operation is the value e with op(e, x) = x for every x. A disjoint node returns it so that it does not disturb the answer. Using the wrong one is a classic bug: returning 0 for a minimum query silently makes every answer 0 or less.

The identity must be correct for the type's range, too: Integer.MAX_VALUE is the identity of min over int, and Long.MAX_VALUE over long. Do not use Integer.MAX_VALUE with long values that can exceed it. The table lists the usual operations; the code puts the identity next to the operation so that the pair cannot get out of step.

Operation	Neutral element	Because
sum	0	x + 0 = x
product	1	x × 1 = x
minimum	largest value of the type	min(MAX, x) = x
maximum	smallest value of the type	max(MIN, x) = x
XOR	0	x ^ 0 = x
GCD	0	gcd(0, x) = x

Java

1enum Op {
2    SUM(0), PRODUCT(1), MIN(Long.MAX_VALUE), MAX(Long.MIN_VALUE), XOR(0), GCD(0);
3    final long identity;
4    Op(long identity) { this.identity = identity; }
5    long apply(long x, long y) {
6        switch (this) {
7            case SUM: return x + y;
8            case PRODUCT: return x * y;
9            case MIN: return Math.min(x, y);
10            case MAX: return Math.max(x, y);
11            case XOR: return x ^ y;
12            default: return gcd(x, y);
13        }
14    }
15    private static long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); }
16}

Segment tree: build, range query, point update, iterative version

Interactive · edit the input

segment tree (each node shows its range under the value) · 11 nodes

[0, 5]

[0, 2]

[0, 1]

[0, 0]

[1, 1]

[2, 2]

[3, 5]

[3, 4]

[3, 3]

[4, 4]

[5, 5]

Partly inside: recurseFully inside: use itOutside: neutral elementJust built or recomputedCandidate

a[]

Setup

Build a sum tree over 6 values: each node stores the sum of its range; a leaf stores one element. ? marks nodes not built yet.

Step 1 / 27

Java

1void build(int node, int lo, int hi) {                   // recursive segment tree
2    if (lo == hi) { tree[node] = a[lo]; return; }        // leaf
3    int mid = lo + (hi - lo) / 2;
4    build(2 * node, lo, mid);
5    build(2 * node + 1, mid + 1, hi);
6    tree[node] = tree[2 * node] + tree[2 * node + 1];     // combine
7}
8int query(int node, int lo, int hi, int l, int r) {
9    if (r < lo || hi < l) return 0;                       // disjoint: the neutral element
10    if (l <= lo && hi <= r) return tree[node];            // fully inside: use the stored value
11    int mid = lo + (hi - lo) / 2;
12    return query(2 * node, lo, mid, l, r) + query(2 * node + 1, mid + 1, hi, l, r);
13}
14void update(int node, int lo, int hi, int i, int v) {
15    if (lo == hi) { tree[node] = v; return; }
16    int mid = lo + (hi - lo) / 2;
17    if (i <= mid) update(2 * node, lo, mid, i, v); else update(2 * node + 1, mid + 1, hi, i, v);
18    tree[node] = tree[2 * node] + tree[2 * node + 1];     // recompute on the way back
19}
20int queryIterative(int l, int r) {                        // bottom-up, half-open [l, r)
21    int res = 0;
22    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
23        if ((l & 1) == 1) res += tree[l++];               // l is a right child: take it and move right
24        if ((r & 1) == 1) res += tree[--r];               // r is exclusive: its left neighbour is a right child
25    }
26    return res;
27}

Live state

0 nodes visited

No condition evaluated on this step

Execution trace (dry run table)Show 27 steps

Step	Line	State	What happens
1	L1	n=6	Build a sum tree over 6 values: each node stores the sum of its range; a leaf stores one element. ? marks nodes not built yet.
2	L2	node=8 range=[0, 0] value=2	Leaf [0]: tree[8] = a[0] = 2.
3	L2	node=9 range=[1, 1] value=5	Leaf [1]: tree[9] = a[1] = 5.
4	L6	node=4 range=[0, 1] value=7	Combine the children of [0, 1]: 2 + 5 = 7.
5	L2	node=5 range=[2, 2] value=1	Leaf [2]: tree[5] = a[2] = 1.
6	L6	node=2 range=[0, 2] value=8	Combine the children of [0, 2]: 7 + 1 = 8.
7	L2	node=12 range=[3, 3] value=4	Leaf [3]: tree[12] = a[3] = 4.
8	L2	node=13 range=[4, 4] value=9	Leaf [4]: tree[13] = a[4] = 9.
9	L6	node=6 range=[3, 4] value=13	Combine the children of [3, 4]: 4 + 9 = 13.
10	L2	node=7 range=[5, 5] value=3	Leaf [5]: tree[7] = a[5] = 3.
11	L6	node=3 range=[3, 5] value=16	Combine the children of [3, 5]: 13 + 3 = 16.
12	L6	node=1 range=[0, 5] value=24	Combine the children of [0, 5]: 8 + 16 = 24.
13	L8	l=1 r=4	Query sum(a[1..4]). Each node is outside (return 0, the neutral element), fully inside (use its stored value) or partly inside (ask both children and combine).
14	L11	node=1 range=[0, 5] kind=partial	[0, 5] overlaps [1, 4] only partly: recurse into both children.
15	L11	node=2 range=[0, 2] kind=partial	[0, 2] overlaps [1, 4] only partly: recurse into both children.
16	L11	node=4 range=[0, 1] kind=partial	[0, 1] overlaps [1, 4] only partly: recurse into both children.
17	L9	node=8 range=[0, 0] kind=disjoint	[0, 0] lies outside [1, 4]: return 0.
18	L10	node=9 range=[1, 1] kind=inside	[1, 1] lies inside [1, 4]: use the stored value 5; no need to look at its children.
19	L12	node=4 result=5	Combine the two answers below [0, 1]: 5.
20	L10	node=5 range=[2, 2] kind=inside	[2, 2] lies inside [1, 4]: use the stored value 1; no need to look at its children.
21	L12	node=2 result=6	Combine the two answers below [0, 2]: 6.
22	L11	node=3 range=[3, 5] kind=partial	[3, 5] overlaps [1, 4] only partly: recurse into both children.
23	L10	node=6 range=[3, 4] kind=inside	[3, 4] lies inside [1, 4]: use the stored value 13; no need to look at its children.
24	L9	node=7 range=[5, 5] kind=disjoint	[5, 5] lies outside [1, 4]: return 0.
25	L12	node=3 result=13	Combine the two answers below [3, 5]: 13.
26	L12	node=1 result=19	Combine the two answers below [0, 5]: 19.
27	L12	return=19 nodes visited=9	sum(a[1..4]) = 19, after visiting 9 nodes. At most four nodes per level are visited, so a query is O(log n).

29.03.6

Query combination

When the operation is commutative (sum, min, max), the order in which partial answers are combined does not matter. When it is not, such as composing functions, concatenating strings or multiplying matrices, the left part of the range must be combined before the right part. The recursive query already does this: it combines the answer of the left child with the answer of the right child, in that order.

The example stores affine functions x -> a × x + b. Applying f and then g gives g(f(x)) = g.a × (f.a × x + f.b) + g.b, which is not the same as f after g. The tree answers 'the combined function of positions l..r applied in order' in O(log n). Iterative bottom-up trees need two accumulators for this reason (see the iterative lesson).

Java

1record Affine(long a, long b) {                  // the function x -> a * x + b
2    static final Affine IDENTITY = new Affine(1, 0);
3    Affine then(Affine g) { return new Affine(g.a * a, g.a * b + g.b); }   // apply this first, then g
4    long at(long x) { return a * x + b; }
5}
6class AffineTree {
7    private final int n;
8    private final Affine[] tree;
9    AffineTree(Affine[] f) {
10        n = f.length;
11        tree = new Affine[4 * n];
12        build(f, 1, 0, n - 1);
13    }
14    private void build(Affine[] f, int node, int lo, int hi) {
15        if (lo == hi) { tree[node] = f[lo]; return; }
16        int mid = lo + (hi - lo) / 2;
17        build(f, 2 * node, lo, mid);
18        build(f, 2 * node + 1, mid + 1, hi);
19        tree[node] = tree[2 * node].then(tree[2 * node + 1]);          // left first, then right
20    }
21    Affine query(int l, int r) { return query(1, 0, n - 1, l, r); }
22    private Affine query(int node, int lo, int hi, int l, int r) {
23        if (r < lo || hi < l) return Affine.IDENTITY;
24        if (l <= lo && hi <= r) return tree[node];
25        int mid = lo + (hi - lo) / 2;
26        return query(2 * node, lo, mid, l, r).then(query(2 * node + 1, mid + 1, hi, l, r));
27    }
28}

Practice ladder

Now try it yourself

Easy

Range Sum Query - Mutable

Medium

My Calendar I
Range Module
Count Integers in Intervals

Advanced

Falling Squares
My Calendar III
The Skyline Problem

Key takeaways

A segment tree splits [lo, hi] at mid; it has 2n - 1 nodes, and queries and updates visit O(log n) of them.
A query returns the neutral element for a disjoint node and the stored value for a node fully inside; only partial nodes recurse.
Combine the left answer before the right one so that non-commutative operations stay correct.