RMQ

如题：作用是询问区间最大最小值问题

步骤：

1.定义

a[i]表示数列的数

lg数组是一个辅助数组，用于快速计算查询区间的长度对应的k值。具体来说，lg[i]表示以2为底，i的对数。在C++中，可以使用lg2函数来计算以2为底的对数

f[i][j]表示从a[i]到a[i+2^i-1]这个范围内的最大值，也就是以a[i]为起点连续2^i个数的最大值

2.初始化

初始化lg[0] = -1，这样才能使lg[1] = 0

预处理出长度为1-n的lg值

计算f[i][j]

void rmq()
{
    lg[0] = -1;
    for(int i=1;i<=n;i++)
        f[i][0] = a[i],lg[i] = lg[i>>1]+1; //预处理出长度为1-n的lg值
    for(int j=1;j<=lgn;j++) //计算f[i][j]
        for(int i=1;i+(1<<j)-1<=n;i++) //区间边界不超过n
            f[i][j] = max(f[i][j-1],f[i+(1<<j-1)][j-1]);
}

3.询问

对于求区间[x,y]的最大值，直接按照下面的表达式计算即可

s = lg[y-x+1]

ans = max(f[x][s],f[y-(1<<s)+1][s])

     int s = lg[y-x+1]; //求lg2(y-x+1)下取整的值 
     printf("%d\n",max(f[x][s],f[y-(1<<s)+1][s]));

6570: 数列区间最大值

描述

输入一串数字，给你 M 个询问，每次询问就给你两个数字 X,Y，要求你说出 X 到 Y 这段区间内的最大数。

输入

第一行两个整数 N,M 表示数字的个数和要询问的次数；

接下来一行为 N 个数；

接下来 M 行，每行都有两个整数 X,Y。

对于全部数据，1≤N≤10⁵,1≤M≤10⁶,1≤X≤Y≤N。数字不超过 C/C++ 的 int 范围。

输出

输出共 M 行，每行输出一个数。

样例输入

10 2
3 2 4 5 6 8 1 2 9 7
1 4
3 8

样例输出

5
8

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10,inf = 0x3f3f3f3f,lgn = 20;
int lg[N],f[N][lgn+5],a[N];
int n,m,x,y;
void rmq()
{
    lg[0] = -1;
    for(int i=1;i<=n;i++)
        f[i][0] = a[i],lg[i] = lg[i>>1]+1; //预处理出长度为1-n的lg值
    for(int j=1;j<=lgn;j++) //计算f[i][j]
        for(int i=1;i+(1<<j)-1<=n;i++) //区间边界不超过n
            f[i][j] = max(f[i][j-1],f[i+(1<<j-1)][j-1]);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    rmq(); //预处理rmq 
    while(m--)
    {
        scanf("%d%d",&x,&y);
        int s = lg[y-x+1]; //求lg2(y-x+1)下取整的值 
        printf("%d\n",max(f[x][s],f[y-(1<<s)+1][s]));
    } 
     return 0;
}