Sparse Table (Range Query)
Learn Sparse Table (Range Query) (Range Query Techniques, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
Sparse Table: O(1) Range Minimum Queries A sparse table answers range minimum (or maximum, or gcd) queries in O(1) on an array that never changes . Store st[k][i] = the minimum of the block of 2 k elements starting at i. Build from smaller blocks: st[k][i] = min(st[k-1][i], st[k-1][i + 2^(k-1)]) . Cost: O(n log n) time and memory to build. A query uses two overlapping blocks that cover the range; overlap is harmless for min.