Medium · Sparse Table
Understand → Visualise → Practice.
Return the greatest common divisor of every inclusive immutable-array range.
GCD is idempotent: gcd(x, x) = x, so two overlapping power-of-two blocks covering [l, r] give the exact answer in O(1).
table[0] is the array; table[j][i] = gcd(table[j−1][i], table[j−1][i + 2ʲ⁻¹]).
For a range of length len, let j = ⌊log₂ len⌋.
Return gcd(table[j][l], table[j][r − 2ʲ + 1]); the overlap does no harm.
O(n log n) preprocessing and O(1) per query, with O(n log n) space.
Overlapping blocks only work for idempotent operations like gcd, min and max, never for sum.
Read the full guide first: Fenwick Trees and Segment Trees.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.