[DataStructure]Sparse Table

对于不需要支持频繁更新的range query，我们很多时候可以用更有效率的数据结构来储存。比如区间和的话，如果更新不频繁，我们只需要存presum即可，然后每次查询用两个presum相减，这样可以用O(n)的空间达到O(1)的查询速度。对于其他的问题也有类似的思路，比如Range Minimum Query(RMQ)问题，虽然我们没有办法用线性空间达到常数空间的查询速度，我们可以用Sparse Table O(n * log n)的空间达到O(1)的查询速度。
对于长度为n的数组，Sparse Table的结构(log2(n) + 1) * n的一个matrix，ST[i][j]存的是从j开始的长度为2^i的区间的最小值，比如对于下图的array：

对应的Sparse Table的结构为：

因为RMQ的性质，即使我们查询两个overlapping的区间i1和i2，那么我们仍然有RMQ(i1 U i2) = min(RMQ(i1), RMQ(i2))。假设查询区间为[i, j]，k = floor(log2(j - 1 + 1))，那么我们只需要查询min(ST[k][i], ST[k][j - 2^k + 1])。代码如下：

另外，RMQ与LCA(Lowerst Common Ancester)问题有紧密的联系。如果我们需要频繁地对树中的任意两个节点进行LCA的查询，RMQ可以给我们很大的帮助，具体请参考这篇文章。