中国外协加工网官网志鸿优化网官网

 st算法（sparse_tabel）可以在O(N log N)的预处理后实现O(1)的查询效率。

rmq：Range Maximum (Minimum) Query的缩写，顾名思义是用来求某个区间内的最大值或最小值，通常用在需要多次询问一些区间的最值得问题中。

#include<bits/stdc++.h>
using namespace std;
int n,d[200005],b,a,m,f[200001][18];
int main() {scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&f[i][0]);}for(int j=1;j<=int(log(n)/log(2));j++)for(int i=1;i+(1<<j)-1<=n;i++)f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);scanf("%d",&m);while(m--){scanf("%d%d",&a,&b);int k=int(log(b-a+1)/log(2));printf("%d\n",max(f[a][k],f[b+1-(1<<k)][k]));}
}