Sparse Tables: O(1) Range Queries on Static Arrays

                Mastery target: Level B implementation. You should be able to build a sparse table, answer a range query in O(1), explain why the trick requires an idempotent combine function, and know when a Segment Tree is the correct choice instead.
            

1. Introduction & Motivation

A Sparse Table answers range-minimum, range-maximum, or range-GCD queries over an array in $O(1)$ time, after a one-time $O(n \log n)$ preprocessing step. That is a remarkable guarantee: no matter how large the query range is, or how many queries arrive, each one costs the same small constant amount of work once the table is built.

The guarantee comes with one hard restriction: the array must be static. A Sparse Table has no supported way to change a single element after it is built without recomputing large portions of the table. If a workload needs both range queries and point or range updates, a Sparse Table is the wrong tool — that job belongs to a Segment Tree, which answers any range query in $O(\log n)$ but also supports updates in $O(\log n)$. This site's Segment Tree coverage lives in Segment Tree section of the Advanced Structures lesson; if updates are part of the workload, start there instead of forcing a Sparse Table to do a job it cannot do.

So the core tradeoff is: Sparse Table gives $O(1)$ query but zero update support (rebuild is $O(n \log n)$); Segment Tree gives $O(\log n)$ query and $O(\log n)$ update. Choose based on whether the array ever changes after the queries begin.

2. Prerequisites

This lesson assumes comfort with arrays and basic asymptotic notation, covered in Part 3: Arrays & Array ADT. It also leans on the fact that every positive integer range length has a largest power of two that fits inside it, and on fast $\lfloor \log_2 n \rfloor$ computation — both are bread-and-butter bit tricks covered in Bit Manipulation: Core Tricks and Interview Patterns. This lesson does not re-derive those bit tricks; it only reuses the result that floor(log2(x)) equals the index of the highest set bit of x, and that it can be built as a lookup table in $O(n)$.

3. Core Insight

                Core insight: Precompute, for every starting index $i$ and every power of two $2^j$, the combined answer (min, max, or GCD) over the range $[i, i + 2^j - 1]$. Because min, max, and GCD are idempotent — combining a value with itself changes nothing, so overlapping the same element twice does not corrupt the answer — any query range can be covered by just two overlapping precomputed ranges, chosen so their union is exactly the query range. That is what makes the query $O(1)$: no loop over the range, just one table lookup and one combine.
            

Contrast this with sum: $2 + 3 = 5$, but if a range is covered twice, the double-counted overlap breaks the total. That is precisely why the standard Sparse Table trick only works for idempotent operations. Section 7 below covers a variant, the Disjoint Sparse Table, that lifts this restriction by avoiding overlap entirely.

4. A Concrete Example

Worked Example

Range-minimum over an 8-element array

Take arr = [7, 2, 3, 0, 5, 10, 3, 12] (indices 0-7, $n = 8$). Build one row of the table per power of two: sparse[j][i] holds the minimum of the $2^j$ elements starting at index $i$.

j (block length $2^j$)	sparse[j][i] for valid i
0 (length 1)	[7, 2, 3, 0, 5, 10, 3, 12]
1 (length 2)	[2, 2, 0, 0, 5, 3, 3] — e.g. sparse[1][0] = min(7,2) = 2
2 (length 4)	[0, 0, 0, 0, 3] — e.g. sparse[2][0] = min(sparse[1][0], sparse[1][2]) = min(2,0) = 0
3 (length 8)	[0] — sparse[3][0] = min(sparse[2][0], sparse[2][4]) = min(0,3) = 0

Now answer query(1, 5), the minimum of [2, 3, 0, 5, 10] (length 5). The largest power of two that fits inside a length-5 range is $2^2 = 4$, so $j = 2$. Cover the range with two overlapping length-4 windows: sparse[2][1] covers indices 1-4, and sparse[2][2] covers indices 2-5. Their union is exactly indices 1-5, and they overlap at indices 2-3 — which is harmless because min is idempotent. Both entries equal 0, so the answer is min(0, 0) = 0, matching the true minimum of [2, 3, 0, 5, 10].

5. Building the Sparse Table

