RMQ问题

RMQ（Range Maximum/Minimum Query）问题，即区间最值问题。

一般是多次询问，对时间复杂度要求高，一般需要 $O(logn)$ 或 $O(1)$ 复杂度

ST表

p[i][j] 是以i为起点，连续 $2^j$ 个数字的最大值(是一个递推表)

	3	9	4	2	1	6	8	5
`p[i][0]`	3	9	4	2	1	6	8	5
`p[i][1]`	9	9	4	2	6	8	8	-
`p[i][2]`	9	9	6	8	8	-	-	-
`p[i][3]`	9	-	-	-	-	-	-	-

优缺点

优点：可查询，可在末尾插入删除
缺点：不能修改

实现

递推

$p(i,j)=\max(p(i,j-1),p(i+2^{j-1},j-1))$

查询

令 k = r-l+1;
int t = log2(k);
ans = max(p[l][t], p[r-(1<<t)+1][t]);

复杂度

$O(logn+q)$

代码

$\color{green}\text{点击查看代码}$

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#pragma GCC optimize (3) // O(3)
using namespace std;

int p[100010][20], lg[100010];

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()
{
	ios::sync_with_stdio(false);
	int n, m;
	n=read();m=read();
	for(int i = 1;i <= n;i++) p[i][0]=read();
	for(int j = 1;(1<<j) <= n;j++)
		for(int i = 1;i+(1<<j-1) <= n;i++)
			p[i][j] = max(p[i][j-1], p[i+(1<<j-1)][j-1]);
	lg[1] = 0;
	for(int i = 2;i <= n;i++) lg[i] = lg[i>>1] + 1;
	while(m--)
	{
		int l, r;
		l=read();r=read();
		int t = lg[r-l+1];
		printf("%d\n",max(p[l][t], p[r-(1<<t)+1][t]));
	}
	return 0;
}

技巧-快速读入

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;
}

~~背下来就好了~~