RMQ问题的求解方法—ST算法

ST算法针对的是没有修改操作的多次询问的RMQ问题，如果遇见动态的RMQ问题，使用时要谨慎。

主要思路：dp 预处理
时间复杂度：预处理时间复杂度O（nlogn），查询时间O（1）。
我们还是直接题目引入：

输入一串数字，给你 $M$M个询问，每次询问就给你两个数字 $X,Y,$X,Y,要求你说出 $X$X到 $Y$Y这段区间内的最大数。
输入格式：
第一行两个整数 $N,M$N,M表示数字的个数和要询问的次数；
接下来一行为 $N$N个数；
接下来 $M$M行，每行都有两个整数 $X,Y$X,Y。
输出格式：
输出共 $M$M行，每行输出一个数。
样例输入
10 2
3 2 4 5 6 8 1 2 9 7
1 4
3 8
样例输出
5
8
对于全部数据， $1\le N\le 10^5,1\le M\le 10^6,1\le X\le Y\le N.$1≤N≤105,1≤M≤106,1≤X≤Y≤N.

ST表的主要思想是DP思想，我们按照解决DP的套路来解决这个问题。

1.确定状态： $dp\left[i\right]\left[j\right]$dp[i][j]

我们设一个数组 $dp\left[i\right]\left[j\right]$dp[i][j]，前面的 $i$i代表的是当前的位置，即输入数组的下标， $j$j这个数字代表的是选着的区间长度为 $2^j$2j,因为我们选取一些 $2$2 的整数次幂来作为代表值从而划分整个区域,那么 $dp\left[i\right]\left[j\right]$dp[i][j]代表的是原序列在区间 $[i,i+2^j-1]$[i,i+2j−1]之间的最值。

2.状态转移方程： $dp\left[i\right]\left[j\right]=max\left(dp\right[i\left]\right[j-1],dp[i+(1\&lt;\&lt;j-1)\left]\right[j-1\left]\right)$dp[i][j]=max(dp[i][j−1],dp[i+(1<<j−1)][j−1])（位运算的优先级比加减法低）

3.初始条件和边界情况：

初始条件就是将原数组输出进去：

for(int i=1,i<=n;i++){//n是数组元素个数
	dp[i][0]=a[i];
}

4.计算顺序：

在这个问题中我们要先更新 $i$i 的值，再更新 $j$j 的值。代码如下：

for(j=1;j<=log[n];j++){
		for(i=1;i+(1<<j)-1<=n;i++){
			dp[i][j]=max(dp[i][j-1],dp[i+(1<<j-1)][j-1]);
		}
	}

如果我们按照常规思路，外层 $i$i ，内层 $j$j ,那我们计算的时候 $dp\left[i\right]\left[j\right]$dp[i][j]里面是没有值的。举个栗子：我们要求 $dp\left[3\right]\left[2\right]$dp[3][2],如果我们按照上面那样求，我们需要知道 $dp\left[3\right]\left[1\right]$dp[3][1]和 $dp\left[4\right]\left[1\right]$dp[4][1],先循环 $j$j ，我们的得不到 $dp\left[4\right]\left[1\right]$dp[4][1]的值，计算也无法展开了，所以我们要按上面那种方法去做。

小技巧:

在这个算法里面我们要用到log()函数，但是 cmath 库里log()函数效率不高，所以我们可以直接递推处理出 $1\dots n$1…n的函数。

log[0]=-1//初始化，让log[1]=0
for(int i=1;i<=n;i++){
	log[i]=log[i>>1]+1;
}

AC代码如下：

#include<iostream>
using namespace std;
typedef long long ll;
ll a[100005],i,j,log[1000050];
ll tree[100005][1000];
int main(){
	ll n,m;
	scanf("%lld%lld",&n,&m);	
	for(i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	log[0]=-1;
	for(i=1;i<=n;i++){
		tree[i][0]=a[i];
		log[i]=log[i>>1]+1;
	}
	for(j=1;j<=log[n];j++){
		for(i=1;i+(1<<j)-1<=n;i++){
			tree[i][j]=max(tree[i][j-1],tree[i+(1<<j-1)][j-1]);
		}
	}
	while(m--){
		ll l,r;
		scanf("%lld%lld",&l,&r);
		int len=log[r-l+1];
		printf("%lld\n",max(tree[l][len],tree[r-(1<<len)+1][len]));
	}
}

//蒟蒻的学习总结，如果有问题欢迎指出。