ST表
导入
RMQ（Range Mininum/Maxnum Query）：即区间最值查询。对于长度为(N)的数组(A)，有若干次询问(RMQ(i,j))，回答下标区间([i,j])内的最大/最小值。
ST表可以很好地解决此类问题，预处理复杂度(O(NlogN))，查询(O(1))。
预处理
设(A[i])是要求区间最值的数组，(F[i][j])表示从第(i)个数起连续(2^j)个数中的最大值。
显然初始化时要令(F[i][0]=A[i])。
除初始状态外，(F[i][j])表示的区间必有偶数个数字。将其均分为两段，一段为(F[i][j-1])，另一段为(F[i+2^{j-1}][j-1])。注意两段均包含(2^{j-1})个数字。
则状态转移方程（以求区间最大值为例）
[F[i][j]=max(F[i][j-1],F[i+2^{j-1}][j-1])
]
从而预处理出数组中所有长度为(2^j)((j=0,1...log_2N（向下取整）))的区间上的最值。
//其实就是区间DP
for (int j = 1; j <= lg[n]; j++) {
//枚举区间长度
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
//枚举左端点i，区间长度为1<<j，则右端点就是i+(1<<j)-1，显然右端点不能超过n
f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
}
查询
假设需要查询的区间为([l,r])，注意到区间重复是不影响结果的。如查询([1,5])，则查询(F[1][2])（区间([1,4])的最大值）和(F[2][2])（区间([2,5])的最大值）即可。
换句话说，我们需要找到一个合适的(k)，使得从(l)起往右(2^k)个数不会超过(r)，且从(r)起往左(2^k)个数不会超过(l)，这样就可以从(F[l][k])和(F[r-2^k+1][k])中得到区间([l,r])的最值。
这个(k)显然和区间长度有关。查询区间的长度为(r-l+1)，取(k=log_2(l-r+1))（向下取整），则这个(k)就是我们要找的合适的(k)。
则有：
[RMQ(l,r)=max(F[l][k],F[r-2^k+1][k])
]
for (int i = 1; i <= m; i++) {
int l, r; cin >> l >> r;
int k = lg[r - l + 1];
cout << max(f[l][k], f[r - (1 << k) + 1][k]);
}
另外(log_2i)的值同样可以预处理得出。（和倍增LCA的lg预处理不一样，不要混淆！这里是真正的(log_2i)，那边是(log_2i+1)）
lg[0] = -1;
for (int i = 1; i <= n; i++) {
lg[i] = lg[i / 2] + 1;
}
完整代码
const int maxn = 1e5 + 100;
int a[maxn], f[maxn][22], lg[maxn];
int main() {
lg[0] = -1;
n = read(); m = read();
//洛谷模板题时间卡得很紧，全部用快读
for (int i = 1; i <= n; i++) {
a[i] = read();
lg[i] = lg[i / 2] + 1;
}
for (int i = 1; i <= n; i++) {
f[i][0] = a[i];
}
for (int j = 1; j <= lg[n]; j++) {
//枚举区间长度
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
//枚举左端点i，区间长度为1<<j，则右端点就是i+(1<<j)-1，显然右端点不能超过n
f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
}
for (int i = 1; i <= m; i++) {
int l, r;
l = read(); r = read();
int k = lg[r - l + 1];
printf("%d
", max(f[l][k], f[r - (1 << k) + 1][k]));
}
return 0;
}