Sparse Table for Range Queries in O(1)

---

The Problem: Repeated Range Queries

Imagine you have a static array (no updates) and need to answer thousands of queries like “what is the minimum value between index l and index r?” A naive approach scans the range each time, giving O(n) per query. With Q queries, that is O(n * Q) — potentially billions of operations.

Sparse tables solve this by precomputing answers for all ranges whose lengths are powers of 2. Any arbitrary range can then be answered by combining at most two precomputed ranges, giving us O(1) per query after O(n log n) preprocessing.

---

The Core Idea

Power-of-2 Decomposition

Every positive integer can be represented as a sum of distinct powers of 2 (binary representation). Sparse tables exploit this by precomputing answers for ranges of length 1, 2, 4, 8, 16, and so on.

For an array of size n, we build a 2D table st[k][i] where:

• k is the “level” (the exponent in 2^k)
• i is the starting index
• st[k][i] stores the answer for the range [i, i + 2^k - 1]

The maximum level we need is floor(log2(n)), so the table has dimensions (log2(n) + 1) x n.

Why This Works for Min/Max

For idempotent operations (where applying the operation to overlapping ranges gives the correct result), we can answer queries by overlapping two precomputed ranges.

For a query min(l, r):

1. Find the largest k such that 2^k {'<'}= r - l + 1
2. Answer = min(st[k][l], st[k][r - 2^k + 1])

The two ranges [l, l+2^k-1] and [r-2^k+1, r] might overlap, but since min(a, a) = a, overlapping does not change the result.

---

Building the Sparse Table

Step-by-Step Construction

Level 0 (k=0): Each range has length 2^0 = 1, so st[0][i] = arr[i].

Level k (k > 0): Each range of length 2^k is split into two halves of length 2^(k-1):

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

This is the key recurrence. We combine two adjacent precomputed ranges from the previous level.

Python Implementation: Build

import math

