Segment Trees Explained: Fast Range Queries

A segment tree is a binary tree data structure that answers range queries over an array — sum, minimum, maximum, greatest common divisor, and similar associative operations — in logarithmic time, while also supporting point or range updates without rebuilding the structure from scratch. It’s the standard answer to a specific, common problem: an array that changes over time, where you need to repeatedly query aggregate values over arbitrary subranges.

The problem with naive range queries

Given an array, “what’s the sum of elements from index 3 to index 17” is trivial to compute once, in linear time, by just summing that slice. The problem is repetition: if the array is queried many times, and updated between queries, recomputing each range sum from scratch is wasteful. A prefix-sum array fixes the query side — O(1) range sums after O(n) preprocessing — but breaks immediately when the array is updated, since a single element change requires recomputing every prefix sum after it, an O(n) update cost. Segment trees give up the O(1) query speed of prefix sums in exchange for O(log n) updates, which is the better tradeoff whenever the array isn’t static.

How the tree is structured

A segment tree built over an array of size n represents the whole array as its root, and recursively splits each node’s range in half until each leaf covers a single element:

• The root covers the entire array, range [0, n-1].
• Each internal node covers a contiguous range and has two children, each covering half of that range.
• Each leaf covers exactly one array element.
• Every internal node stores the aggregate (sum, min, max — whatever operation the tree is built for) of its entire range, computed from its two children.

For an array of size n, the tree has O(n) nodes total and a height of O(log n), since the range halves at each level. It’s commonly implemented as an array itself (using the same 2i/2i+1 child-indexing trick as a binary heap) rather than as linked nodes, which keeps it cache-friendly and avoids pointer overhead.

Answering a range query

To query a range [l, r], the algorithm walks down from the root, at each node checking three cases:

1. The node’s range is entirely outside [l, r] — contributes nothing, stop descending this branch.
2. The node’s range is entirely inside [l, r] — its stored aggregate is exactly what’s needed for that whole sub-range; use it directly and stop descending.
3. The node’s range partially overlaps [l, r] — recurse into both children and combine their results.

Because each level of the tree only requires descending into a bounded number of nodes that straddle the query boundary, a query touches O(log n) nodes total, regardless of how wide the query range is. That’s the core efficiency win over a naive linear scan.

Updating a value

Updating a single element means updating its leaf, then walking back up the tree recomputing every ancestor’s aggregate from its two children — a path of length O(log n) from leaf to root. Range updates (adding a value to every element in a range, for example) are also possible, but naively touch every leaf in the range; the standard technique to keep that O(log n) as well is lazy propagation, which defers pushing an update down into child nodes until a query actually needs to descend into them, storing a pending update at the higher node in the meantime.

Segment trees vs alternatives

	Segment tree	Prefix sum array	Fenwick tree (BIT)
Range query	O(log n)	O(1)	O(log n)
Point update	O(log n)	O(n)	O(log n)
Range update	O(log n) with lazy propagation	O(n)	O(log n), more involved
Supported operations	Any associative operation (sum, min, max, gcd)	Sum only, without extra structure	Primarily sum-like (invertible) operations
Implementation complexity	Moderate	Trivial	Simple, but less flexible

A Fenwick tree (binary indexed tree) solves a narrower version of the same problem — it’s simpler to implement and has a smaller constant factor, but it’s naturally suited to operations with an inverse (sum, XOR) and awkward for operations like minimum or maximum that don’t have one. Segment trees handle any associative operation uniformly, at the cost of a somewhat more involved implementation. For a static array with no updates at all, a plain prefix-sum array is simpler and faster — reach for a segment tree specifically when the array changes and you still need fast range queries against it.

Where this comes up in practice

Segment trees show up most often in competitive programming and in systems that need repeated range aggregates over changing data — range-minimum queries for problems like the lowest common ancestor in a tree, maintaining running statistics over a sliding or arbitrary window (related in spirit to the sliding window technique but generalized to arbitrary, not just contiguous-moving, ranges), and interval scheduling problems where ranges are queried and updated repeatedly. They’re less common in typical application backends, where a database index or a materialized view usually handles aggregate queries at a scale and durability that an in-memory tree structure isn’t built for — segment trees are the right tool specifically when the data lives in memory and needs sub-millisecond query and update latency.

The takeaway

A segment tree trades the O(1) query time of a prefix-sum array for O(log n) updates, making it the right structure whenever an array is both queried for range aggregates and modified repeatedly. Its binary structure — each node storing the aggregate of a range, split recursively in half — lets both queries and updates touch only O(log n) nodes. For static data, a simpler prefix-sum array wins; for sum-only operations on changing data, a Fenwick tree is a lighter-weight alternative. Reach for a full segment tree when the operation isn’t invertible or when the query type varies.