倍增算法之：ST表 与 RMQ

讲解：

倍增思想，就是每次在原基础上往前“跳” \(2^n\) 步
RMQ参考 https://blog.csdn.net/qq_31759205/article/details/75008659
RMQ 问题，即区间最值查询问题，通常的做法（我会的做法）有 暴力、线段树……
这里介绍一种比较高效的算法：ST表。
ST 表可以做到 \(O(nlogn)\) 的预处理和 \(O(1)\) 的查询，是一种在码量和复杂度上都非常优秀的方法。

预处理：

• 设 \(a\) 是要求区间最值的序列，\(f_{i,j}\) 表示从第 \(i\) 个数起连续 \(2^j\) 个数中的最大值。（DP状态）

for example：
a={3,2,4,5,6,8,1,2,9,7};
\(f_{1,0}\)表示从第一个数开始，长度为 \(2^0=1\) 的最大值，其实就是这个数 \(3\)。

• 很容易看出 \(f_{i,0} = a_i\)。（DP的初始值）
• 我们把 \(f_{i,j}\) 平均分成 \(2\) 段（因为 \(i\) 到 \(i+j-1\) 之间一定有偶数个数），从 \(i\) 到 \(i+2^(j-1) -1\) 为一段，\(i+2^(j-1)\) 到 \(i+2^j-1\) 为一段，每段长度都是 \(2^(j-1)\)。我们可以得出状态转移方程：\(f_{i,j}=max\{f_{i,j-1},f_{i+2^(j-1),j-1}\}\)。

查询：

• 假如我们要查询的区间为 \(i\) 到 \(j\)，那么我们需要找到覆盖整个闭区间（左边界取 \(i\)，右边界取 \(j\)）的最小幂（可以重叠）

比如我们要查询 1，2，3，4，5 中的最大值，我们可以先查询 1，2，3，4 中的最大值，再查询 2，3，4，5 中的最大值，最后取 max

• 因为这个区间长度为 \(j-i+1\)，所以我们就可以取 \(k=log2（j-i+1）\) 则有 \(RMQ（i，j）= max\{f_{i,k},f_{j-2^k+1,k}\}\).

洛谷模板题传送门：ST 表 && RMQ 问题

代码：

#include<bits/stdc++.h>

using namespace std;

int n,m;
int f[100100][100];

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()
{
	n=read();m=read();
	for(int i=1;i<=n;i++)
	{
		f[i][0]=read();
	}
	for(int j=1;(1<<j)<=n;j++)
	{
		for(int i=1;i+(1<<j)-1<=n;i++)
		{
			f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
		}
	}
	while(m--)
	{
		int k=0;
		int l,r;
		l=read();r=read();
		while((1<<(k+1))<=r-l+1)k++;
		int ans=max(f[l][k],f[r-(1<<k)+1][k]);
		printf("%d\n",ans);
	}
	return 0;
 }