目录：

RMQ 问题

ST 表

log 函数预处理

例题讲解

RMQ 问题

        RMQ（Range Minimum/Maximum Query）问题是指：对于长度为 n 的数列 A，回答若干询问 RMQ  (区间 [ l，r ] ) ，返回数列A中下标在 l , r 里的最小/大值，也就是说，RMQ 问题是指求区间最值的问题。

ST 表

        st 表和线段树常被用来解决 RMQ 问题，两个各有优缺点：st 表运行效率高，但不能修改；线段树运行效率相对较慢，但支持修改操作。

        st 表的合并复杂度为 O(1)，构建复杂度为 O(n log n)，查询复杂度是 O(1)。

        st 表的核心要领在于倍增和 DP ，设区间左端点为 l ，长度为  ，求其区间最值。st 表的做法就是 DP 预处理出所有的区间最值，询问时直接输出。

                                        ​​​​​​​        ​​​​​​​        ​​​​​​​        

        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        

        其中 merge 为最值函数，最大值用 max ，最小值用 min 。

        易看出，只有当区间中重叠的部分对最终答案无影响时，才能使用 st 表。

        一点小优化，可以预处理一个 log[] 数组，以减小 cmath 库中  函数的运算时间。

log 函数预处理

        没什么可讲的，只是注意初始时，log [0] = -1 。因为 log 和 某个函数重了，所以用 Log 来表示。

for(register int i=1;i<=n;i++) 
    Log[i]=Log[i>>1]+1;

例题讲解

P3865 【模板】ST 表https://www.luogu.com.cn/problem/P3865https://www.luogu.com.cn/problem/P3865        st 表的板子题目，也可以用线段树，不过需要卡常。

st 表做法：

        套用 st 表的板子，轻松 AC ，时间复杂度为 O(n log n + m) 。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
using namespace std;
inline int read()
{
    int num=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {num=(num<<1)+(num<<3)+ch-'0';ch=getchar();}
    return num*w;
}
int n,m,l,r,k;
int a[100001];
int f[100001][30];
int Log[100001];
inline void st()
{
	Log[0]=-1;
	for(register int i=1;i<=n;i++) Log[i]=Log[i>>1]+1;
	for(register int i=1;i<=n;i++) f[i][0]=a[i];
	for(register int j=1;j<=Log[n];j++)
		for(register int i=1;i+(1<<j)-1<=n;i++)
			f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
	return;
}
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	n=read(),m=read();
	for(register int i=1;i<=n;i++) a[i]=read();
	st();
	while(m--) 
	{
		l=read(),r=read();
		k=Log[r-l+1];
		printf("%d\n",max(f[l][k],f[r-(1<<k)+1][k]));}
	//fclose(stdin);
	//fclose(stdout);		
	return 0;
}

线段树做法：

        需要使用卡常大法！！！

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<string>
#include<cstring>
#include<stack>
using namespace std;
inline int read()
{
	int num=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {num=(num<<1)+(num<<3)+ch-'0';ch=getchar();}
	return num*w;
}
struct node 
{
	int l;
	int r;
	int maxx;
}tree[1000001];
int n,m,x,y;
int a[1000001];
inline void add(int k)
{
	tree[k].maxx=max(tree[k<<1].maxx,tree[k<<1|1].maxx);
}
inline void build(int k,int l,int r)
{
	tree[k].l=l,tree[k].r=r;
	if(l==r) {tree[k].maxx=a[l];return;}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	add(k);
	return;
}
inline int find(int k,int l,int r,int x,int y)
{
	if(x<=l&&r<=y) return tree[k].maxx;
	int mid=(l+r)>>1;
	int res=-0x3f3f3f;
	if(x<=mid) res=max(res,find(k<<1,l,mid,x,y));
	if(y>mid) res=max(res,find(k<<1|1,mid+1,r,x,y)); 
	return res;
}
int main()
{
	n=read(),m=read();
	for(register int i=1;i<=n;i++) a[i]=read();
	build(1,1,n);
	while(m--)
	{
		x=read(),y=read();
		printf("%d\n",find(1,1,n,x,y));
	}
	return 0;
}

​​​​​​​