ST表 模板

ST表

一种利用dp求解区间最值的倍增算法
可以进行区间最值查询, 预处理复杂度$O(nlogn)$, 查询时间复杂度$O(1)$

题目描述

给定一个长度为 $N$ 的数列，和 $M$次询问，求出每一次询问的区间内数字的最大值。

$f[i][j]$表示$i$到$i+2j−1$这段区间的最大值。

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+10;
int st[N][21]; // 2^n大于e5, 100足够了
int n,m;

inline int searh(int l,int r){
    int t=log2(r-l+1);
    return max(st[l][t],st[r-(1<<t)+1][t]);
}

int main(){
    scanf("%d%d",&n,&m);
    for(register int i=1;i<=n;i++)
        scanf("%d",&st[i][0]);
    for(register int j=1;j<=21;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
            st[i][j] = max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
    int x,y;
    while(m--){
        scanf("%d%d",&x,&y);
        printf("%d\n",searh(x,y));
    }
    return 0;
}

感想

本题的输入输出太大，用cin，cout直接TLE，改scanf，printf解决