P3865 【模板】ST 表

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1e5 + 7;
int n, m;
int st[N][20];//N的2为底的log最大为16
int lg[N];//求每个j的2为底的log值向下取整，可以用(int)(log(j)/log(2))来代替
int l, r, p;
inline int read()//快读
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch>'9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}
int main() {

    n=read(),m= read();
    for (int i = 1; i <= n; i++)st[i][0] = read();//初始化最小区间1的每个值
    lg[1] = 0;
    for (int i = 2; i <= n; i++)lg[i] = lg[i >> 1] + 1;//初始化每个j的2为底的log值向下取整

    for (int j = 1; j <= lg[n]; j++) {
        for (int i = 1; i <= n - (1 << j) + 1; i++) {
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }
    //dp思想，由两个小的区间求出更大的区间最大值，所以要从j开始遍历。
    //转移方程：st[i][j]=max(st[i][j-1],st[i+pow(2,j-1)][j-1]),平方公式可以用位运算表示，1 << (j-1);
    while (m--) {
        l = read(), r = read();
        p = lg[r - l + 1];
        printf("%d\n", max(st[l][p], st[r - (1 << p) + 1][p]));
        //为什么左端点是r-(1<<p)+1,即r-pow(2,r)+1,因为我们需要第一个点x，满足x+pow(2,r)-1=r,所以x=r-pow(2,k)+1,对应转移方程
    }
    //不能直接输出st[l][p]。
    //求区间[l,r]的最值，也可以转化为求st表中前部分和后部分的最值。
    return 0;
}