Sparse Table: Range Query Data Structure Explained

A sparse table precomputes the answer for every range whose length is a power of two. Any query is then two overlapping blocks — O(1).

Why it matters:

When the array never changes, this beats segment trees: O(1) per query after an O(n log n) build.

The overlap insight:

min (and max, gcd) are idempotent — overlapping blocks don’t corrupt the answer. That’s what makes two blocks enough.

Core Template

class SparseTable {
    int[][] sp;   // sp[j][i] = min of range [i, i + 2^j)

    public SparseTable(int[] arr) {
        int n = arr.length;
        int levels = 32 - Integer.numberOfLeadingZeros(n);
        sp = new int[levels][n];

        sp[0] = arr.clone();
        for (int j = 1; j < levels; j++)
            for (int i = 0; i + (1 << j) <= n; i++)
                sp[j][i] = Math.min(sp[j - 1][i],
                                    sp[j - 1][i + (1 << (j - 1))]);
    }

    public int query(int l, int r) {          // inclusive
        int j = 31 - Integer.numberOfLeadingZeros(r - l + 1);
        return Math.min(sp[j][l], sp[j][r - (1 << j) + 1]);
    }
}

class SparseTable:
    def __init__(self, arr):
        self.n = len(arr)
        self.sp = [list(arr)]

        j = 1
        while (1 << j) <= self.n:
            prev, half = self.sp[-1], 1 << (j - 1)
            self.sp.append(
                [min(prev[i], prev[i + half])
                 for i in range(self.n - (1 << j) + 1)]
            )
            j += 1

    def query(self, l, r):                    # inclusive
        j = (r - l + 1).bit_length() - 1
        return min(self.sp[j][l], self.sp[j][r - (1 << j) + 1])

class SparseTable {
    vector<vector<int>> sp;

public:
    SparseTable(vector<int>& arr) {
        int n = arr.size();
        int levels = 1;
        while ((1 << levels) <= n) levels++;
        sp.assign(levels, vector<int>(n));

        sp[0] = arr;
        for (int j = 1; j < levels; j++)
            for (int i = 0; i + (1 << j) <= n; i++)
                sp[j][i] = min(sp[j - 1][i],
                               sp[j - 1][i + (1 << (j - 1))]);
    }

    int query(int l, int r) const {           // inclusive
        int j = 31 - __builtin_clz(r - l + 1);
        return min(sp[j][l], sp[j][r - (1 << j) + 1]);
    }
};

class SparseTable {
  constructor(arr) {
    this.sp = [[...arr]];

    for (let j = 1; 1 << j <= arr.length; j++) {
      const prev = this.sp[j - 1];
      const half = 1 << (j - 1);
      const row = [];
      for (let i = 0; i + (1 << j) <= arr.length; i++)
        row.push(Math.min(prev[i], prev[i + half]));
      this.sp.push(row);
    }
  }

  query(l, r) { // inclusive
    const j = 31 - Math.clz32(r - l + 1);
    return Math.min(this.sp[j][l], this.sp[j][r - (1 << j) + 1]);
  }
}

Swap min for max or gcd and nothing else changes.

Pattern: Static RMQ / LCA

Watch level 1 and level 2 get built on [5, 2, 4, 7, 1, 3], then min([0..4]) answered by merging two length-4 blocks. Press ▶ to animate.

Sparse Table Range Minimum Query

Answer range-min (or max) queries in O(1) after an O(n log n) build.

Build sp[j][k] = min over a range of length 2^j starting at k by merging two length-2^(j-1) blocks. A query picks k = floor(log2(length)) and takes the min of two overlapping length-2^k blocks covering the range. Overlap is harmless for min/max, so each query is O(1).

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        build: sp[0][k] = arr[k]
                      
                        2
                               sp[j][k] = min(sp[j-1][k], sp[j-1][k + 2^(j-1)])
                      
                        3
                        query(l, r): k = floor(log2(r - l + 1))
                      
                        4
                                     return min(sp[k][l], sp[k][r - 2^k + 1])

Classic uses:

Range minimum on a fixed array (sliding-window analytics)
LCA via Euler tour + RMQ — O(1) per query
Range gcd of static values

If data updates even once → use a segment tree instead.

Sparse table = power-of-two block table + two-block idempotent merge.

Common Mistakes

Using it for sums.

Overlapping blocks double-count elements. The two-block trick only works for idempotent operations (min/max/gcd). Sums need segment trees or prefix arrays.

Wrong log computation.

k = floor(log2(length)). Off by one here selects blocks that are too big/small. Prefer bit-length builtins over floating-point log2.

Inclusive vs exclusive bounds.

The template above uses inclusive [l..r]; block B starts at r − 2^k + 1. Mixing conventions silently shifts ranges.

Complexity

Operation	Time
Build	O(n log n)
Query	O(1)
Update	not supported
Space	O(n log n)

⚠️ Animation & Content Notice

Sparse Table

Core Template

Pattern: Static RMQ / LCA

⚠️ Animation & Content Notice

Sparse Table Range Minimum Query

Common Mistakes

Complexity

Premium Content

My Private Notes

Earn Premium with Referrals

Core Template

Pattern: Static RMQ / LCA

Sparse Table Range Minimum Query

Common Mistakes

Complexity

Premium Content

My Private Notes