Interview Guide: Sparse Tables Problems and Solutions

What is a Sparse Table?

A Sparse Table is a data structure that answers range queries on a static array in O(1) time after O(n log n) preprocessing. It's specifically designed for idempotent operations — functions where overlapping intervals in a query do not change the result. Classic examples include:

• Range Minimum Query (RMQ)
• Range Maximum Query
• Range Greatest Common Divisor (GCD)
• Range Bitwise AND / OR

The core insight is brilliantly simple: any range [L, R] can be covered by two precomputed intervals of length 2^k that overlap in the middle. Because the operation is idempotent (e.g., min(a, a) = a), the overlap doesn't corrupt the answer. This gives you true O(1) queries with no recursion, no tree traversal, just two lookups and one operation.

Structure and Construction

The Sparse Table is a 2D array st[j][i] where:

• i is the starting index of an interval (0 ≤ i < n)
• j is the power of two exponent, representing interval length 2^j
• st[j][i] stores the result of applying the operation on the interval [i, i + 2^j - 1]

Construction follows a dynamic programming pattern similar to binary lifting:

// st[0][i] = arr[i]  (base: intervals of length 1)
// st[j][i] = combine(st[j-1][i], st[j-1][i + 2^(j-1)])

Complete C++ Implementation for Range Minimum Query

Below is a production-ready Sparse Table class that handles RMQ. It precomputes floor(log2) values for all lengths to make queries truly O(1):

#include <vector>
#include <cmath>
#include <algorithm>
#include <limits>

class SparseTable {
private:
    std::vector<std::vector<int>> st;   // st[j][i] = min in [i, i+2^j-1]
    std::vector<int> log_table;          // precomputed floor(log2) values
    int n;

public:
    SparseTable(const std::vector<int>& arr) {
        n = arr.size();
        
        // Precompute log2 for all lengths up to n
        log_table.resize(n + 1);
        log_table[1] = 0;
        for (int i = 2; i <= n; i++) {
            log_table[i] = log_table[i / 2] + 1;
        }
        
        // Maximum power of two needed
        int K = log_table[n] + 1;
        st.assign(K, std::vector<int>(n));
        
        // Base layer: intervals of length 1
        for (int i = 0; i < n; i++) {
            st[0][i] = arr[i];
        }
        
        // Build layers for j = 1..K-1
        for (int j = 1; j < K; j++) {
            int len = 1 << j;           // interval length = 2^j
            int half = 1 << (j - 1);    // half-length = 2^(j-1)
            for (int i = 0; i + len <= n; i++) {
                st[j][i] = std::min(st[j-1][i], st[j-1][i + half]);
            }
        }
    }
    
    // Query minimum in inclusive range [L, R]
    int query(int L, int R) const {
        int length = R - L + 1;
        int j = log_table[length];
        int span = 1 << j;
        // Two overlapping intervals of length 2^j cover [L, R]
        return std::min(st[j][L], st[j][R - span + 1]);
    }
};

Query Breakdown: How O(1) Really Works

Let's trace a query on range [3, 10] (length = 8):

• log_table[8] = 3, so j = 3, span = 2^3 = 8
• First interval: st[3][3] covers [3, 3+8-1] = [3, 10]
• Second interval: st[3][10-8+1] = st[3][3] also covers [3, 10]
• They are identical — overlap is total, result is correct

Now for range [2, 7] (length = 6):

• log_table[6] = 2 (since 2²=4 ≤ 6 < 2³=8), j = 2, span = 4
• First interval: st[2][2] covers [2, 5]
• Second interval: st[2][7-4+1] = st[2][4] covers [4, 7]
• Overlap region is [4, 5] — but for min, overlapping doesn't double-count

This is the magic: the two intervals always together cover the full query range, and idempotence ensures correctness despite the overlap.

Why Sparse Tables Matter in Interviews

Interviewers love Sparse Tables because they test your understanding of:

• Preprocessing vs query tradeoffs — when to invest O(n log n) build time for O(1) queries
• Idempotence as a property of operations — knowing why sum queries don't work here
• Binary representation tricks — representing any integer as a sum of powers of two (in this case, just the largest power ≤ length and the remainder covered by overlap)
• Static vs dynamic data — recognizing when the array won't change, making Sparse Table the optimal choice over Segment Trees

