What Is a Sparse Table? The O(1) Range Minimum Query Algorithm

You have an array. A million entries. Someone asks for the minimum value between index 143,027 and index 891,442. Then again, different bounds. Ten million times. Your PM calls it "just a filter."

Scanning the array each time is O(n) per query. Ten million scans on a million-element array is 10^13 operations. Your server will not finish before the heat death of the universe.

The sparse table algorithm solves this: build once in O(n log n), then answer any range minimum query in O(1). No tree rotations, no rebalancing, no crying. Just one observation about overlapping intervals and a two-dimensional lookup table.

---

What Problem Does a Sparse Table Actually Solve?

A range query asks: given an array and two indices left and right, compute some function over arr[left..right]. Minimum, maximum, GCD, sum.

The naive approach scans [left, right] each time. For n = 10^6 and 10^7 queries, that is 10^13 operations. Your cloud bill would be notable.

A sparse table preprocesses the array so that range minimum (and other idempotent) queries answer in O(1). The trade-off: O(n log n) build time, O(n log n) space, and zero support for updates.

If the array is static and you need many fast minimum or maximum queries, a sparse table is the right tool. If the array changes, it is not. We will get to that part.

---

The Trick: Overlapping Ranges Are Fine

One observation makes O(1) queries possible. It is almost embarrassingly simple.

Say you want the minimum of arr[2..6]. You happen to know:

• The minimum of arr[2..5] is 2
• The minimum of arr[3..6] is 4

Those ranges overlap at arr[3..5]. Does the double-counting break things? No. min(min(arr[2..5]), min(arr[3..6])) still equals min(arr[2..6]).

Any element in the overlap appears in both sub-minimums. Taking the overall min counts those elements twice, but min(x, x) = x. Math is occasionally on your side.

This only works for idempotent functions: functions where applying them to the same element twice changes nothing. Minimum and maximum are idempotent. Sum is not, because sum(x, x) = 2x.

That single property, idempotency, is what makes O(1) queries achievable. The entire algorithm is really just an extended argument from min(x, x) = x.

---

Building the Table

The sparse table precomputes answers for every range whose length is a power of 2. You pay O(n log n) up front so every query is free later, like a gym membership you actually use.

table[i][j] = the minimum for the range starting at index j with length 2^i.

The recurrence:

• Base case: table[0][j] = arr[j] (ranges of length 1)
• Inductive step: table[i][j] = min(table[i-1][j], table[i-1][j + 2^(i-1)])

Each cell at level i combines two non-overlapping half-size ranges from level i-1. Left half covers [j, j + 2^(i-1) - 1], right half covers [j + 2^(i-1), j + 2^i - 1]. Together they cover [j, j + 2^i - 1].

You build from the bottom up, level by level.

A Concrete Example

arr = [1, 3, 2, 7, 5, 4, 6, 8]
       0  1  2  3  4  5  6  7

Level 0 (length = 1 = 2^0, each cell = arr[j]):

table[0] = [1, 3, 2, 7, 5, 4, 6, 8]

Level 1 (length = 2 = 2^1, each cell = min of 2 adjacent elements):

table[1][0] = min(1, 3) = 1   # covers [0, 1]
table[1][1] = min(3, 2) = 2   # covers [1, 2]
table[1][2] = min(2, 7) = 2   # covers [2, 3]
table[1][3] = min(7, 5) = 5   # covers [3, 4]
table[1][4] = min(5, 4) = 4   # covers [4, 5]
table[1][5] = min(4, 6) = 4   # covers [5, 6]
table[1][6] = min(6, 8) = 6   # covers [6, 7]

Level 2 (length = 4, each cell combines two level-1 ranges of length 2):

table[2][0] = min(table[1][0], table[1][2]) = min(1, 2) = 1   # covers [0, 3]
table[2][1] = min(table[1][1], table[1][3]) = min(2, 5) = 2   # covers [1, 4]
table[2][2] = min(table[1][2], table[1][4]) = min(2, 4) = 2   # covers [2, 5]
table[2][3] = min(table[1][3], table[1][5]) = min(5, 4) = 4   # covers [3, 6]
table[2][4] = min(table[1][4], table[1][6]) = min(4, 6) = 4   # covers [4, 7]

Level 3 (length = 8, one valid entry covering the whole array):

table[3][0] = min(table[2][0], table[2][4]) = min(1, 4) = 1   # covers [0, 7]

Total cells: roughly n * floor(log2(n)). For n = 8 that is about 24 meaningful entries.

---

Two Lookups. Done.

