（RMQ）区间最值问题——ST表

　　构建ST表相当于是一个DP的过程在【l，r】中选取两段(部分重合或首尾相接)的两段中的最大值中选取最值；

• 【算法分析】

  这里用到的是倍增法:
  用f[i][j]表示从i开始向后$2^i-1$的距离中的最大值。
  对于$f[i][0]=a[i]$由此逐步拓展到整个数据，就是一个dp的过程
  $f[i][j]=max(f[i][j-1],f[i+2^{j-1}][j-1])$
  用空间换时间，ST表构建完后，每次查询区间最值用$O{（1）}$的时间完成

• 查询方法如图：
  

板子题：vijos P1514 天才的记忆
直接上代码了

#include<bits/stdc++.h>
using namespace std;
int n;
int f[200010][20];
int main() {
    scanf("%d",&n);
    for(int i=1; i<=n; i++) {
        scanf("%d",&f[i][0]);
    }
    int m,l,r;
    int k=2;
    for(int j=1; j<=19; j++) {
        for(int i=1; i+k-1<=n; i++) {
            f[i][j]=max(f[i][j-1],f[i+k/2][j-1]);
        }
        k*=2;
    }
    scanf("%d",&m);
    for(int i=1; i<=m; i++) {
        scanf("%d%d",&l,&r);
        int t=log(r-l+1)/log(2);//换底公式
        int x=pow(2,t);
        printf("%d\n",max(f[l][t],f[r-x+1][t]));//将没有表示过的【l，r】,变为已经表示过的两端
    }
    return 0;
}