Expand description
Implementation of a sparse table which is a data structure that can very quickly query a range on a static array in $O(1)$ for overlap-friendly functions (idempotent functions) using $O(n*logn)$ memory. For functions that are only associative, the query is done in $O(log(n))$.
A function $f$ is associative if $f(a, f(b, c)) = f(f(a, b), c)$. Examples include scalar and matrix addition and multiplication, and string concatenation. A function is overlap-freindly if $f(f(a, b), f(b, c)) = f(f(a, b), c)$. Examples include min, max, gcd and lcm.