Sparse Table

O(1) RMQ with O(n log n) preprocessing for static arrays.

6 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode

Sparse Table Concept

Sparse Table precomputes answers for all intervals of length 2^k. st[i][k] = answer for range [i, i+2^k-1]. Query [L,R] splits into two overlapping intervals of length 2^k covering [L,R]. O(1) query for idempotent operations (min, max, gcd).

Gosparse-table-for-rmq-(min).go

47 linesLn 1, Col 1Go

st[i][k] = min of arr[i..i+2^k-1]. Build: O(n log n). Query: k = floor(log2(len)), answer = min(st[L][k], st[R-2^k+1][k]). Overlapping intervals OK for idempotent ops (min, max, gcd).

Building the Table

Bottom-up: st[i][0] = arr[i]. For k>0: st[i][k] = combine(st[i][k-1], st[i+2^{k-1}][k-1]). Only compute valid ranges where i+2^k-1 < n.

O(1) Queries

Length = R-L+1. k = floor(log2(length)). Two intervals: [L, L+2^k-1] and [R-2^k+1, R]. They overlap but cover [L,R] completely. Works for min, max, gcd, lcm (idempotent). NOT for sum (would double count).

Limitations

Aspect	Sparse Table	Segment Tree
Query time	O(1)	O(log n)
Update	Not supported	O(log n)
Space	O(n log n)	O(n)
Operations	Idempotent only	Any associative

Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.