The build is bottom-up: row 0 is the array itself, and each later row combines two overlapping rows from one level down using the recurrence sparse[j][i] = combine(sparse[j-1][i], sparse[j-1][i + 2^(j-1)]). A log_table lookup (built once in $O(n)$) lets the query step avoid computing a logarithm at query time.

def build_sparse_table(arr):
    """
    Build a sparse table for O(1) idempotent range queries (here: minimum)
    on a static array. sparse[j][i] holds combine(arr[i .. i+2^j-1]).
    Preprocessing time and space: O(n log n).
    """
    n = len(arr)
    log_table = [0] * (n + 1)
    for i in range(2, n + 1):
        log_table[i] = log_table[i // 2] + 1

    max_log = log_table[n] + 1
    sparse = [[0] * n for _ in range(max_log)]
    sparse[0] = arr[:]

    for j in range(1, max_log):
        half = 1 << (j - 1)
        for i in range(n - (1 << j) + 1):
            sparse[j][i] = min(sparse[j - 1][i], sparse[j - 1][i + half])

    return sparse, log_table


arr = [7, 2, 3, 0, 5, 10, 3, 12]
sparse, log_table = build_sparse_table(arr)
print("sparse[0]:", sparse[0])          # sparse[0]: [7, 2, 3, 0, 5, 10, 3, 12]
print("sparse[1]:", sparse[1][:7])      # sparse[1]: [2, 2, 0, 0, 5, 3, 3]
print("sparse[2]:", sparse[2][:5])      # sparse[2]: [0, 0, 0, 0, 3]

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

pair<vector<vector<int>>, vector<int>> buildSparseTable(const vector<int>& arr) {
    int n = static_cast<int>(arr.size());
    vector<int> logTable(n + 1, 0);
    for (int i = 2; i <= n; ++i) {
        logTable[i] = logTable[i / 2] + 1;
    }

    int maxLog = logTable[n] + 1;
    vector<vector<int>> sparse(maxLog, vector<int>(n, 0));
    sparse[0] = arr;

    for (int j = 1; j < maxLog; ++j) {
        int half = 1 << (j - 1);
        for (int i = 0; i + (1 << j) <= n; ++i) {
            sparse[j][i] = min(sparse[j - 1][i], sparse[j - 1][i + half]);
        }
    }
    return {sparse, logTable};
}

int main() {
    vector<int> arr{7, 2, 3, 0, 5, 10, 3, 12};
    auto [sparse, logTable] = buildSparseTable(arr);

    for (int v : sparse[0]) cout << v << ' ';
    cout << '\n'; // 7 2 3 0 5 10 3 12
    for (int i = 0; i < 7; ++i) cout << sparse[1][i] << ' ';
    cout << '\n'; // 2 2 0 0 5 3 3
    for (int i = 0; i < 5; ++i) cout << sparse[2][i] << ' ';
    cout << '\n'; // 0 0 0 0 3
}

import java.util.Arrays;

public class SparseTableBuild {
    static int[][] sparse;
    static int[] logTable;

    static void build(int[] arr) {
        int n = arr.length;
        logTable = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            logTable[i] = logTable[i / 2] + 1;
        }

        int maxLog = logTable[n] + 1;
        sparse = new int[maxLog][n];
        sparse[0] = Arrays.copyOf(arr, n);

        for (int j = 1; j < maxLog; j++) {
            int half = 1 << (j - 1);
            for (int i = 0; i + (1 << j) <= n; i++) {
                sparse[j][i] = Math.min(sparse[j - 1][i], sparse[j - 1][i + half]);
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {7, 2, 3, 0, 5, 10, 3, 12};
        build(arr);

        System.out.println(Arrays.toString(sparse[0]));
        // [7, 2, 3, 0, 5, 10, 3, 12]
        System.out.println(Arrays.toString(Arrays.copyOfRange(sparse[1], 0, 7)));
        // [2, 2, 0, 0, 5, 3, 3]
        System.out.println(Arrays.toString(Arrays.copyOfRange(sparse[2], 0, 5)));
        // [0, 0, 0, 0, 3]
    }
}

6. Range Minimum Query (RMQ) in O(1)

To answer query(left, right) (inclusive), take length = right - left + 1, look up j = log_table[length] (the largest power of two that fits), and combine the two length-$2^j$ windows anchored at left and at right - 2^j + 1. Those two windows always cover the full range, and any overlap between them is harmless because min is idempotent.

def build_sparse_table(arr):
    n = len(arr)
    log_table = [0] * (n + 1)
    for i in range(2, n + 1):
        log_table[i] = log_table[i // 2] + 1

    max_log = log_table[n] + 1
    sparse = [[0] * n for _ in range(max_log)]
    sparse[0] = arr[:]

    for j in range(1, max_log):
        half = 1 << (j - 1)
        for i in range(n - (1 << j) + 1):
            sparse[j][i] = min(sparse[j - 1][i], sparse[j - 1][i + half])

    return sparse, log_table


def query_min(sparse, log_table, left, right):
    """Inclusive range [left, right], answered in O(1)."""
    length = right - left + 1
    j = log_table[length]
    return min(sparse[j][left], sparse[j][right - (1 << j) + 1])


arr = [7, 2, 3, 0, 5, 10, 3, 12]
sparse, log_table = build_sparse_table(arr)
print(query_min(sparse, log_table, 1, 5))  # range [2,3,0,5,10] -> 0
print(query_min(sparse, log_table, 0, 7))  # whole array       -> 0
print(query_min(sparse, log_table, 4, 6))  # range [5,10,3]    -> 3

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

pair<vector<vector<int>>, vector<int>> buildSparseTable(const vector<int>& arr) {
    int n = static_cast<int>(arr.size());
    vector<int> logTable(n + 1, 0);
    for (int i = 2; i <= n; ++i) {
        logTable[i] = logTable[i / 2] + 1;
    }

    int maxLog = logTable[n] + 1;
    vector<vector<int>> sparse(maxLog, vector<int>(n, 0));
    sparse[0] = arr;

    for (int j = 1; j < maxLog; ++j) {
        int half = 1 << (j - 1);
        for (int i = 0; i + (1 << j) <= n; ++i) {
            sparse[j][i] = min(sparse[j - 1][i], sparse[j - 1][i + half]);
        }
    }
    return {sparse, logTable};
}

int queryMin(const vector<vector<int>>& sparse, const vector<int>& logTable, int left, int right) {
    int length = right - left + 1;
    int j = logTable[length];
    return min(sparse[j][left], sparse[j][right - (1 << j) + 1]);
}

int main() {
    vector<int> arr{7, 2, 3, 0, 5, 10, 3, 12};
    auto [sparse, logTable] = buildSparseTable(arr);

    cout << queryMin(sparse, logTable, 1, 5) << '\n'; // 0
    cout << queryMin(sparse, logTable, 0, 7) << '\n'; // 0
    cout << queryMin(sparse, logTable, 4, 6) << '\n'; // 3
}

import java.util.Arrays;

public class SparseTableRMQ {
    static int[][] sparse;
    static int[] logTable;

    static void build(int[] arr) {
        int n = arr.length;
        logTable = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            logTable[i] = logTable[i / 2] + 1;
        }

        int maxLog = logTable[n] + 1;
        sparse = new int[maxLog][n];
        sparse[0] = Arrays.copyOf(arr, n);

        for (int j = 1; j < maxLog; j++) {
            int half = 1 << (j - 1);
            for (int i = 0; i + (1 << j) <= n; i++) {
                sparse[j][i] = Math.min(sparse[j - 1][i], sparse[j - 1][i + half]);
            }
        }
    }

    static int queryMin(int left, int right) {
        int length = right - left + 1;
        int j = logTable[length];
        return Math.min(sparse[j][left], sparse[j][right - (1 << j) + 1]);
    }

    public static void main(String[] args) {
        int[] arr = {7, 2, 3, 0, 5, 10, 3, 12};
        build(arr);

        System.out.println(queryMin(1, 5)); // 0
        System.out.println(queryMin(0, 7)); // 0
        System.out.println(queryMin(4, 6)); // 3
    }
}

GCD and Max Variants

The exact same table structure and the exact same query formula work for range-maximum and range-GCD, because max and GCD are idempotent too: max(x, x) = x and gcd(x, x) = x. Only the combine function changes — swap min for max, or for gcd, everything else stays identical. Only the GCD variant is shown below; the Max variant is the same code with min replaced by max.

from math import gcd

def build_sparse_table_gcd(arr):
    """Identical structure to the min version -- only combine() changes."""
    n = len(arr)
    log_table = [0] * (n + 1)
    for i in range(2, n + 1):
        log_table[i] = log_table[i // 2] + 1

    max_log = log_table[n] + 1
    sparse = [[0] * n for _ in range(max_log)]
    sparse[0] = arr[:]

    for j in range(1, max_log):
        half = 1 << (j - 1)
        for i in range(n - (1 << j) + 1):
            sparse[j][i] = gcd(sparse[j - 1][i], sparse[j - 1][i + half])

    return sparse, log_table


def query_gcd(sparse, log_table, left, right):
    length = right - left + 1
    j = log_table[length]
    return gcd(sparse[j][left], sparse[j][right - (1 << j) + 1])


arr = [24, 36, 18, 12, 48, 60, 30, 18]
sparse, log_table = build_sparse_table_gcd(arr)
print(query_gcd(sparse, log_table, 1, 5))  # gcd(36,18,12,48,60)    -> 6
print(query_gcd(sparse, log_table, 4, 5))  # gcd(48,60)             -> 12
print(query_gcd(sparse, log_table, 0, 7))  # gcd of the whole array -> 6

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

using namespace std;

pair<vector<vector<int>>, vector<int>> buildSparseTableGcd(const vector<int>& arr) {
    int n = static_cast<int>(arr.size());
    vector<int> logTable(n + 1, 0);
    for (int i = 2; i <= n; ++i) logTable[i] = logTable[i / 2] + 1;
    int maxLog = logTable[n] + 1;

    vector<vector<int>> sparse(maxLog, vector<int>(n, 0));
    sparse[0] = arr;

    for (int j = 1; j < maxLog; ++j) {
        int half = 1 << (j - 1);
        for (int i = 0; i + (1 << j) <= n; ++i) {
            sparse[j][i] = gcd(sparse[j - 1][i], sparse[j - 1][i + half]);
        }
    }
    return {sparse, logTable};
}

int queryGcd(const vector<vector<int>>& sparse, const vector<int>& logTable, int left, int right) {
    int length = right - left + 1;
    int j = logTable[length];
    return gcd(sparse[j][left], sparse[j][right - (1 << j) + 1]);
}

int main() {
    vector<int> arr{24, 36, 18, 12, 48, 60, 30, 18};
    auto [sparse, logTable] = buildSparseTableGcd(arr);

    cout << queryGcd(sparse, logTable, 1, 5) << '\n'; // 6
    cout << queryGcd(sparse, logTable, 4, 5) << '\n'; // 12
    cout << queryGcd(sparse, logTable, 0, 7) << '\n'; // 6
}

import java.util.Arrays;

public class SparseTableGCD {
    static int[][] sparse;
    static int[] logTable;

    static int gcd(int a, int b) {
        while (b != 0) {
            int t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

    static void build(int[] arr) {
        int n = arr.length;
        logTable = new int[n + 1];
        for (int i = 2; i <= n; i++) logTable[i] = logTable[i / 2] + 1;
        int maxLog = logTable[n] + 1;

        sparse = new int[maxLog][n];
        sparse[0] = Arrays.copyOf(arr, n);

        for (int j = 1; j < maxLog; j++) {
            int half = 1 << (j - 1);
            for (int i = 0; i + (1 << j) <= n; i++) {
                sparse[j][i] = gcd(sparse[j - 1][i], sparse[j - 1][i + half]);
            }
        }
    }

    static int query(int left, int right) {
        int length = right - left + 1;
        int j = logTable[length];
        return gcd(sparse[j][left], sparse[j][right - (1 << j) + 1]);
    }

    public static void main(String[] args) {
        int[] arr = {24, 36, 18, 12, 48, 60, 30, 18};
        build(arr);

        System.out.println(query(1, 5)); // 6
        System.out.println(query(4, 5)); // 12
        System.out.println(query(0, 7)); // 6
    }
}

7. Disjoint Sparse Table

                Core insight: The standard Sparse Table needs an idempotent combine function because its two covering windows overlap. The Disjoint Sparse Table removes that requirement by never overlapping: for each power-of-two block, it precomputes a suffix combine across the left half (ending at the midpoint) and a prefix combine across the right half (starting at the midpoint). A query then combines exactly one prefix-half value and one suffix-half value — each array element is touched by the final combine exactly once, so non-idempotent operations such as sum, and non-commutative operations such as matrix multiplication, work correctly as long as the combine function is associative.
            

The remaining puzzle is finding, in $O(1)$, which block level and which midpoint apply to a given (left, right) pair. The answer: the correct block is the smallest one where left and right fall in different halves, which happens exactly at the level of the highest bit where left and right differ — i.e. highest_bit(left XOR right). That value is looked up in a precomputed table, giving $O(1)$ queries. One subtlety is easy to get wrong: left XOR right can exceed n - 1 even though both left and right are valid indices below n, so the lookup table must be sized to 2 * n, not just n, or the lookup goes out of bounds.

def build_disjoint_sparse_table(arr, combine):
    """
    combine must be associative but need NOT be idempotent or commutative
    (sum, string concatenation, matrix multiplication all qualify).
    Preprocessing time and space: O(n log n).
    """
    n = len(arr)
    log_table = [0] * (n + 1)
    for i in range(2, n + 1):
        log_table[i] = log_table[i // 2] + 1
    max_log = log_table[n] + 1

    sparse = [arr[:] for _ in range(max_log)]  # level 0 = arr itself

    for k in range(1, max_log):
        block = 1 << (k + 1)
        half = 1 << k
        for start in range(0, n, block):
            mid = min(start + half, n)
            end = min(start + block, n)

            # suffix combine leftward across the left half [start, mid-1]
            sparse[k][mid - 1] = arr[mid - 1]
            for i in range(mid - 2, start - 1, -1):
                sparse[k][i] = combine(arr[i], sparse[k][i + 1])

            # prefix combine rightward across the right half [mid, end-1]
            if mid < end:
                sparse[k][mid] = arr[mid]
                for i in range(mid + 1, end):
                    sparse[k][i] = combine(sparse[k][i - 1], arr[i])

    # "highest differing bit" table -- sized to 2n because left ^ right
    # can exceed n - 1 even though left and right are both valid indices
    xor_bound = 2 * n
    highest_bit = [0] * xor_bound
    for x in range(2, xor_bound):
        highest_bit[x] = highest_bit[x // 2] + 1

    return sparse, highest_bit


def query_disjoint(sparse, highest_bit, arr, left, right, combine):
    if left == right:
        return arr[left]
    k = highest_bit[left ^ right]
    return combine(sparse[k][left], sparse[k][right])


arr = [3, 1, 4, 1, 5, 9, 2, 6]
add = lambda a, b: a + b
sparse, highest_bit = build_disjoint_sparse_table(arr, add)
print(query_disjoint(sparse, highest_bit, arr, 2, 5, add))  # 4+1+5+9     -> 19
print(query_disjoint(sparse, highest_bit, arr, 0, 7, add))  # whole array -> 31
print(query_disjoint(sparse, highest_bit, arr, 4, 7, add))  # 5+9+2+6     -> 22

#include <functional>
#include <iostream>
#include <vector>

using namespace std;

pair<vector<vector<long long>>, vector<int>> buildDisjointSparseTable(
        const vector<long long>& arr,
        const function<long long(long long, long long)>& combine) {
    int n = static_cast<int>(arr.size());
    vector<int> logTable(n + 1, 0);
    for (int i = 2; i <= n; ++i) logTable[i] = logTable[i / 2] + 1;
    int maxLog = logTable[n] + 1;

    vector<vector<long long>> sparse(maxLog, arr);

    for (int k = 1; k < maxLog; ++k) {
        int block = 1 << (k + 1);
        int half = 1 << k;
        for (int start = 0; start < n; start += block) {
            int mid = min(start + half, n);
            int end = min(start + block, n);

            sparse[k][mid - 1] = arr[mid - 1];
            for (int i = mid - 2; i >= start; --i) {
                sparse[k][i] = combine(arr[i], sparse[k][i + 1]);
            }
            if (mid < end) {
                sparse[k][mid] = arr[mid];
                for (int i = mid + 1; i < end; ++i) {
                    sparse[k][i] = combine(sparse[k][i - 1], arr[i]);
                }
            }
        }
    }

    int xorBound = 2 * n;
    vector<int> highestBit(xorBound, 0);
    for (int x = 2; x < xorBound; ++x) highestBit[x] = highestBit[x / 2] + 1;

    return {sparse, highestBit};
}

long long queryDisjoint(const vector<vector<long long>>& sparse, const vector<int>& highestBit,
                         const vector<long long>& arr, int left, int right,
                         const function<long long(long long, long long)>& combine) {
    if (left == right) return arr[left];
    int k = highestBit[left ^ right];
    return combine(sparse[k][left], sparse[k][right]);
}

int main() {
    vector<long long> arr{3, 1, 4, 1, 5, 9, 2, 6};
    auto combine = [](long long a, long long b) { return a + b; };
    auto [sparse, highestBit] = buildDisjointSparseTable(arr, combine);

    cout << queryDisjoint(sparse, highestBit, arr, 2, 5, combine) << '\n'; // 19
    cout << queryDisjoint(sparse, highestBit, arr, 0, 7, combine) << '\n'; // 31
    cout << queryDisjoint(sparse, highestBit, arr, 4, 7, combine) << '\n'; // 22
}

import java.util.function.LongBinaryOperator;

public class DisjointSparseTable {
    static long[][] sparse;
    static int[] highestBit;
    static long[] arr;

    static void build(long[] values, LongBinaryOperator combine) {
        arr = values;
        int n = arr.length;
        int[] logTable = new int[n + 1];
        for (int i = 2; i <= n; i++) logTable[i] = logTable[i / 2] + 1;
        int maxLog = logTable[n] + 1;

        sparse = new long[maxLog][];
        for (int k = 0; k < maxLog; k++) sparse[k] = arr.clone();

        for (int k = 1; k < maxLog; k++) {
            int block = 1 << (k + 1);
            int half = 1 << k;
            for (int start = 0; start < n; start += block) {
                int mid = Math.min(start + half, n);
                int end = Math.min(start + block, n);

                sparse[k][mid - 1] = arr[mid - 1];
                for (int i = mid - 2; i >= start; i--) {
                    sparse[k][i] = combine.applyAsLong(arr[i], sparse[k][i + 1]);
                }
                if (mid < end) {
                    sparse[k][mid] = arr[mid];
                    for (int i = mid + 1; i < end; i++) {
                        sparse[k][i] = combine.applyAsLong(sparse[k][i - 1], arr[i]);
                    }
                }
            }
        }

        int xorBound = 2 * n;
        highestBit = new int[xorBound];
        for (int x = 2; x < xorBound; x++) highestBit[x] = highestBit[x / 2] + 1;
    }

    static long query(int left, int right, LongBinaryOperator combine) {
        if (left == right) return arr[left];
        int k = highestBit[left ^ right];
        return combine.applyAsLong(sparse[k][left], sparse[k][right]);
    }

    public static void main(String[] args) {
        long[] values = {3, 1, 4, 1, 5, 9, 2, 6};
        LongBinaryOperator sum = (a, b) -> a + b;
        build(values, sum);

        System.out.println(query(2, 5, sum)); // 19
        System.out.println(query(0, 7, sum)); // 31
        System.out.println(query(4, 7, sum)); // 22
    }
}

8. Complexity Analysis

                Standard Sparse Table (idempotent combine, e.g. min/max/GCD): $O(n \log n)$ preprocessing time, $O(n \log n)$ space, $O(1)$ query time.

                Disjoint Sparse Table (any associative combine): $O(n \log n)$ preprocessing time and space, $O(1)$ query time, with a larger constant factor and the extra "highest differing bit" table.

                Updates: neither variant supports an in-place update. Changing one element can change $O(\log n)$ table entries across different rows, but those entries are not localized the way a Segment Tree's are — the practical answer is a full $O(n \log n)$ rebuild. This is exactly why Sparse Tables are reserved for static arrays: workloads with even occasional writes belong on a Segment Tree instead.

9. Applications & Alternatives

Where Sparse Tables show up

Lowest Common Ancestor (LCA): flatten a tree with an Euler tour, then answer LCA queries as a range-minimum query (by depth) over the tour in $O(1)$ after $O(n \log n)$ preprocessing — a classic reduction from a tree problem to an array problem.
Competitive programming range queries: any problem that fixes the array up front and then fires a large batch of range-min, range-max, or range-GCD queries is a strong candidate for a Sparse Table over a Segment Tree, since the query code is simpler and faster in practice.
String algorithms: range-minimum over an LCP (longest common prefix) array, used inside suffix-array-based string matching, is a textbook Sparse Table application.

10. Exercises and Mastery

Easy

By hand, build the sparse table for [5, 1, 4, 2, 8, 3, 9, 6] and answer query(2, 6) and query(0, 3) for range minimum.
For an array of length 13, list every power-of-two window length that log_table would ever select for a query, and explain why.

Medium

Implement range-GCD queries using the sparse table on [8, 12, 20, 4, 16, 28] and verify query(1, 4) by hand against a direct GCD computation.
Explain why a range-sum Sparse Table built the same way as range-minimum would silently give wrong answers, and construct a specific failing example.

Hard

Sketch how to combine a sparse table with an Euler tour of a tree to answer Lowest Common Ancestor queries in $O(1)$ after $O(n \log n)$ preprocessing. You do not need to write full code — describe: what the Euler tour records at each visit, what array the sparse table is built over (hint: node depths), and how a range-minimum query over the tour maps back to an LCA. A sketch of the update to the RMQ query signature (returning the index of the minimum, not just its value) is welcome but optional.
Prove that the Disjoint Sparse Table's query never double-counts an element: for any left < right, show that the block level $k =$ highest_bit(left XOR right) places left and right in different halves of the same block, and that the union of the two halves used is exactly $[left, right]$.

Mastery challenge: A read-heavy analytics service loads a fixed array of daily metrics once per day and then serves millions of range-minimum and range-GCD queries against it until the next load. Design the data structure choice (justify Sparse Table over Segment Tree here), state what happens if a single value needs correcting mid-day, and estimate the preprocessing and per-query cost for $n = 100{,}000$ values.

Review rhythm: tomorrow, rebuild the sparse table for a small array from memory and answer two queries by hand; next week, implement both the standard and disjoint variants without looking at this page; several weeks later, recognize when a new range-query problem calls for a Sparse Table instead of a Segment Tree or Fenwick Tree.

11. Summary Cheat Sheet

Sparse Table: $O(n \log n)$ preprocessing, $O(1)$ query, but the array must be static — no supported updates.
Works only for idempotent combine functions (min, max, GCD), because the $O(1)$ query overlaps two precomputed ranges.
Build recurrence: sparse[j][i] = combine(sparse[j-1][i], sparse[j-1][i + 2^(j-1)]).
Query: pick j = log_table[length], combine the windows at left and at right - 2^j + 1.
Disjoint Sparse Table: same $O(n \log n)$/$O(1)$ bounds, but works for any associative combine (sum, matrix multiplication) by precomputing non-overlapping prefix/suffix combines per block.
Disjoint query: find the split level via highest_bit(left XOR right), sized to 2n to avoid an out-of-bounds lookup.
Need updates too? Use a Segment Tree instead — $O(\log n)$ query and update, fully general.

Cookie Consent

Sparse Tables: O(1) Range Queries on Static Arrays

Table of Contents

1. Introduction & Motivation

2. Prerequisites

3. Core Insight

4. A Concrete Example

Range-minimum over an 8-element array

5. Building the Sparse Table

6. Range Minimum Query (RMQ) in O(1)

GCD and Max Variants

7. Disjoint Sparse Table

8. Complexity Analysis

9. Applications & Alternatives

Where Sparse Tables show up

10. Exercises and Mastery

Easy

Medium

Hard

11. Summary Cheat Sheet

Cookie Consent

Sparse Tables: O(1) Range Queries on Static Arrays

Table of Contents

1. Introduction & Motivation

2. Prerequisites

3. Core Insight

4. A Concrete Example

Range-minimum over an 8-element array

5. Building the Sparse Table

6. Range Minimum Query (RMQ) in O(1)

GCD and Max Variants

7. Disjoint Sparse Table

8. Complexity Analysis

9. Applications & Alternatives

Where Sparse Tables show up

10. Exercises and Mastery

Easy

Medium

Hard

11. Summary Cheat Sheet

Continue the DSA Curriculum

Data Structures & Algorithms Hub

Advanced Structures: Trie, Union-Find & Segment Tree

Bit Manipulation: Core Tricks and Interview Patterns