To answer the minimum of arr[left..right]:

1. Compute len = right - left + 1
2. Find k = floor(log2(len)). This is the largest power of 2 that fits.
3. Return min(table[k][left], table[k][right - 2^k + 1])

The two ranges are:

• [left, left + 2^k - 1]: starts at left, length 2^k
• [right - 2^k + 1, right]: ends at right, length 2^k

Together they cover [left, right]. They overlap if the range length is not exactly a power of 2. That overlap is safe. You know why.

Tracing the Query

Minimum of arr[2..6]. Length = 5, k = floor(log2(5)) = 2, so 2^k = 4.

Two ranges of length 4:

• [2, 5]: table[2][2] = 2
• [3, 6]: table[2][3] = 4

min(2, 4) = 2. The actual minimum of arr[2..6] is min(2, 7, 5, 4, 6) = 2. Correct.

Precomputing the Log Table

Computing floor(log2(x)) with a floating-point function at query time introduces overhead and precision risk. The fix: precompute an integer log2 table in O(n).

log2 = [0] * (n + 1)
for i in range(2, n + 1):
    log2[i] = log2[i >> 1] + 1

Right-shifting by 1 halves the integer and increments the bit-length count. Every query looks up k in O(1) with no floating-point involved.

---

Time and Space Complexity

Phase	Time	Space
Build	O(n log n)	O(n log n)
Query (idempotent: min, max, GCD)	O(1)	O(1) extra
Query (non-idempotent: sum)	O(log n)	O(1) extra
Update	Not supported	N/A

The O(n log n) space comes from storing floor(log2(n)) + 1 rows of n entries each. For n = 10^6, that is about 20 million integers, roughly 80 MB for 32-bit values. Feasible, but worth checking against memory limits in a contest.

The sparse table actually achieves O(1) queries. Unlike this.

For non-idempotent functions like sum, you cannot use overlapping ranges. You need to decompose [left, right] into non-overlapping power-of-2 chunks, which takes O(log n) steps. That makes a sparse table strictly worse than a Fenwick tree for sum queries. Use a Fenwick tree there instead.

---

The Part Nobody Wants to Hear: No Updates

This is where the sparse table's elegance falls apart.

Me when an interviewer asks "what if we need to update the array?"

The sparse table is read-only after construction. If a single element changes, you need to rebuild from scratch, which is O(n log n). No clever trick saves you here. The structure is fundamentally a precomputed snapshot of a frozen array.

This is not a bug or a design flaw. It is a deliberate trade: give up mutability, gain O(1) queries. If your array changes, use a segment tree. The O(log n) query cost is worth it for the flexibility.

---

Sparse Table vs Segment Tree vs Fenwick Tree

Knowing which structure to reach for is half the interview answer.

Use a sparse table when: the array is static, the operation is idempotent (min, max, GCD), and you need many queries fast. The O(1) query is the whole point.

Use a segment tree when: you need updates, or the operation is non-idempotent, or you need range assignments. The segment tree handles everything a sparse table does and more, at the cost of O(log n) per query.

Use a Fenwick tree when: you only need prefix queries (cumulative sum up to index i) with occasional point updates. Simpler code, O(log n) everything, O(n) space.

	Sparse Table	Segment Tree	Fenwick Tree
Build	O(n log n)	O(n)	O(n log n)
Query	O(1)	O(log n)	O(log n)
Update	Not supported	O(log n)	O(log n)
Space	O(n log n)	O(n)	O(n)
Idempotent only	Yes	No	No

The one-sentence rule: reach for a sparse table when the array is frozen and you need millions of range minimum or maximum queries. In every other situation, a segment tree is more flexible.

For a deeper look at when each structure wins, see Segment Tree vs Sparse Table.

---

One Structure, Every Language

Range minimum query with a precomputed log2 table for O(1) lookups. All 14 implementations follow the same structure: build the table level by level, then query using two overlapping power-of-2 ranges.

# Python 3
import math

class SparseTable:
    def __init__(self, arr: list[int]):
        n = len(arr)
        k = int(math.log2(n)) + 1 if n > 1 else 1
        self.log2 = [0] * (n + 1)
        for i in range(2, n + 1):
            self.log2[i] = self.log2[i >> 1] + 1
        self.table = [arr[:]]
        for i in range(1, k):
            prev = self.table[i - 1]
            row = prev[:]
            for j in range(n - (1 << i) + 1):
                row[j] = min(prev[j], prev[j + (1 << (i - 1))])
            self.table.append(row)

    def query(self, left: int, right: int) -> int:
        k = self.log2[right - left + 1]
        return min(self.table[k][left], self.table[k][right - (1 << k) + 1])