def build_sparse_table(arr):
    """Build a sparse table for range minimum queries."""
    n = len(arr)
    if n == 0:
        return [], []
    
    # Maximum level needed
    LOG = int(math.log2(n)) + 1 if n > 0 else 1
    
    # Precompute floor(log2(i)) for all i up to n
    # This avoids repeated log computations during queries
    log_table = [0] * (n + 1)
    for i in range(2, n + 1):
        log_table[i] = log_table[i // 2] + 1
    
    # Initialize sparse table
    # st[k][i] = min of arr[i..i+2^k-1]
    st = [[0] * n for _ in range(LOG)]
    
    # Level 0: ranges of length 1
    for i in range(n):
        st[0][i] = arr[i]
    
    # Fill remaining levels
    for k in range(1, LOG):
        # i + 2^k - 1 must be < n
        for i in range(n - (1 << k) + 1):
            st[k][i] = min(st[k - 1][i], st[k - 1][i + (1 << (k - 1))])
    
    return st, log_table


# Example
arr = [3, 1, 4, 1, 5, 9, 2, 6]
st, log_table = build_sparse_table(arr)

# Print the sparse table
for k in range(len(st)):
    valid = len(arr) - (1 << k) + 1
    print(f"k={k} (len={1 << k}): {st[k][:valid]}")

Output:

k=0 (len=1): [3, 1, 4, 1, 5, 9, 2, 6]
k=1 (len=2): [1, 1, 1, 1, 5, 2, 2]
k=2 (len=4): [1, 1, 1, 1, 2]
k=3 (len=8): [1]

---

Querying in O(1)

The Overlap Trick

For idempotent functions, we pick the largest power of 2 that fits within the range and use two overlapping sub-ranges:

def query_min(st, log_table, l, r):
    """Return the minimum value in arr[l..r] in O(1)."""
    length = r - l + 1
    k = log_table[length]
    return min(st[k][l], st[k][r - (1 << k) + 1])

Example Walkthrough

For arr = [3, 1, 4, 1, 5, 9, 2, 6], query min(1, 6):

1. Length = 6 - 1 + 1 = 6
2. k = floor(log2(6)) = 2, so 2^2 = 4
3. Left range: st[2][1] = min(arr[1..4]) = 1
4. Right range: st[2][3] = min(arr[3..6]) = 1
5. Answer: min(1, 1) = 1

The ranges [1,4] and [3,6] overlap at indices 3 and 4, but since min is idempotent, this is fine.

# Complete usage
arr = [3, 1, 4, 1, 5, 9, 2, 6]
st, log_table = build_sparse_table(arr)

# Test several queries
queries = [(0, 7), (1, 6), (2, 5), (0, 3), (4, 7)]
for l, r in queries:
    result = query_min(st, log_table, l, r)
    # Verify against brute force
    expected = min(arr[l:r+1])
    assert result == expected
    print(f"min({l}, {r}) = {result}")

Output:

min(0, 7) = 1
min(1, 6) = 1
min(2, 5) = 1
min(0, 3) = 1
min(4, 7) = 2

---

Idempotent Functions: Why This Only Works for Some Operations

An operation f is idempotent if f(a, a) = a. This means applying it to overlapping ranges still gives the correct result.

Operation	Idempotent?	Sparse Table O(1) Query?
min	Yes	Yes
max	Yes	Yes
gcd	Yes	Yes
bitwise AND	Yes	Yes
bitwise OR	Yes	Yes
sum	No	No (double-counts overlap)
product	No	No

For non-idempotent operations like sum, you cannot use the overlap trick. You would need to decompose the range into non-overlapping powers of 2 (like binary indexed trees do), which takes O(log n) per query.

Sparse Table for Range GCD

import math

def build_sparse_table_gcd(arr):
    """Sparse table for range GCD queries."""
    n = len(arr)
    LOG = int(math.log2(n)) + 1 if n > 0 else 1
    
    log_table = [0] * (n + 1)
    for i in range(2, n + 1):
        log_table[i] = log_table[i // 2] + 1
    
    st = [[0] * n for _ in range(LOG)]
    
    for i in range(n):
        st[0][i] = arr[i]
    
    for k in range(1, LOG):
        for i in range(n - (1 << k) + 1):
            st[k][i] = math.gcd(st[k - 1][i], st[k - 1][i + (1 << (k - 1))])
    
    return st, log_table

def query_gcd(st, log_table, l, r):
    length = r - l + 1
    k = log_table[length]
    return math.gcd(st[k][l], st[k][r - (1 << k) + 1])


arr = [12, 6, 18, 9, 15, 3]
st, log_table = build_sparse_table_gcd(arr)
print(f"GCD(0, 5) = {query_gcd(st, log_table, 0, 5)}")  # 3
print(f"GCD(0, 2) = {query_gcd(st, log_table, 0, 2)}")  # 6
print(f"GCD(1, 3) = {query_gcd(st, log_table, 1, 3)}")  # 3

---

Sparse Table for Range Maximum (Index Version)

Sometimes you need the index of the minimum/maximum element, not just the value. This is useful for problems like Range Minimum Query (RMQ) used in LCA algorithms.

def build_sparse_table_index(arr):
    """Build sparse table that stores indices of minimum elements."""
    n = len(arr)
    LOG = int(math.log2(n)) + 1 if n > 0 else 1
    
    log_table = [0] * (n + 1)
    for i in range(2, n + 1):
        log_table[i] = log_table[i // 2] + 1
    
    # st[k][i] stores the INDEX of minimum in arr[i..i+2^k-1]
    st = [[0] * n for _ in range(LOG)]
    
    for i in range(n):
        st[0][i] = i  # Index of itself
    
    for k in range(1, LOG):
        for i in range(n - (1 << k) + 1):
            left = st[k - 1][i]
            right = st[k - 1][i + (1 << (k - 1))]
            st[k][i] = left if arr[left] <= arr[right] else right
    
    return st, log_table

def query_min_index(arr, st, log_table, l, r):
    """Return the index of the minimum in arr[l..r]."""
    length = r - l + 1
    k = log_table[length]
    left = st[k][l]
    right = st[k][r - (1 << k) + 1]
    return left if arr[left] <= arr[right] else right


arr = [3, 1, 4, 1, 5, 9, 2, 6]
st, log_table = build_sparse_table_index(arr)
idx = query_min_index(arr, st, log_table, 2, 7)
print(f"Index of min in arr[2..7] = {idx}, value = {arr[idx]}")
# Index of min in arr[2..7] = 6, value = 2

---

Complexity Analysis

Operation	Time	Space
Build	O(n log n)	O(n log n)
Query (idempotent)	O(1)	-
Query (non-idempotent)	O(log n)	-
Update	Not supported	-

Space breakdown: The table has log2(n) rows and n columns. For n = 10^6, that is about 20 * 10^6 = 20M integers, which is approximately 80 MB for 32-bit ints. This is usually fine, but be aware of memory limits in competitive programming.

---

Sparse Table vs Segment Tree

Feature	Sparse Table	Segment Tree
Build time	O(n log n)	O(n)
Query time	O(1) for idempotent ops	O(log n)
Update	Not supported	O(log n)
Space	O(n log n)	O(n)
Implementation	Simpler	More complex
Best for	Static arrays, many queries	Dynamic arrays, updates needed

Rule of thumb:

• If the array never changes and you need many queries: use a sparse table.
• If you need updates: use a segment tree.

---

Non-Idempotent Operations: Range Sum with Sparse Table

While you cannot get O(1) range sum with the overlap trick, you can still use the sparse table structure to decompose any range into O(log n) non-overlapping power-of-2 ranges:

def build_sparse_table_sum(arr):
    """Sparse table storing range sums (non-idempotent)."""
    n = len(arr)
    LOG = int(math.log2(n)) + 1 if n > 0 else 1
    
    st = [[0] * n for _ in range(LOG)]
    for i in range(n):
        st[0][i] = arr[i]
    
    for k in range(1, LOG):
        for i in range(n - (1 << k) + 1):
            st[k][i] = st[k - 1][i] + st[k - 1][i + (1 << (k - 1))]
    
    return st

def query_sum(st, l, r):
    """Range sum using non-overlapping decomposition. O(log n)."""
    total = 0
    length = r - l + 1
    i = l
    
    # Decompose length into powers of 2 (greedy, largest first)
    k = length.bit_length() - 1
    while k >= 0:
        if (1 << k) <= r - i + 1:
            total += st[k][i]
            i += (1 << k)
        k -= 1
    
    return total


arr = [3, 1, 4, 1, 5, 9, 2, 6]
st = build_sparse_table_sum(arr)
print(f"sum(1, 6) = {query_sum(st, 1, 6)}")  # 1+4+1+5+9+2 = 22
print(f"sum(0, 7) = {query_sum(st, 0, 7)}")  # 31

However, for range sums on static arrays, prefix sums are simpler and give O(1) queries with only O(n) space. Use prefix sums for sum; use sparse tables for min/max/gcd.

---

2D Sparse Table

You can extend sparse tables to 2D for answering range min/max queries on a matrix:

def build_2d_sparse_table(matrix):
    """Build 2D sparse table for sub-rectangle min queries."""
    rows, cols = len(matrix), len(matrix[0])
    LOG_R = int(math.log2(rows)) + 1
    LOG_C = int(math.log2(cols)) + 1
    
    # st[kr][kc][i][j] = min in sub-rectangle
    # from (i,j) to (i+2^kr-1, j+2^kc-1)
    st = [[[[0]*cols for _ in range(rows)] 
           for _ in range(LOG_C)] for _ in range(LOG_R)]
    
    # Base: kr=0, kc=0
    for i in range(rows):
        for j in range(cols):
            st[0][0][i][j] = matrix[i][j]
    
    # Fill kc dimension first (for kr=0)
    for kc in range(1, LOG_C):
        for i in range(rows):
            for j in range(cols - (1 << kc) + 1):
                st[0][kc][i][j] = min(
                    st[0][kc-1][i][j],
                    st[0][kc-1][i][j + (1 << (kc-1))]
                )
    
    # Fill kr dimension
    for kr in range(1, LOG_R):
        for kc in range(LOG_C):
            for i in range(rows - (1 << kr) + 1):
                for j in range(cols - (1 << kc) + 1):
                    st[kr][kc][i][j] = min(
                        st[kr-1][kc][i][j],
                        st[kr-1][kc][i + (1 << (kr-1))][j]
                    )
    
    return st

# Query minimum in sub-rectangle (r1,c1) to (r2,c2) in O(1)

---

Complete Reusable Class

import math

class SparseTable:
    """Sparse table for static range minimum queries in O(1)."""
    
    def __init__(self, arr, func=min):
        self.n = len(arr)
        self.func = func
        self.LOG = max(1, int(math.log2(self.n)) + 1) if self.n else 1
        
        # Precompute log table
        self.log_table = [0] * (self.n + 1)
        for i in range(2, self.n + 1):
            self.log_table[i] = self.log_table[i // 2] + 1
        
        # Build sparse table
        self.st = [[0] * self.n for _ in range(self.LOG)]
        for i in range(self.n):
            self.st[0][i] = arr[i]
        
        for k in range(1, self.LOG):
            for i in range(self.n - (1 << k) + 1):
                self.st[k][i] = self.func(
                    self.st[k-1][i],
                    self.st[k-1][i + (1 << (k-1))]
                )
    
    def query(self, l, r):
        """Return func(arr[l..r]) in O(1). Only correct for idempotent func."""
        if l == r:
            return self.st[0][l]
        length = r - l + 1
        k = self.log_table[length]
        return self.func(self.st[k][l], self.st[k][r - (1 << k) + 1])


# Usage
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
rmq = SparseTable(arr, min)
rmxq = SparseTable(arr, max)

print(rmq.query(0, 10))   # 1
print(rmxq.query(0, 10))  # 9
print(rmq.query(4, 8))    # 2
print(rmxq.query(4, 8))   # 9

---

Practice Problems

1. Range Minimum Query (SPOJ RMQSQ): Direct application of sparse table.
2. Range GCD Query: Build a sparse table with math.gcd as the combining function.
3. Static Range Min with Index: Return the index of the minimum, not the value. Useful as a subroutine in Cartesian tree and LCA.
4. Number of Minimums in Range: Extend the sparse table to store (min_value, count) pairs.
5. Longest Common Extension (LCE): Given a string, answer “how long is the longest common prefix of suffixes starting at i and j?” Use suffix array + LCP array + sparse table.

---

Key Takeaways

• Sparse tables give O(1) range queries for idempotent operations on static arrays.
• Build time and space are both O(n log n), which is very efficient for up to millions of elements.
• The core trick is the overlap technique: cover any range with two power-of-2 sub-ranges.
• For problems needing updates, reach for a segment tree instead.
• Sparse tables are a fundamental building block in competitive programming — they appear in LCA algorithms, suffix arrays, and Cartesian trees.