范围最小值问题（Range Minimum Query, RMQ）。给定一个数组A[1, n]，求A[i，j]的最小值。 这里假定数组A的元素不会变化（如果变化，用线段树）。
Sparse-Table（ST）算法
预处理时间O(nlogn)，查询O(1)。
令 表示从开始，长度为的一段元素中的最小值。 利用动态规划，状态转移方程是：。
注意。故d数组的元素个数不超过。每一项可在常数时间计算完，故总时间为。
以下为预处理代码，注意嵌套的for循环的顺序，j在外层，i在内层。
void RMQ_init(vector<int> A) {
int n = A.size();
for (int i = 0; i < n; i++) d[i][0] = A[i];
for (int j = 0; (1<<j) <= n; j++)
for (int i = 0; i + (1 << j) - 1 < n; i++)
d[i][j] = min(d[i][j - 1], d[i + (1<<(j - 1))][j - 1]);
}
查询代码如下。令k为满足的最大整数。则两个待比较的区间范围分别是以i开始和以j结尾的长度的区间。即，两个区间有重复也没关系，需要确保能够覆盖[i，j]整个区间。如果是累加之类的问题，则注意不能重复。
int RMQ(int i, int j) {
int k = 0;
while (i + (1 << (k + 1)) - 1 <= j) k++;
return min(d[i][k], d[j - (1 << k) + 1][k]);
}
参考：
- http://blog.csdn.net/niushuai666/article/details/6624672/
- 《算法竞赛入门经典-训练指南》
