ST 稀疏表的实现
ST（Sparse Table，稀疏表）算法是求解 RMQ 问题的经典在线算法，以 O (nlogn) 时间预处理，然后在 O (1) 时间内回答每个查询。ST 算法本质上是动态规划算法，定义了一个二维辅助数组 st [n][n]，st [i][j] 表示原数组 a 中从下标 i 开始，长度为 2^j 的子数组中的最值（以最小值为例）。
预处理：要求解 st [i][j] 时，即求下标 i 开始，长度为 2^j 的子数组的最小值时，可以把这段子数组再划分成两半，每半的长度为 2^(j-1)，于是前一半的最小值为 st [i][j-1]，后一半的最小值为 st [i+2^(j-1)][j-1]，于是动态规划的转移方程为：st [i][j] = min (st [i][j-1], st [i+2^(j-1)][j-1]) 长度为 2^j 的情况只和长度为 2^(j-1) 的情况有关，只需要初始化长度为 2^0=1 的情况即可。而长度为 1 时的最小值是显然的（为其本身）。
查询： 现在问题是，st 数组可以怎样加速我们的查询呢？这也是算法的巧妙之处，假设求下标在 u 到 v 之间的最小值。先求 u 和 v 之间的长度 len=v-u+1，然后求 k=ln (len)，则 u 到 v 之间的子数组可以分为两部分： 以 u 开始，长度为 2^k 的一段 以 v 结束，长度为 2^k 的一段（可以计算得到起始位置为 v-2^k+1）注意，一般情况下这两段是重叠的，但是这两段的最小值中较小的一个仍然是 u 到 v 的最小值。于是 RMQ (u,v) = min (st [u][k], st [v-2^k+1][k])