1270. 数列区间最大值

此题有多种方法做，线段树、树状数组、ST算法。这里我就用ST写个模板

ST算法 蓝书41页

给定一个长度为N的数组A，ST算法能在O(NlogN)时间复杂度预处理后，以O(1)的时间复杂度在线回答“数列A中下标在l-r之间的数最大值是多少”的这样区间最值问题。对于这一个问题，他比线段树快

模板

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 1e5+10;

int N,M;
int arr[maxn],Log2[maxn];//原始数组，log2(x)数组
int f[maxn][20];//F[i][j]: arr[i~i+2^j-1]的最大值

void ST_init(){ //初始化所有长度为2^x的区间最大值
    for(int i = 1;i<=N;i++) Log2[i] = log(i)/log(2); //初始化log求值，之后O(1)取值
    for(int i = 1;i<=N;i++) f[i][0] = arr[i]; 
    int len = log(N)/log(2) +1;
    for(int j = 1;j<len;j++){
        for(int i = 1;i<=N-(1<<j)+1;i++){
            f[i][j] = max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }
}
int query(int l,int r){ //查询arr[l~r]区间的最值
    int k = Log2[r-l+1];
    return max(f[l][k],f[r-(1<<k)+1][k]);
}
int main(){
    cin>>N>>M;
    for(int i = 1;i<=N;i++) scanf("%d",&arr[i]);
    ST_init();
    int x,y;
    while(M--){
        scanf("%d%d",&x,&y);
        printf("%d\n",query(x,y));
    }
    return 0;
}