Expert · Module 26
Range queries
Answer sums, minimums and updates over ranges in logarithmic time.
A range query asks for a summary over a slice of an array, and the versions worth studying are the ones where the array keeps changing. This module builds the four structures that dominate the problem: sparse tables that answer static ranges in constant time, segment trees that trade space for updates, lazy propagation that lets one operation cover a whole subtree in one step, and Fenwick trees that compress the same tree into index arithmetic.
- 1Sparse tablesPro — members onlyPrecompute every power-of-two range once, then answer a minimum, maximum or gcd over any slice with two array reads. The trick survives only if the operation tolerates overlap.13 min
- 2Segment treesPro — members onlyA binary tree of partial answers over the array: build in linear time, update a point and answer a range in logarithmic time, merging with any associative operation instead of only sums.14 min
- 3Lazy propagationPro — members onlyA range update that covers a whole subtree records its work in one lazy slot instead of rewriting every leaf. Queries collect that work on the way down, which keeps both updates and queries at O(log n).13 min
- 4Fenwick treesPro — members onlyThe lowest set bit decides how many elements each cell owns, which buys prefix sums and point updates in O(log n) with one array of n plus 1 cells and a loop short enough to hold in your head.14 min