Skip to content
Tutorials Center
My learning

Topics

Lesson 116 of 225 ยท Tries and Range Queries

Sparse Tables and RMQ

Answer range minimum queries in O(1) with a sparse table in Python. Build it in O(n log n), learn why overlap works for idempotent operations, and see LCA via RMQ.

Imagine an array that never changes and a stream of questions: "what is the smallest value between index 3 and index 9?" You could scan the range every time, which costs O(n) per question. A segment tree answers in O(log n). A sparse table answers in O(1): two lookups and one comparison, no loop at all.

The price is that the array must be static (no updates) and the table takes O(n log n) memory. When the data is read-only and queries are many, that is a great trade. The query is called a range minimum query, or RMQ, and it hides inside many other problems, including finding the lowest common ancestor in a tree.

The idea: precompute every window whose length is a power of two

Instead of storing answers for all O(nยฒ) ranges, store answers only for ranges whose length is 1, 2, 4, 8, and so on. Let table[k][i] be the minimum of the 2^k elements starting at index i.

TEXT
a      = [5, 2, 4, 7, 1, 3, 6, 8]

k=0 (len 1): 5  2  4  7  1  3  6  8
k=1 (len 2): 2  2  4  1  1  3  6
k=2 (len 4): 2  1  1  1  1
k=3 (len 8): 1

Each row is built from the row above it. A window of length 2^k is two windows of length 2^(k-1) placed side by side:

table[k][i] = min(table[k-1][i], table[k-1][i + 2^(k-1)])

There are about logโ‚‚(n) rows, and each row has at most n entries, so the table holds O(n log n) values and builds in O(n log n) time.

Python Build the table and print every level

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Answering a query with two overlapping windows

Suppose we want the minimum of a[left..right] (both ends included). Let length = right - left + 1 and let k be the largest integer with 2^k <= length. Two windows of length 2^k cover the whole range: one starting at left, one ending at right. They may overlap in the middle.

TEXT
range [1..6], length 6, k = 2 (window 4)

index:   0  1  2  3  4  5  6  7
a:       5  2  4  7  1  3  6  8
            [-------]            window starting at left  (1..4)
                  [-------]      window ending at right   (3..6)
answer = min(table[2][1], table[2][3])

The overlap is harmless for the minimum: counting the same element twice does not change the smallest value. That is the key insight and the reason the query is O(1) with no loop.

To find k quickly, use length.bit_length() - 1, which is floor(logโ‚‚(length)) in constant time. Or precompute a log array. Both are fine.

Python Constant-time queries, checked against brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

From brute force to sparse table

Here is the progression for "many queries on a fixed array":

Approach Build Query Memory Updates
Scan the range none O(n) O(1) trivial
Precompute all ranges O(nยฒ) O(1) O(nยฒ) rebuild
Segment tree O(n) O(log n) O(n) O(log n)
Sparse table O(n log n) O(1) O(n log n) rebuild

Let's count the work instead of timing it. Each brute-force query reads every element in its range; a sparse-table query reads exactly two table cells.

Python Counting reads: scan versus sparse table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Which operations work? Idempotent ones

The overlap trick needs an operation where op(x, x) == x. Such an operation is called idempotent. These work with the same class and a different op:

  • min and max
  • math.gcd (the gcd of overlapping groups is still the gcd of the union)
  • bitwise AND and OR

Sum, product and XOR are not idempotent. Counting an element twice changes the result, so the two-window query gives a wrong answer. Never use the overlap query for them.

Watch out: SparseTable(values, op=operator.add) builds fine and then returns wrong sums. When the two windows overlap, the shared elements are counted twice; when the length is a power of two, both windows are the same window and the answer is exactly doubled. For sums, use prefix sums.

Python gcd works, sum silently breaks (wrong on purpose)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Application: lowest common ancestor via RMQ

The lowest common ancestor (LCA) of two nodes in a rooted tree is the deepest node that has both as descendants. Here is a neat reduction to RMQ:

  1. Walk the tree depth-first and write down the node every time you arrive at it or return to it (an Euler tour), together with its depth.
  2. Remember the first position where each node appears.
  3. The LCA of u and v is the shallowest node between their first positions in the tour.

That is a range minimum query over depths, which a sparse table answers in O(1). After an O(n log n) preparation you can answer millions of LCA questions instantly. Tree structure itself is covered in trees and tree traversals.

Python LCA with an Euler tour and a sparse table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Complexity

Part Time Space
Build O(n log n) O(n log n)
Query O(1) O(1) extra
Update not supported (rebuild in O(n log n))

The log factor comes from the number of rows (about logโ‚‚ n), and every row costs O(n) to fill. For n = 10โถ that is roughly twenty rows of a million numbers each, which is heavy in Python but fine in a compiled language.

Common mistakes

  • Off-by-one on the second window. The second window starts at right - 2^k + 1, not right - 2^k.
  • Using it for sums. Only idempotent operations are safe with the overlap query.
  • Expecting updates. One changed element invalidates up to n log n cells. Use a segment tree or a Fenwick tree when the data changes.
  • Computing the log with math.log2. Floating-point rounding can give the wrong k. Use bit_length() - 1 or a precomputed table.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does table[k][i] store in a sparse table for minimum queries?

    Each cell covers a window whose length is a power of two, 2^k, beginning at i.
  2. 2. Why can a sparse table answer a minimum query with two overlapping windows?

    The operation is idempotent, so covering some elements twice cannot change the result.
  3. 3. Which operation must NOT be used with the two-window query?

    Sum counts the overlapping elements twice, so it returns a wrong total. Use prefix sums instead.
  4. 4. A sparse table is built over n elements. What are its build time and memory?

    There are about log2(n) rows and each row has up to n entries.
  5. 5. For a range of length 6, which window length 2^k does the query use?

    k is floor(log2(6)) = 2, so the windows have length 4 and together cover the range of 6.

Summary

  • A sparse table stores the answer for every window whose length is a power of two, built row by row from the row above.
  • A query on [left, right] combines two windows of length 2^k, where k = floor(log2(length)); they may overlap.
  • Queries cost O(1); building costs O(n log n) time and space; the array must not change.
  • Only idempotent operations (min, max, gcd, AND, OR) work with the overlap trick; use prefix sums for sums.
  • LCA reduces to RMQ over an Euler tour of the tree.
  • For changing data choose a segment tree or Fenwick tree.

Next: Square Root Decomposition and Mo's Algorithm