Comparison with Segment Trees

Here's a quick decision guide:

If you have a static array and need many range queries (millions) for an idempotent operation, Sparse Table dominates. If updates are required or the operation is not idempotent (sum, XOR), use a Segment Tree or Fenwick Tree.

Extended Examples: Beyond Minimum

Range Maximum Query

Simply replace std::min with std::max in both build and query. Everything else stays identical:

// Inside build loop:
st[j][i] = std::max(st[j-1][i], st[j-1][i + half]);

// Query:
return std::max(st[j][L], st[j][R - span + 1]);

Range GCD Query

GCD is also idempotent because gcd(a, a) = a. The same structure applies — just use your GCD function (the standard std::gcd in C++17):

#include <numeric>  // for std::gcd

// Build:
st[j][i] = std::gcd(st[j-1][i], st[j-1][i + half]);

// Query:
return std::gcd(st[j][L], st[j][R - span + 1]);

Range Bitwise AND / OR

Both bitwise AND and OR are idempotent (a & a = a, a | a = a). The pattern holds perfectly:

// For range AND:
st[j][i] = st[j-1][i] & st[j-1][i + half];
query: return st[j][L] & st[j][R - span + 1];

// For range OR:
st[j][i] = st[j-1][i] | st[j-1][i + half];
query: return st[j][L] | st[j][R - span + 1];

Common Interview Problems Solved with Sparse Tables

Problem 1: "Find Minimum in Every Sliding Window" (Static Array Version)

Given a static array and a list of query intervals, return the minimum for each. With a Sparse Table built once, each query is O(1):

std::vector<int> solve(std::vector<int>& arr, 
                      const std::vector<std::pair<int,int>>& queries) {
    SparseTable st(arr);
    std::vector<int> results;
    results.reserve(queries.size());
    for (auto [L, R] : queries) {
        results.push_back(st.query(L, R));
    }
    return results;
}

Problem 2: "Range Frequency of Minimum"

A more nuanced problem: not just the minimum value, but how many times it appears in the range. This requires storing pairs (value, frequency) and defining a custom combine function:

struct MinFreq {
    int value;
    int freq;
};

MinFreq combine(const MinFreq& a, const MinFreq& b) {
    if (a.value < b.value) return a;
    if (b.value < a.value) return b;
    // Values equal: sum frequencies
    return {a.value, a.freq + b.freq};
}

// Base layer: st[0][i] = {arr[i], 1}
// Build with combine()
// Query returns both min value and its frequency in the range

Problem 3: "Longest Prefix in Range with Value Below Threshold"

You can combine Sparse Table with binary search. Use the Sparse Table to query the minimum in [L, mid] and binary search for the rightmost index where the min stays below the threshold. Each check is O(1), yielding O(log n) per query.

Problem 4: "2D Range Minimum Query"

Sparse Tables extend to 2D grids. Build a Sparse Table for each row, then build a Sparse Table of those tables for columns. This gives O(1) queries on submatrices with O(n×m×log n×log m) preprocessing. While space-heavy, it's the fastest query-time solution for static 2D RMQ.

Best Practices for Sparse Table Implementation

1. Always Precompute the Log Table

Computing floor(log2(x)) via std::log2 or a while-loop per query turns O(1) into O(log n). Precompute it once:

log_table[1] = 0;
for (int i = 2; i <= n; i++) {
    log_table[i] = log_table[i / 2] + 1;
}

2. Be Careful with 0-Based vs 1-Based Indexing

The formulas above assume 0-based indexing. If you use 1-based, adjust: interval [L, R] has length R-L+1, and the second interval starts at R - (1<. Keep consistent throughout your code — mixing indices is a common bug.

std::vector<int> st_flat(K * n);
// Access: st_flat[j * n + i]
// Build: st_flat[j*n + i] = combine(st_flat[(j-1)*n + i], 
//                                    st_flat[(j-1)*n + i + half]);