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 .