What you'll learn
Quick Answer
A segment tree is a binary tree where each node stores a combined value — a sum, minimum, or maximum — for a range of the underlying array, so both range queries and single-element updates run in O(log n). It trades the O(1) query speed of a plain prefix sum array for O(log n) query time, in exchange for O(log n) updates instead of O(n) ones — the trade that matters the moment your data changes after you've started asking range questions about it.
The Problem: Prefix Sums Can't Handle Updates
A prefix sum array answers any range sum in O(1) after an O(n) build — great, as long as the underlying array never changes. The moment a single element changes, the prefix array from that position onward is stale, and fixing it means recomputing an O(n) suffix of it.
That's fine if updates are rare. It falls apart the moment updates and range queries are both frequent — a leaderboard where scores change constantly and you repeatedly need "total score across ranks 100 to 200," or live inventory counts across a range of warehouse shelves that both change and get summed constantly. Paying O(n) per update erases the whole benefit of precomputing anything.
A segment tree is built for exactly this mixed workload: O(log n) for a range query and O(log n) for a point update, so neither operation dominates the other no matter how often either happens.
How a Segment Tree Is Shaped
Each leaf of the tree corresponds to one element of the original array. Each internal node corresponds to a contiguous range and stores the combined value of that range — the sum of it, for the classic case, though it works equally for min, max, or gcd as long as the operation is associative. The root covers the entire array; every node splits its range in half between its two children, all the way down to single-element leaves.
The usual implementation stores the whole tree as one flat array using heap-style indexing: node i's children live at 2*i and 2*i + 1. That layout doesn't guarantee tight packing when the array length isn't a power of two, so the backing array is conventionally sized at 4 * n to stay safe for any input length rather than trying to compute the exact minimum. Both building the tree and answering a query touch at most O(log n) levels of recursion, since each level halves the range being considered — that logarithmic depth is where all the speed comes from.
Building the Tree and Querying a Range
class SegmentTree {
constructor(arr) {
this.n = arr.length;
this.tree = new Array(4 * this.n).fill(0);
this.build(arr, 1, 0, this.n - 1);
}
build(arr, node, start, end) {
if (start === end) {
this.tree[node] = arr[start];
return;
}
const mid = Math.floor((start + end) / 2);
this.build(arr, 2 * node, start, mid);
this.build(arr, 2 * node + 1, mid + 1, end);
this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
}
query(l, r) {
return this._query(1, 0, this.n - 1, l, r);
}
_query(node, start, end, l, r) {
if (r < start || end < l) return 0; // no overlap
if (l <= start && end <= r) return this.tree[node]; // total overlap
const mid = Math.floor((start + end) / 2);
return this._query(2 * node, start, mid, l, r) +
this._query(2 * node + 1, mid + 1, end, l, r); // partial overlap
}
}
const st = new SegmentTree([2, 4, 5, 7, 8, 9]);
st.query(1, 3); // 16 (4 + 5 + 7)
st.query(0, 5); // 35 (whole array)_query only ever hits one of three cases at each node: the node's range doesn't overlap the query at all (return 0 and stop), the node's range sits entirely inside the query (return its precomputed value directly, no need to look further down), or the ranges partially overlap (split and recurse into both children). It's that middle case — being able to return a whole subtree's answer in one lookup instead of walking every leaf — that makes the query logarithmic instead of linear.
Updating a Value
update(idx, value) {
this._update(1, 0, this.n - 1, idx, value);
}
_update(node, start, end, idx, value) {
if (start === end) {
this.tree[node] = value;
return;
}
const mid = Math.floor((start + end) / 2);
if (idx <= mid) this._update(2 * node, start, mid, idx, value);
else this._update(2 * node + 1, mid + 1, end, idx, value);
this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
}
st.update(1, 10); // arr[1] becomes 10
st.query(1, 3); // 22 now (10 + 5 + 7)
st.query(0, 5); // 41 now (whole array)An update walks straight down to the single leaf that changed — an O(log n) path, since each level halves the range — then recomputes every ancestor's stored value on the way back up out of the recursion. Only the nodes directly on that path are touched, which is why a single update never costs more than O(log n), no matter how large the array is.
The Gotcha: Forgetting to Recompute Ancestors After an Update
The most damaging bug in a hand-rolled segment tree isn't in build or query — it's dropping the last line of _update, the one that recomputes this.tree[node] from its two children on the way back up. Without it, the one leaf that changed is updated correctly, but nothing above it in the tree finds out.
This was tested directly: removing that line from _update on the same tree as above, then calling update(1, 10) and re-querying, gives query(1, 3) → 22 (correct, by coincidence of which nodes that particular range happens to touch) but query(0, 5) → 35 — the stale root value, when the real answer is 41. Two queries against the exact same tree, right after the exact same update, and one is right while the other is silently wrong.
That inconsistency is what makes this bug dangerous: a quick manual test with one query range can pass while a different range on the same data is wrong, so it's easy to ship confident that the update logic works. Always recompute every ancestor's merged value on the way back up — never just the leaf.
Segment Tree vs Prefix Sum vs Fenwick Tree
Three structures solve overlapping versions of the same range-query problem, and picking the right one comes down to whether the data changes and what operation you need combined:
- Prefix sum array — O(n) build, O(1) query, O(n) update. Best when the array is effectively static and you just need fast sums.
- Fenwick tree (Binary Indexed Tree) — O(n) build, O(log n) query, O(log n) update, but only for operations that have an inverse, like sum (subtraction undoes addition). Noticeably less code than a segment tree and a smaller constant factor.
- Segment tree — O(n) build, O(log n) query, O(log n) update, and it works for any associative operation, including min, max, and gcd, where there's no inverse operation to lean on the way a Fenwick tree does.
The practical rule: if all you'll ever need is range sums with updates, a Fenwick tree does the same job in noticeably less code. Reach for a segment tree when you need min/max/gcd-style queries, or when you want a structure general enough to extend later — lazy propagation for range updates, for instance, builds directly on top of the segment tree shape shown here.