更优视觉请见浅谈RMQ
RMQ，即Range Minimum/Maximum Query，区间最大最小问题，通常采取ST表求解，下面将结合例题讲解
例题
题目描述
给定一个长度为(N)的数列，和(M)次询问，求出每一次询问的区间内数字的最大值。
(1 leq N leq {10}^5, 1 leq M leq 2 imes {10}^6, a_i in [0, {10}^9], 1 leq l_i leq r_i leq N)
这种问题最简单的想法就是对于每个区间遍历一次，求出最大值
但这样的时间复杂度是(O(NM))的，明显会超时
那么我们可以考虑一下怎么优化
发现如果我们可以预处理出每个区间的最大值是不是就可以了
这时候就可以使用ST表
ST表
ST表基于倍增的思想，可以做到在(O(nlogn))的时间内预处理出从每个点往后(2^x)的区间内的最大值
设(f[i][j])表示从(i)往后(2^j-1)的区间内的最大值，那么转移方程为
(f[i][j]=maxegin{cases}f[i][j-1]\f[i+2^{j-1}][j-1] end{cases})
首先这个区间可以拆成连个区间，前一半和后一半，然后再比较这两个区间内的最大值就可以了
同时由这个转移方程哦我们可以看出要求出(f[i][j])，那么(f[i][j-1])必须要先求出来，所以循环的时候要先循环(j)再循环(i)
那么现在处理出每个区间的最大值，我们就需要在(O(1))的时间内求出任意区间的值
现在有一个区间([l,r])，我们先求出(x=log_2(r-l+1))。那么这时候整个区间就可以分成([l,l+2^x-1])和([r-2^x+1,r])两个区间，然后就可以根据已经预处理好的(f)数组在(O(1))的时间里查询
那么可能就有同学会问了，如果说分成的两个区间不能覆盖原区间呢？
也就是说，会不会有(r-2^x+1>l+2^x-1)的情况
假设(r-2^x+1>l+2^x-1)
那么(r-l+2>2 imes 2^x)
又因为(x=log_2(r-l+1))，也就是(2^x=r-l+1)
所以(r-l+2>2*(r-l+1))
即(r-l>2*(r-l))
因为(r-l>0)
所以(r-l>2*(r-l))不成立
即(r-2^x+1>l+2^x-1)不成立
就说明(r-2^x+1le l+2^x-1)
那么分成的两个区间就一定可以覆盖原来的区间，我们可以放心的这么拆区间啦
例题Code
#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
int n,m,l,r,x,f[100005][17];
int read()
{
int res=0,fh=1;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') fh=-1;ch=getchar();}
while (ch>='0'&&ch<='9') res=res*10+(ch-'0'),ch=getchar();
return res*fh;
}
int main()
{
n=read();m=read();
for (int i=1;i<=n;++i)//f[i][0]就是从i到i+2^0-1内的最大值，就是a[i]
f[i][0]=read();
for (int j=1;j<=log2(n);++j)
for (int i=1;i<=n+1-(1<<j);++i)
f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);//预处理
for (int i=1;i<=m;++i)
{
l=read();r=read();
x=log2(r-l+1);
printf("%d
",max(f[l][x],f[r+1-(1<<x)][x]));//O(1)求答案
}
return 0;
}