Skip to main content

Sparse Table

Learn Sparse Table (Advanced Data Structures, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

Sparse Table with Any Idempotent Operation A sparse table answers range queries in O(1) for any idempotent operation, one where combining a value with itself changes nothing: min , max , gcd , bitwise AND and OR . Write the table once with the operation passed in as a function, and the same code gives range-max or range-gcd queries. Build st[k][i] = op(st[k-1][i], st[k-1][i + 2^(k-1)]) in O(n log n); a query combines two overlapping blocks .

More lessons in Advanced Data Structures