Range Trees
Precompute overlapping range sums, then update only the ancestors that depend on one value.
The idea
Fenwick trees encode prefix sums with least-significant-bit jumps. A range query subtracts two short prefix decompositions, and a point update visits the nodes whose covered ranges contain that index.
Segment trees store explicit interval sums in a binary tree. Queries choose disjoint nodes that exactly cover the requested range, while point updates recompute one leaf-to-root path.
A warehouse can total one aisle by subtracting cumulative checkpoints, or by combining labeled shelf sections that tile the aisle exactly.
When to reach for it
- Many range queries are mixed with point updates.
- Recomputing each range directly would be too slow.
- The combine operation is associative, such as sum, minimum, or maximum.
Language-independent template
build partial range aggregates
query by combining a logarithmic decomposition
update one point and propagate through its ancestorsComplexity — time O(n log n) build, O(log n) query/update, space O(n).
Common mistakes
- Mixing Fenwick tree's one-based storage with zero-based input indices.
- Using an inclusive endpoint as if it were exclusive.
- Updating a leaf without recomputing every ancestor.
Practice progression
Canonical interview problems, ordered from foundation to advanced application.
Answer repeated static range-sum queries.
Support point updates and range sums.
Count subarray sums inside a target interval.