# Python 2
import math

class SparseTable(object):
    def __init__(self, arr):
        n = len(arr)
        k = int(math.log(n, 2)) + 1 if n > 1 else 1
        self.log2 = [0] * (n + 1)
        for i in xrange(2, n + 1):
            self.log2[i] = self.log2[i >> 1] + 1
        self.table = [arr[:]]
        for i in xrange(1, k):
            prev = self.table[i - 1]
            row = prev[:]
            for j in xrange(n - (1 << i) + 1):
                row[j] = min(prev[j], prev[j + (1 << (i - 1))])
            self.table.append(row)

    def query(self, left, right):
        k = self.log2[right - left + 1]
        return min(self.table[k][left], self.table[k][right - (1 << k) + 1])

// JavaScript
class SparseTable {
    constructor(arr) {
        const n = arr.length;
        let k = 1;
        while ((1 << k) <= n) k++;
        this.log2 = new Array(n + 1).fill(0);
        for (let i = 2; i <= n; i++) {
            this.log2[i] = this.log2[i >> 1] + 1;
        }
        this.table = [arr.slice()];
        for (let i = 1; i < k; i++) {
            const prev = this.table[i - 1];
            const row = prev.slice();
            for (let j = 0; j + (1 << i) <= n; j++) {
                row[j] = Math.min(prev[j], prev[j + (1 << (i - 1))]);
            }
            this.table.push(row);
        }
    }

    query(left, right) {
        const k = this.log2[right - left + 1];
        return Math.min(this.table[k][left], this.table[k][right - (1 << k) + 1]);
    }
}

// TypeScript
class SparseTable {
    private table: number[][];
    private log2: number[];

    constructor(arr: number[]) {
        const n = arr.length;
        let k = 1;
        while ((1 << k) <= n) k++;
        this.log2 = new Array(n + 1).fill(0);
        for (let i = 2; i <= n; i++) {
            this.log2[i] = this.log2[i >> 1] + 1;
        }
        this.table = [arr.slice()];
        for (let i = 1; i < k; i++) {
            const prev = this.table[i - 1];
            const row = prev.slice();
            for (let j = 0; j + (1 << i) <= n; j++) {
                row[j] = Math.min(prev[j], prev[j + (1 << (i - 1))]);
            }
            this.table.push(row);
        }
    }

    query(left: number, right: number): number {
        const k = this.log2[right - left + 1];
        return Math.min(
            this.table[k][left],
            this.table[k][right - (1 << k) + 1]
        );
    }
}

// Java
class SparseTable {
    private final int[][] table;
    private final int[] log2;

    public SparseTable(int[] arr) {
        int n = arr.length;
        int k = 1;
        while ((1 << k) <= n) k++;
        log2 = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            log2[i] = log2[i >> 1] + 1;
        }
        table = new int[k][n];
        System.arraycopy(arr, 0, table[0], 0, n);
        for (int i = 1; i < k; i++) {
            for (int j = 0; j + (1 << i) <= n; j++) {
                table[i][j] = Math.min(table[i-1][j], table[i-1][j + (1 << (i-1))]);
            }
        }
    }

    public int query(int left, int right) {
        int k = log2[right - left + 1];
        return Math.min(table[k][left], table[k][right - (1 << k) + 1]);
    }
}

// C++
#include <vector>
#include <algorithm>

class SparseTable {
    std::vector<std::vector<int>> table;
    std::vector<int> log2_table;

public:
    SparseTable(const std::vector<int>& arr) {
        int n = arr.size();
        int k = 1;
        while ((1 << k) <= n) k++;
        log2_table.assign(n + 1, 0);
        for (int i = 2; i <= n; i++) {
            log2_table[i] = log2_table[i >> 1] + 1;
        }
        table.assign(k, std::vector<int>(n));
        table[0] = arr;
        for (int i = 1; i < k; i++) {
            for (int j = 0; j + (1 << i) <= n; j++) {
                table[i][j] = std::min(table[i-1][j], table[i-1][j + (1 << (i-1))]);
            }
        }
    }

    int query(int left, int right) {
        int k = log2_table[right - left + 1];
        return std::min(table[k][left], table[k][right - (1 << k) + 1]);
    }
};

// C
#include <stdlib.h>

typedef struct {
    int** table;
    int*  log2;
    int   rows;
} SparseTable;

