Start from the query mix
Range problems differ by what changes and what is asked. A static array with many range-sum queries needs only a prefix array: O(n) preprocessing and O(1) per query. When point updates interleave with range queries, prefix sums degrade to O(n) per update, so a Fenwick tree or segment tree is worth its extra code. Write the expected counts of updates and queries before choosing; a structure that is optimal for one mix can be the slowest choice for another.
Fenwick trees and segment trees
A Fenwick (binary indexed) tree stores partial sums whose spans follow the lowest set bit of each index. Both prefix queries and point updates touch O(log n) cells, and the array uses n + 1 slots. A segment tree stores an aggregate for every node of a balanced partition; it supports any associative combine such as min, max or gcd, and with lazy propagation it also supports range updates, at roughly four times the memory and more code to get right.
Intervals and bit sets
Sorted, non-overlapping intervals in a TreeMap keyed by start allow O(log n) lookup of the interval covering a point and amortized merging on insert, because each interval is created once and removed at most once. A BitSet packs booleans into 64-bit words, so membership is O(1) and bulk and/or/xor operations process 64 flags per word. Bit sets fit dense small integer universes; sparse or huge universes waste memory, and a hash set or sorted list is better.
Worked Java example
Illustrative snippet: imports, surrounding types or collaborators may be omitted. Read the assumptions before adapting it.
final class Fenwick {
private final long[] tree;
Fenwick(int n) { tree = new long[n + 1]; }
void add(int index, long delta) { // index is 0-based
for (int i = index + 1; i < tree.length; i += i & -i) tree[i] += delta;
}
long prefixSum(int endExclusive) { // sum of [0, endExclusive)
long sum = 0;
for (int i = endExclusive; i > 0; i -= i & -i) sum += tree[i];
return sum;
}
long rangeSum(int from, int toExclusive) {
return prefixSum(toExclusive) - prefixSum(from);
}
}Walkthrough
i & -i isolates the lowest set bit, which is the span length of tree[i]. add climbs to every cell whose span covers the index; prefixSum walks down by removing the lowest bit until zero. For n = 8, add(2, 5) updates cells 3, 4 and 8; prefixSum(5) reads cells 5 and 4. rangeSum subtracts two prefixes, so it needs an invertible combine: sums work, but min and max do not, which is when a segment tree is required.
Practice it yourself
A dashboard receives 10^5 point updates and 10^5 range-sum queries over 10^6 counters. Compare a plain array, a prefix array and a Fenwick tree, then explain what changes if the query becomes range minimum.
Check your reasoning
A plain array gives O(1) updates but O(n) queries, around 10^11 operations worst case. A prefix array gives O(1) queries but O(n) updates, the same worst case. The Fenwick tree gives O(log n) for both, about 2 × 10^5 × 20 = 4 × 10^6 cell touches. Range minimum is not invertible, so prefix subtraction fails; use a segment tree with O(log n) query and update, or a sparse table if the data is static.
Recall checklist
- Explain the main invariant or contract without looking.
- Trace the example and test an edge case.
- State time, space, input variables and assumptions where relevant.
- Explain one alternative and when you would choose it.