Segment Tree Visualization for Coding Interviews
Range sum + point update in O(log n); recursive build.
Concept
A segment tree is a static-sized binary tree that answers range queries and point or range updates over an array in O(log n) per operation. The idea is to store, at every internal node, an aggregate over a contiguous segment of the underlying array - typically a sum, min, max, gcd, or any associative operation - so that any arbitrary range [l, r] can be covered by at most O(log n) stored segments. Segment trees are the go-to structure whenever Fenwick trees are not expressive enough (because you need min/max instead of just sum, or you need range assignment with lazy propagation, or you need to store structured data per node). The classic implementation lives in a 4n-sized array, where the children of node i are at 2i and 2i+1. Competitive programmers love them because the same skeleton solves a dozen different problems with a change of merge function and (optionally) a lazy-propagation rule; systems engineers run into them inside time-series databases, OLAP cubes, and anywhere prefix-sum generalizations are needed.
How it works
Build recurses over the array: at a leaf node representing a single array index, it stores the value; at an internal node representing [l, r], it recurses into [l, mid] and [mid+1, r] and combines the two child aggregates with the merge function. Query for [ql, qr] starts at the root and, at each node covering [l, r], handles three cases: if [l, r] is entirely outside [ql, qr] it returns the identity element (0 for sum, +infinity for min); if [l, r] is entirely inside [ql, qr] it returns the stored aggregate; otherwise it recurses into both children and combines the partial results. That three-way split guarantees O(log n) nodes are visited because at each level at most four nodes can be partially covered. Point update walks from the root down to the leaf representing the updated index, overwriting it, then rebuilds each ancestor's aggregate on the way back up. Range update and range query together need a lazy-propagation extension: every node carries a pending update that has been applied to its own aggregate but not yet pushed to its children; you push the pending value down whenever you descend past a node that has one. The 4n size bound accommodates the worst case where the underlying array length is one more than a power of two.
Implementation
public class SegmentTree {
private final int n;
private final long[] tree;
public SegmentTree(int[] input) {
this.n = input.length;
this.tree = new long[4 * Math.max(n, 1)];
if (n > 0) build(1, 0, n - 1, input);
}
private void build(int node, int l, int r, int[] input) {
if (l == r) {
tree[node] = input[l];
return;
}
int mid = (l + r) >>> 1;
build(2 * node, l, mid, input);
build(2 * node + 1, mid + 1, r, input);
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
/** Set input[i] = value (point update). */
public void update(int i, int value) {
if (i < 0 || i >= n) throw new IndexOutOfBoundsException();
update(1, 0, n - 1, i, value);
}
private void update(int node, int l, int r, int i, int value) {
if (l == r) {
tree[node] = value;
return;
}
int mid = (l + r) >>> 1;
if (i <= mid) update(2 * node, l, mid, i, value);
else update(2 * node + 1, mid + 1, r, i, value);
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
/** Sum of input[ql..qr] inclusive. */
public long queryRangeSum(int ql, int qr) {
if (ql < 0 || qr >= n || ql > qr) throw new IndexOutOfBoundsException();
return query(1, 0, n - 1, ql, qr);
}
private long query(int node, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return 0L; // disjoint
if (ql <= l && r <= qr) return tree[node]; // fully covered
int mid = (l + r) >>> 1;
return query(2 * node, l, mid, ql, qr)
+ query(2 * node + 1, mid + 1, r, ql, qr);
}
}Complexity
- Build:
O(n) - Query:
O(log n) - Update:
O(log n) - Space:
O(n)
Common pitfalls
- Sizing the tree array at 2n instead of 4n - works when n is a power of two, fails silently otherwise.
- Forgetting to recompute the parent aggregate after a point update, leaving a stale value along the path.
- Using the wrong identity element (e.g. 0 for a min query) and returning garbage for out-of-range segments.
- Implementing lazy propagation without pushing pending updates before descending into children.
- Using int for a sum aggregate that can overflow - promote to long when the values are dense or the range is wide.
Key design decisions & trade-offs
- Segment tree vs Fenwick tree — Chosen: Segment tree for non-invertible operations. Fenwick is faster and smaller for prefix sums, but cannot express range-min or range-gcd without losing O(log n) updates.
- Recursive vs iterative — Chosen: Recursive for clarity. Recursive is a near-direct translation of the structure; iterative bottom-up is faster in contests but harder to extend with lazy propagation.
- Eager vs lazy updates — Chosen: Lazy propagation for range assignment. Eager range update is O(n log n); lazy defers the work and only touches O(log n) nodes per operation.
Practice problems
Interview follow-ups
- Extend the segment tree with lazy propagation to support range-add and range-sum together.
- Build a segment tree indexed by coordinates for 2D range queries.
- Support persistent versions of the segment tree for historical queries.
- Compare iterative bottom-up segment tree against the recursive variant on a stress test.
- Implement a merge-sort tree for range-k-th-smallest queries.
Why it matters
Segment Tree is a core part of the Trees toolkit. If you are preparing for a technical interview at a top-tier company or teaching a course, a working visualization is the fastest path from "I read about it" to "I understand it".