SparseTable* sparse_build(int* arr, int n) {
    SparseTable* st = malloc(sizeof(SparseTable));
    int k = 1;
    while ((1 << k) <= n) k++;
    st->rows = k;
    st->log2 = calloc(n + 1, sizeof(int));
    for (int i = 2; i <= n; i++) {
        st->log2[i] = st->log2[i >> 1] + 1;
    }
    st->table = malloc(k * sizeof(int*));
    for (int i = 0; i < k; i++) {
        st->table[i] = malloc(n * sizeof(int));
    }
    for (int j = 0; j < n; j++) st->table[0][j] = arr[j];
    for (int i = 1; i < k; i++) {
        for (int j = 0; j + (1 << i) <= n; j++) {
            int a = st->table[i-1][j];
            int b = st->table[i-1][j + (1 << (i-1))];
            st->table[i][j] = a < b ? a : b;
        }
    }
    return st;
}

int sparse_query(SparseTable* st, int left, int right) {
    int k = st->log2[right - left + 1];
    int a = st->table[k][left];
    int b = st->table[k][right - (1 << k) + 1];
    return a < b ? a : b;
}

// Go
package main

type SparseTable struct {
    table [][]int
    log2  []int
}

func NewSparseTable(arr []int) *SparseTable {
    n := len(arr)
    k := 1
    for (1 << k) <= n {
        k++
    }
    log2 := make([]int, n+1)
    for i := 2; i <= n; i++ {
        log2[i] = log2[i>>1] + 1
    }
    table := make([][]int, k)
    for i := range table {
        table[i] = make([]int, n)
    }
    copy(table[0], arr)
    for i := 1; i < k; i++ {
        for j := 0; j+(1<<i) <= n; j++ {
            a, b := table[i-1][j], table[i-1][j+(1<<(i-1))]
            if a < b {
                table[i][j] = a
            } else {
                table[i][j] = b
            }
        }
    }
    return &SparseTable{table: table, log2: log2}
}

func (st *SparseTable) Query(left, right int) int {
    k := st.log2[right-left+1]
    a, b := st.table[k][left], st.table[k][right-(1<<k)+1]
    if a < b {
        return a
    }
    return b
}

// Rust
struct SparseTable {
    table: Vec<Vec<i32>>,
    log2: Vec<usize>,
}

impl SparseTable {
    fn new(arr: &[i32]) -> Self {
        let n = arr.len();
        let mut k = 1;
        while (1 << k) <= n {
            k += 1;
        }
        let mut log2 = vec![0usize; n + 1];
        for i in 2..=n {
            log2[i] = log2[i >> 1] + 1;
        }
        let mut table = vec![arr.to_vec()];
        for i in 1..k {
            let prev = table[i - 1].clone();
            let mut row = prev.clone();
            for j in 0..n {
                if j + (1 << i) <= n {
                    row[j] = prev[j].min(prev[j + (1 << (i - 1))]);
                }
            }
            table.push(row);
        }
        SparseTable { table, log2 }
    }

    fn query(&self, left: usize, right: usize) -> i32 {
        let k = self.log2[right - left + 1];
        self.table[k][left].min(self.table[k][right - (1 << k) + 1])
    }
}

// Swift
class SparseTable {
    private let table: [[Int]]
    private let log2: [Int]

    init(_ arr: [Int]) {
        let n = arr.count
        var k = 1
        while (1 << k) <= n { k += 1 }
        var log2 = [Int](repeating: 0, count: n + 1)
        if n >= 2 {
            for i in 2...n {
                log2[i] = log2[i >> 1] + 1
            }
        }
        var built = [arr]
        for i in 1..<k {
            var row = built[i - 1]
            for j in 0..<n where j + (1 << i) <= n {
                row[j] = min(built[i-1][j], built[i-1][j + (1 << (i-1))])
            }
            built.append(row)
        }
        self.table = built
        self.log2 = log2
    }

    func query(_ left: Int, _ right: Int) -> Int {
        let k = log2[right - left + 1]
        return min(table[k][left], table[k][right - (1 << k) + 1])
    }
}

// Kotlin
class SparseTable(arr: IntArray) {
    private val table: Array<IntArray>
    private val log2: IntArray

    init {
        val n = arr.size
        var k = 1
        while ((1 shl k) <= n) k++
        log2 = IntArray(n + 1)
        for (i in 2..n) log2[i] = log2[i shr 1] + 1
        table = Array(k) { IntArray(n) }
        arr.copyInto(table[0])
        for (i in 1 until k) {
            for (j in 0..n - (1 shl i)) {
                table[i][j] = minOf(table[i-1][j], table[i-1][j + (1 shl (i-1))])
            }
        }
    }

