A status page stores 5xx counts per minute in a long array. Ops asks “how many errors from minute 240 to 400?” You scan the slice. A collector then delivers a late correction for minute 312. You scan again. Prefix sums make the query free — and turn every correction into a rewrite of every prefix after that index.
A segment tree stores an aggregate of every interval node so a range is a handful of nodes and a point update touches a handful of ancestors. Query and update are both O(log n). The series glossary (ADT vs implementation, Big-O, how to read a complexity table) lives on the Data Structures Roadmap. This post is the layout: interval nodes, build, range sum query, and point update. There is no JDK SegmentTree.
Each node owns an interval
The leaves are the array. Internal nodes are contiguous ranges. A node that covers [lo, hi) stores the aggregate of a[lo] … a[hi-1]. Its left child covers [lo, mid); its right child covers [mid, hi). Half-open intervals keep the split honest: every index sits in exactly one child.
Range sum is the running example. Combine is +. The identity (empty range) is 0. The same shape works for min, max, or gcd — only the combine and the identity change.
Array a = [2, 1, 3, 4]
[0,4) 10
/ \
[0,2) 3 [2,4) 7
/ \ / \
[0,1) 2 [1,2) 1 [2,3) 3 [3,4) 4Four leaves, three internal nodes, seven values. The root is the sum of the whole array. You never store the original a separately unless you want a convenient copy — the leaves are the array.
Note: A heap is also a complete tree in an array, but it answers “what is next?” A segment tree answers “what is the aggregate of this slice?” Same 2-child picture, different invariant.
Build from the leaves up
Fill every leaf from a, then set each parent to left + right. Every node is written once, so build is O(n). The usual packing is a 1-based heap-style array: root at index 1, left child 2 * node, right child 2 * node + 1. Length 4 * n is the safe bound when n is not a power of two — the extra slots stay unused.
public class SegmentTree {
private final int n;
private final int[] tree; // 1-based; tree[1] covers [0, n)
public SegmentTree(int[] a) {
n = a.length;
tree = new int[4 * n];
build(a, 1, 0, n);
}
private void build(int[] a, int node, int lo, int hi) {
if (hi - lo == 1) {
tree[node] = a[lo];
return;
}
int mid = (lo + hi) >>> 1;
build(a, node * 2, lo, mid);
build(a, node * 2 + 1, mid, hi);
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
}>>> 1 is unsigned divide-by-two so lo + hi cannot overflow into a negative mid. The public constructor is the only build you call.
For [2, 1, 3, 4], a typical packing (unused slots omitted) looks like this:
index 1 2 3 4 5 6 7
cover [0,4) [0,2) [2,4) [0,1) [1,2) [2,3) [3,4)
value 10 3 7 2 1 3 4Root at 1, not 0. That is the opposite of a 0-based binary heap. Pick one convention per structure and stay there.
Query: take nodes that sit inside the range
A query asks for the sum of a[qLo … qHi). Walk from the root. Three cases per node:
- Disjoint from
[qLo, qHi)— return0. - Fully inside
[qLo, qHi)— returntree[node]and stop. - Partial overlap — recurse both children and add.
public int query(int qLo, int qHi) { // [qLo, qHi)
return query(1, 0, n, qLo, qHi);
}
private int query(int node, int lo, int hi, int qLo, int qHi) {
if (qHi <= lo || hi <= qLo) {
return 0;
}
if (qLo <= lo && hi <= qHi) {
return tree[node];
}
int mid = (lo + hi) >>> 1;
return query(node * 2, lo, mid, qLo, qHi)
+ query(node * 2 + 1, mid, hi, qLo, qHi);
}Query [1, 4) on the tree above — sum of 1 + 3 + 4:
[0,4) partial
[0,2) partial
[0,1) disjoint → 0
[1,2) fully inside → 1
[2,4) fully inside → 7
result 1 + 7 = 8You did not walk index 2 and 3 separately. The right child already held that sum. At most two nodes per level contribute, so the walk is O(log n) — not O(qHi - qLo).
A fully covered node is the whole point of the structure. If you always recurse to the leaves, you built a tree and then paid a linear scan anyway.
Point update: rewrite the leaf, then the ancestors
Set a[i] = value. Only the leaf that owns i changes, plus every parent on the path to the root. That path is the height of the tree: O(log n) writes.
public void update(int i, int value) {
update(1, 0, n, i, value);
}
private void update(int node, int lo, int hi, int i, int value) {
if (hi - lo == 1) {
tree[node] = value;
return;
}
int mid = (lo + hi) >>> 1;
if (i < mid) {
update(node * 2, lo, mid, i, value);
} else {
update(node * 2 + 1, mid, hi, i, value);
}
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}Update index 2 from 3 to 5:
leaf [2,3) : 3 → 5
[2,4) : 3+4 → 5+4 = 9
[0,4) : 3+7 → 3+9 = 12[0,2) does not move. The next query of [1, 4) returns 1 + 9 = 10 without rescanning.
| Operation | Cost |
|---|---|
| Build | O(n) |
Range query [L, R) | O(log n) |
| Point update | O(log n) |
| Space | O(n) — typically 4n slots |
Note: Adding 5 to every index in a range is a different job (range update). The honest version walks O(n) leaves. Lazy tags exist so you can postpone that work; they are out of scope here. This post is point update plus range query.
When not to use a segment tree
Skip the tree when the hot path does not need both range aggregates and updates:
- The array is static and you will query more than once. Prefix sums:
pre[0] = 0,pre[i+1] = pre[i] + a[i], thensum(L, R) = pre[R] - pre[L]. BuildO(n), queryO(1), no tree. - One query, then you throw the array away. Scan the slice.
O(range)with no extra memory and nothing to debug. - You only ever ask for prefixes (
sum(0, R)) with point updates. A Fenwick tree (binary indexed tree) is the slimmer layout for that contract. Do not reach for a segment tree because the name showed up in a roundup — Fenwick is the cheaper cousin when the range always starts at index0. nis tiny. Summing 40 buckets in a loop is clearer than explaining4nslots. Measure when the array grows and the queries stay mixed with writes.
There is no java.util type for this. You write the array (or you pull a library). That cost is worth it only when range query and point update share the hot path.
Cheat sheet
Segment tree: binary tree of intervals; leaf = a[i], parent = combine(left, right)
Interval: node covers [lo, hi); left [lo, mid); right [mid, hi)
Combine: + for range sum (identity 0); min/max/gcd use a different identity
Packing: 1-based heap array; root 1; left 2*node; right 2*node+1; size 4n
Build: leaves up O(n)
Query [L, R): take fully covered nodes O(log n)
Point update: leaf, then ancestors O(log n)
Not a heap: aggregate of a slice, not next-best
Avoid: static array (prefix sums); one scan; prefix-only updates (Fenwick)
No JDK typeDo:
- Name the hot pair: range aggregate plus point writes. That is this layout.
- Keep intervals half-open so every index lands in one child.
- Stop at fully covered nodes. That is the
O(log n)query.
Don’t:
- Rescan
a[L..R]on every dashboard refresh after you already built a tree. - Build prefix sums and then pretend a point update is still
O(1). - Reach for a segment tree when the range always starts at
0— that job is a Fenwick tree.
Wrap-up
A segment tree is a binary tree of intervals over an array. Each node stores an aggregate of its slice. Build fills leaves from the array and parents from children in O(n). A range query combines O(log n) fully covered nodes. A point update rewrites one leaf and its ancestors, also O(log n).
Range sum is the example; min, max, and gcd are the same walk with a different combine. If the array never changes, prefix sums are enough. If you only need prefixes with updates, Fenwick is the slimmer tree. If you need an arbitrary slice and a later correction at one index, this is the layout that makes both cheap.
The series hub is the glossary and index when the next job is a different layout.