RMQ
RMQ (Range Minimum Query)，指求区间最小值。普通的求区间最小值的方法是暴力。
对于一个数列：
\]
对于一个给定的区间\([l, ~r], ~1≤ l ≤r ≤ n\)，\(\min \{A_l, A_{l + 1}, \cdots,A_r\}\)的计算就是RMQ问题。
此解法为\(\text{Sparse-Table}\)解法，简称\(ST\)表。
预处理：预处理为对数据进行\(n\log n\)的时间复杂度的处理
令\(d(i, j )\)为\(A_i, A_{i + 1}, \cdots, A_{i + 2^j - 1}\)的最小值，即\(d(i, j)\)的区间长度为\(2^j\)，这里用到的是倍增的思想。
则\(d(i, j - 1)\)为\(A_i, A_{1 + 1}, \cdots, A_{i + 2^{j - 1}-1}\)的最小值，区间长度为\(2^{j-1}\)
同样地\(d(i + 2^{j - 1}, j - 1)\)表示的是\(A_{i + 2^{j-1}}, A_{i + 2^{j - 1} + 1}, \cdots, A_{i + 2^{j-1} + 2 ^{j - 1} - 1 = i + 2^j - 1}\)。
所以显而易见：\(d(i, j)\)可以表示为：
\[d(i,j) = \min \{d(i, j - 1), ~d(i + 2^{j - 1}, j - 1)\}
\]查询：
令\(k\)为满足\(2 ^ k ≤ R - L+ 1\)的最大整数，即\(k = \max\{t~|~2^t ≤ R - L + 1, t \in \mathbb Z^+\}\)。
同样地：\(k =[ \log_2 (R-L + 1)]\)，所以：\(\operatorname{Query}(L,R) = \min \{d(L,k),~d(R - 2^k + 1, k\}\)
查询的时间复杂度为\(O(1)\)。
注意：由于每次\(pow(2,x)\)非常浪费时间，在计算机内部二进制可以表示为：\(1 << x\)。
代码：
namespace RMQ {
void init(int n) {
for (int i = 1; i <= n; i ++) d[i][0] = a[i];
for (int j = 1; (1 << j) <= n; j ++) {
for (int i = 1; i + (1 << j) - 1 <= n; i ++) {
d[i][j] = min(d[i][j - 1], d[i + (1 << (j - 1))][j - 1]);
}
int query(int l, int r) {
int k = log2(r - l + 1);
return min(d[l][k], d[r - (1 << k) + 1][k]);
}
}
注意：init中的循环顺序不能颠倒，显而易见，\(j\)的值，即区间的长度，必须由小到大。