    fun query(left: Int, right: Int): Int {
        val k = log2[right - left + 1]
        return minOf(table[k][left], table[k][right - (1 shl k) + 1])
    }
}

// C#
public class SparseTable {
    private readonly int[][] table;
    private readonly int[] log2;

    public SparseTable(int[] arr) {
        int n = arr.Length;
        int k = 1;
        while ((1 << k) <= n) k++;
        log2 = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            log2[i] = log2[i >> 1] + 1;
        }
        table = new int[k][];
        for (int i = 0; i < k; i++) table[i] = new int[n];
        arr.CopyTo(table[0], 0);
        for (int i = 1; i < k; i++) {
            for (int j = 0; j + (1 << i) <= n; j++) {
                table[i][j] = Math.Min(table[i-1][j], table[i-1][j + (1 << (i-1))]);
            }
        }
    }

    public int Query(int left, int right) {
        int k = log2[right - left + 1];
        return Math.Min(table[k][left], table[k][right - (1 << k) + 1]);
    }
}

# Ruby
class SparseTable
  def initialize(arr)
    n = arr.length
    k = 1
    k += 1 while (1 << k) <= n
    @log2 = Array.new(n + 1, 0)
    (2..n).each { |i| @log2[i] = @log2[i >> 1] + 1 }
    @table = [arr.dup]
    (1...k).each do |i|
      row = @table[i - 1].dup
      (0..n - (1 << i)).each do |j|
        row[j] = [@table[i-1][j], @table[i-1][j + (1 << (i-1))]].min
      end
      @table << row
    end
  end

  def query(left, right)
    k = @log2[right - left + 1]
    [@table[k][left], @table[k][right - (1 << k) + 1]].min
  end
end

// PHP
class SparseTable {
    private array $table;
    private array $log2;

    public function __construct(array $arr) {
        $n = count($arr);
        $k = 1;
        while ((1 << $k) <= $n) $k++;
        $this->log2 = array_fill(0, $n + 1, 0);
        for ($i = 2; $i <= $n; $i++) {
            $this->log2[$i] = $this->log2[$i >> 1] + 1;
        }
        $this->table = [$arr];
        for ($i = 1; $i < $k; $i++) {
            $row = $this->table[$i - 1];
            for ($j = 0; $j + (1 << $i) <= $n; $j++) {
                $row[$j] = min(
                    $this->table[$i-1][$j],
                    $this->table[$i-1][$j + (1 << ($i-1))]
                );
            }
            $this->table[] = $row;
        }
    }

    public function query(int $left, int $right): int {
        $k = $this->log2[$right - $left + 1];
        return min(
            $this->table[$k][$left],
            $this->table[$k][$right - (1 << $k) + 1]
        );
    }
}

---

Sparse Tables in Coding Interviews

The sparse table is a competitive programming staple that occasionally escapes into interview territory. In standard LeetCode-style interviews it appears less often than segment trees or Fenwick trees, but it shows up in a few specific places.

Where it comes up: problems asking for the minimum or maximum over a static array with many offline queries; lowest common ancestor (LCA) problems, which reduce to RMQ after an Euler tour; sliding window maximum (though a monotonic deque is simpler and more commonly expected).

What interviewers want to hear: whether you notice that the array is static and the operation is idempotent. From there, explain the build (precompute for all power-of-2 lengths), the query (two overlapping ranges), the O(n log n) build, and the O(1) query. Mention that you would switch to a segment tree if updates were needed. That last point often gets left out, and it is the most important one.

The follow-up question is predictable. "Why not always use a sparse table?" has a crisp answer: no update support, O(n log n) memory, and O(1) queries only work for idempotent operations. A segment tree is the more general default. Prepare that answer before you walk in.

The comparison table is often the crux of the follow-up. If you want to practice explaining data structure trade-offs out loud and get rubric-based feedback on whether your reasoning landed, SpaceComplexity runs voice-based mock interviews that simulate exactly that kind of follow-up question.

The Fenwick tree and segment tree are the two structures you are more likely to encounter in a typical interview. The sparse table is the right answer specifically when the array is frozen and every query is range min or max.

---

Further Reading

• Sparse table (Wikipedia)
• Range minimum query (Wikipedia)
• Idempotence (Wikipedia)
• Sparse Table (GeeksforGeeks)
• Range Minimum Query for Static Array (GeeksforGeeks)