Range Structures

Range Query Structures

These structures all answer the same shape of question: something about a range of an array, repeatedly, while the array may be changing. A prefix sum handles it when nothing changes. Once updates enter, you need a structure, and which one depends on the operation and whether updates are point or range. This is the most advanced topic on the site and the least commonly required, but it is decisive when it does come up.

3 patterns6 techniquesJava code

Where to start, and what comes next

01
Binary Indexed Tree (Fenwick)
The Fenwick tree first, despite being the cleverest, because it is ten lines and covers the most common case of prefix sums with point updates.
Point Update, Prefix Query Range Update, Point Query
02
Segment Tree
The segment tree, which is more code and does everything the Fenwick tree cannot, including minimums and range updates via lazy propagation.
Build & Query Lazy Propagation Merge Sort Tree
03
Sparse Table
The sparse table, for O(1) queries on static data. Last because its constraint, no updates at all, is the most limiting.
Range Minimum Query

If you only have time for three things

Choosing by operation: sums with point updates go to a Fenwick tree, minimums or range updates go to a segment tree, static minimums go to a sparse table.
Lazy propagation, and specifically that a pending value must be pushed down before descending, or a query reads a stale node.
Why a sparse table can answer in O(1): a minimum is idempotent, so two overlapping blocks are safe, which is exactly why sums cannot use the same trick.

In an interview

Ask whether the array changes before choosing anything. If it does not, a prefix sum or a sparse table is enough and reaching for a segment tree is over-engineering. If it does, say which operation you need, because that decides between the two trees on its own. Being able to explain why a Fenwick tree cannot do minimums is a strong signal that you understand both.

The idea underneath

If you only need prefix queries with point updates, use a BIT (simpler). If you need arbitrary range queries + range updates, use a segment tree with lazy propagation. Sparse table is O(1) query but static.

Problems that use these patterns

Range Sum Query - MutableCount of Smaller Numbers After SelfRange Minimum QueryLongest Increasing Subsequence (BIT approach)

Head to head

Segment Tree vs Fenwick Treea tree of ranges, one node per range against a flat array indexed by bit tricks

Questions people ask

Fenwick tree or segment tree?

Fenwick if you only need prefix sums with point updates, because it is a fraction of the code and memory. Segment tree for minimums, maximums, range updates, or any node that must store something richer than a number.

Why can a Fenwick tree not answer minimum queries?

Because it works by subtracting one prefix from another, which is meaningful for sums and meaningless for minimums. Once other values are involved you cannot remove one element's contribution from a minimum.

Do I actually need these in interviews?

Rarely, and mostly at companies that lean towards competitive programming. Knowing that they exist and which one solves which shape is usually enough, and it is a better use of time than implementing all three from memory.