Module Sparse table

Sparse table

**Frequency: 2/10** Apart from its use in the Lowest Common Ancestor (LCA) problem, sparse tables are primarily employed for the following purposes: - It can be used as a replacement for a Segment Tree in problems where there are no updates, resulting in improved time complexity. - It is also utilized for binary lifting operations. It's worth noting that the time complexity of `log2()` function in C++ is logarithmic, so pre-calculating the logarithm values is a smart move to optimize performance.

Resources

- [CP Algorithms: Sparse Table](https://cp-algorithms.com/data_structures/sparse-table.html#range-minimum-queries-rmq) - [USACO: Binary Jumping](https://usaco.guide/plat/binary-jump?lang=cpp)

Problems

Minimum query 111 / 122 1300
Graph query 72 / 81 1500
GCD 74 / 80 1700
Leaky roof 35 / 47 1800