Theorem

Sparse table overlap-query correctness theorem

If the operation is idempotent, then two overlapping blocks of length 2^k chosen with k = floor(log2(length)) return the correct answer on the static range [left, right].