Range Query Trees
Every structure on this page exists to answer one shape of question: give me a fold over a range, and let me change an element, over and over, on an array you are not allowed to re-scan each time. Arrays are perfect at one of those two jobs and terrible at the other. This page is about the structure that is merely good at both, which turns out to be exactly what you want the moment both operations are live in the same problem.
1. The problem: queries and updates at the same time
Two operations, repeated, on the same array:
update(i, val)- change one element.query(l, r)- fold a range: sum it, find its minimum, and so on.
If you only ever do one of these, the answer is trivial and you should not be reading the rest of this page:
| Structure | update(i, val) | query(l, r) | When it is enough |
|---|---|---|---|
| Plain array | O(1) - write the slot | O(n) - rescan the range | Updates are frequent, queries are rare |
| Prefix sum array | O(n) - rebuild every suffix | O(1) - two lookups, subtracted | The array is built once and never changes |
| Segment tree | O(log n) | O(log n) | Both operations are live - interleaved, and neither is rare |
If your
problem statement says "you are also given k update operations," that sentence
is the whole justification for the tree. Skip it and either the queries or the
updates degrade to O(n), and O(n) times O(q) queries is the actual
O(n * q) your dense test case is timing out on.
2. Prefix sums, and exactly where they break
A prefix sum array P where P[i] = a[0] + a[1] + ... + a[i-1] turns any range
sum into a subtraction: sum(l, r) = P[r+1] - P[l]. One array, built once,
O(1) per query forever - as long as "forever" does not include a write.
The break is a single write. Change a[2], and every prefix sum from P[3]
onward is now wrong - the entire structure has to be rebuilt from that point
on, which is O(n). Prefix sums buy O(1) queries by baking the entire
history of the array into every entry, and baking is not something you can
partially undo.
A prefix-sum solution silently assumes the array never changes again. It
is the correct answer to "range sum queries, no updates" (LeetCode 303) and the
wrong answer the instant the problem adds "range sum query - mutable"
(LeetCode 307), even though the two problem statements look almost identical.
Read the constraints for the word "update" before reaching for P.
3. Segment trees
A segment tree fixes this by never fully committing to either extreme. Instead of one array that describes the whole range, it builds a binary tree in which every node owns an interval and stores the fold of that interval - the sum, the min, whatever the query needs.
- The root owns the whole array,
[0, n). - Every internal node splits its interval in half and hands the halves to its two children.
- Every leaf owns a single index.
Building it is a post-order walk: each node's value is the fold of its children, so the leaves have to exist before any internal node's value does.
A point update walks down to the one leaf that owns index i, changes it, and
recomputes every ancestor on the way back up - O(log n) nodes, one per level.
The query is the interesting part. query(l, r) does not walk down to every
leaf in [l, r] - it stops as soon as a node's interval fits entirely inside
[l, r], and uses that node's precomputed value directly.
This is the whole reason the query is O(log n): at every level of the tree,
the range [l, r] slices at most two nodes in half (one at its left edge, one
at its right edge) and every node strictly between those cuts is either fully
inside or fully outside. A tree of height log n has at most 2 * log n
"boundary" nodes total, and everything else resolves in one comparison.
merge is that it be associative.Nothing above
depends on it being addition. Swap merge for min, max, gcd, bitwise
|, or even 2x2 matrix multiplication, and every line of build, update and
query still works unchanged - because all a segment tree ever does is fold
an associative operation over a decomposition of the range, and associativity
is exactly the property that makes "fold the pieces in any grouping" give the
same answer. This is the generalisation worth keeping: "segment tree" is a
shape, not a sum.
merge | identity | Answers |
|---|---|---|
a + b | 0 | range sum |
min(a, b) | +inf | range minimum (RMQ) |
max(a, b) | -inf | range maximum |
gcd(a, b) | 0 | range GCD |
a | b | 0 | range OR (bitmask problems) |
| 2x2 matrix product | identity matrix | range Fibonacci-style linear recurrences |
4. Lazy propagation
Point updates are O(log n), but a range update - "add 5 to every element
from index 2 to 6" - naively touches every leaf in that range, which is
O(n). Lazy propagation fixes this the same way the tree fixed range queries:
stop at the first node whose interval fits inside the update range, and defer
the rest.
Every node gets a lazy tag. Setting a node's tag does not mean "apply this update now" - it means "this whole subtree owes an update it has not been told about yet." The node's own stored value is updated immediately (it represents its whole interval, so the update applies to it in one step), but the children are left untouched until something actually needs to look inside them.
Every function that is about to recurse INTO a node's children must call
push_down on that node first. The invariant a lazy segment tree relies on
is: a node's own stored value is always correct for its whole interval, but
its children's values are only correct once the node's tag has been pushed. If
update_range or query reads self.tree[2 * node + 1] without pushing down
first, it reads a value that is missing an update that was already recorded
one level up - and the bug is silent, because it only shows up on ranges that
straddle a previously-tagged boundary, which most test cases will not hit.
A lazy tag is an IOU, not a lie. The node's own answer is already correct - it is not lying about its interval. The tag just means the children have not been told yet, and the only thing that ever collects the debt is a future visit that needs to look inside.
5. Fenwick trees
A segment tree can do more than a Fenwick tree (any associative op, arbitrary merge functions, lazy propagation) but a Fenwick tree (also called a binary indexed tree, or BIT) does one job - prefix folds of an invertible operation like sum - in less memory and with less code, using a single array the same size as the input.
The entire structure is one index trick: i & -i isolates the lowest set
bit of i. In two's-complement, -i is ~i + 1, so every bit below the
lowest set bit of i flips to 1 in ~i, then the +1 carries through those
flipped bits and stops exactly at the lowest set bit - leaving i & -i equal
to just that one bit.
That single number, i & -i, is the size of the range that index i is
responsible for, and it is what both operations walk by.
update walks up by repeatedly adding i & -i - each step jumps to the next
larger index whose range includes i. prefix_sum walks down by repeatedly
subtracting i & -i - each step drops to the previous index whose range ends
exactly where the current one starts. Both walks take O(log n) steps because
each step clears at least one more bit of i.
| Segment tree | Fenwick tree | |
|---|---|---|
| Operations it needs | any associative op | invertible op (sum, XOR) for subtraction-based range queries |
| Range update + range query | yes, with lazy propagation | yes, but needs a second Fenwick array (a known but fiddly trick) |
| Memory | O(n), with a 4n-sized array in practice | O(n), one array the same size as the input |
| Code size | larger - explicit tree, recursive build/query | smaller - one array, two short loops |
| What it generalises to | min/max/gcd RMQ, matrix exponentiation ranges | mostly stays a sum/XOR/count structure |
You cannot subtract your way to a range minimum, so a plain Fenwick tree
cannot answer "min of a range" the way it answers "sum of a range."
prefix_sum(r) - prefix_sum(l-1) works because subtraction undoes addition.
There is no operation that undoes min, so range_min(l, r) cannot be
recovered from two prefix mins the way range_sum can from two prefix sums.
Range minimum needs a segment tree (or a sparse table, if updates are absent).
6. Which structure for which query
| You need | Reach for | Because |
|---|---|---|
| Range sum, values only read (no updates) | Prefix sum array | O(1) query, and you never pay for updates you don't have |
| Range sum, with point updates | Fenwick tree | Smallest code, smallest memory, and sum is invertible |
| Range min/max/gcd, with point updates | Segment tree | Not invertible, so a Fenwick tree cannot subtract its way to the answer |
| Range updates AND range queries | Segment tree with lazy propagation | Both operations need to skip touching every leaf; only the tree defers work |
| Range min/max, NO updates at all | Sparse table | O(1) query after O(n log n) preprocessing - overlapping-interval doubling beats a tree when nothing ever changes |
| An arbitrary associative fold (matrix product, custom merge) | Segment tree | The only one of these that only requires associativity, not invertibility |
"Can I read once and forget the rest?" - use a prefix structure. "Can I undo the operation with subtraction?" - use a Fenwick tree. "Neither?" - use a segment tree. In that order, because each one is progressively more general and progressively more code, and there is no reason to reach for a segment tree when a five-line Fenwick tree already answers the question.
Where to go next
- Balanced Trees - the other family of tree
built to keep an operation at
O(log n)under updates, this time for ordering rather than folding. - Heaps - a different kind of range answer: not "any
range," just "the current minimum or maximum," in exchange for
O(1)peek. - Traversal and Recursion - the post-order
"build from children" shape that a segment tree's
buildandupdateboth follow. - Trees in the Wild - where a Fenwick-tree- style block decomposition turns up outside interview problems.