ST表解决RMQ问题

RMQ问题：

RMQ（Range Minimum/Maximum Query），区间最值查询。对于长度为n的数列A，回答若干询问RMQ（A,i,j）(i,j<=n)，返回数列A中下标在i，j之间的最小/大值。

RMQ问题可以用线段树和ST表解决。

线段树：查询复杂度O(log n) 可以修改数列中的值

ST表： 查询复杂度 O(1) 无法修改数列中的值，是在线算法

其实ST表就是个动态规划

核心思想：倍增

对于dp[i][j] ,其含义为以i为起点，长度为2^j这个区间的最大值

转移方程就是把这个区间分成两个小区间的最大值。

https://www.luogu.com.cn/problem/P3865

https://www.cnblogs.com/zwfymqz/p/8581995.html

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

const int maxn = 1e6 + 5;

int n,m;

int dp[maxn][21];

int main() {

    scanf("%d%d",&n,&m);

    int num;

    for(int i=1;i<=n;i++)  //初始化，区间长度为1，最大值就是本身

    {

        scanf("%d",&num);

        dp[i][0]=num;

    }

    for(int j=1;(1<<j)<=n;j++) //2^j 要大于等于区间长度

        for(int i=1;i+(1<<j)-1<=n;i++) //处理i到i+(1<<j)-1这个区间

        {

            dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]); //将当前区间[i,i+2^j]拆分成[i,i+2^(j-1)] [i+2^(j-1),i+2^(j-1)+2^(j-1)].

        }                                                   //其实就是再中间切割一下 后边区间可以简写成[i+2^(j-1),i+2^j]

    int k;

    int l,r;

    while(m--)

    {

        scanf("%d%d",&l,&r);

        k=log2(r-l+1);

        printf("%d\n",max(dp[l][k],dp[r-(1<<k)+1][k]));

    }

    return 0;

}