Build & Query
Build recursively: leaves store array values, parents store the merge of their children. To query range [L,R]: if the current node's range is fully inside [L,R], return its value. Otherwise, recurse into children and merge results.
How It Works
A segment tree assigns each node an array range: leaves cover single elements, and each internal node covers the union of its two children's ranges, storing their aggregate (sum, min, max, gcd — any associative operation). Building proceeds bottom-up recursively: fill leaves with array values, then set each parent to the merge of its children, touching every node once for O(n) build over roughly 2n-4n nodes.
A query for [L, R] descends from the root with three cases: a node's range fully inside [L, R] contributes its stored value immediately; a range fully outside contributes the identity; a partial overlap recurses into both children and merges. Only O(log n) nodes fully cover disjoint pieces of any query, so queries run in O(log n). A point update rewrites one leaf and recomputes the O(log n) ancestors — the balance of fast queries and fast updates that prefix sums cannot offer.
Step-by-Step Visualization
Code
class SegTree {
int n;
int[] tree;
SegTree(int[] arr) {
n = arr.length;
tree = new int[4 * n];
build(arr, 1, 0, n - 1);
}
void build(int[] arr, int node, int start, int end) {
if (start == end) { tree[node] = arr[start]; return; }
int mid = (start + end) / 2;
build(arr, 2*node, start, mid);
build(arr, 2*node+1, mid+1, end);
tree[node] = tree[2*node] + tree[2*node+1];
}
int query(int node, int start, int end, int l, int r) {
if (r < start || end < l) return 0;
if (l <= start && end <= r) return tree[node];
int mid = (start + end) / 2;
return query(2*node, start, mid, l, r) +
query(2*node+1, mid+1, end, l, r);
}
}Tips & Gotchas
Practice Problems
- 1Range Sum Query - Mutable
- 2Range Minimum Query
- 3Count of Smaller Numbers After Self
- 4My Calendar I
About the Segment Tree Pattern
A binary tree where each node represents a range of the array. Leaves are individual elements. Internal nodes store the aggregate (sum, min, max) of their children's ranges. Supports both queries and updates in O(log n).
If you only need prefix queries with point updates, use a BIT (simpler). If you need arbitrary range queries + range updates, use a segment tree with lazy propagation. Sparse table is O(1) query but static.
Common Range Structures Interview Problems
- Range Sum Query - Mutable
- Count of Smaller Numbers After Self
- Range Minimum Query
- Longest Increasing Subsequence (BIT approach)
Frequently Asked Questions
Why choose a segment tree over a prefix sum array?
Prefix sums answer range-sum queries in O(1) but a single element change forces an O(n) rebuild of every prefix after it. A segment tree makes both operations O(log n), so it wins whenever queries and updates interleave; for a fully static array, prefix sums remain simpler and faster.
Why do range queries only touch O(log n) contributing nodes?
Descending from the root, the query range can partially straddle at most two node boundaries per level — the left and right fringes — while everything between is fully covered and returns immediately. With O(log n) levels and constant work per level on each fringe, the total is O(log n).
What operations can a segment tree aggregate?
Any associative operation with an identity element: sum, min, max, gcd, bitwise AND/OR/XOR, or even matrix products and custom structs (like the best subarray sum). Associativity is what allows partial results from disjoint child ranges to merge correctly; commutativity is not required as long as left and right results merge in order.