ST表（RMQ问题）

算法理解

RMQ问题就是对与区间最值查询一类问题的总称

对于RMQ问题的求解主要有以下两种方式：

• 线段树，建树O(n)，查询O(logn)，支持在线修改
• ST表，预处理O(logn)，查询O(1)，不支持在线修改

这个单元主要讲解的是ST表

倍增思想

考虑一个数必然能被拆分成二进制，所以我们先预处理出 \(2^k\) 的答案，对于一次查询，我们直接将查询分为二进制各个位，按位依次求解即可，通常搭配预处理使用

ST表

本质上是对区间进行一个拆分，拆成一块一块，然后对块进行查询

正常的分块一个块长是 \(\sqrt n\)，因为不需要进行修改操作（个人理解），所以我们可以将区间拆分的更细致一些，以至于块与块之间可以重叠

结合倍增思想，我们选择将块长定为 \(2^k\)，对于每一个端点都求出从这个端点出发，覆盖 \(2^k\) 个点的区间的最值，具体拆分方式见下图

少一张图片

预处理

因为静态询问所以我们先预处理出这个倍增数组，因为 \(2^k=2^{k-1}+2^{k-1}\) 所以 \(2^k\) 的答案可以通过 \(2^{k-1}\) 递推得来，因为递推本质上是递推，所以我们将这个数组设为 \(dp[i][j]\) 表示从i开始经过 \(2^j\) 个点的区间的最大值

查询

我们想要查询 \((l,r)\) 的区间最值，可以将其拆分成两个可以重叠的区间，区间长度就是 \(log2(r-l+1)\) 就是最大的二进制位，第一个区间的左端点就是l，第二个区间的右端点就是r

\(ans=max(dp[l][k],dp[r-(1<<k)+1][k]))\)

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int n,m,l,r;
int a[N],dp[N][40];
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		dp[i][0]=a[i];
	}
	for(int j=1;j<=32;j++){
		for(int i=1;i+(1ll<<j)-1<=n;i++){
			dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
		}
	}
	for(int i=1;i<=m;i++){
		scanf("%lld%lld",&l,&r);
		int k=log2(r-l+1);
		printf("%lld\n",max(dp[l][k],dp[r-(1<<k)+1][k]));
	}
}

T2：

直接把max改成gcd即可

考虑两个区间可以合并，当且仅当区间重复计算并不会对答案产生影响，因为查询时两个区间是重叠的

那我可不可以将ST表改成倍增我对区间(l,r)，进行一个二进制拆分，然后使得区间查询时并不重复，就能实现O(logn)静态维护区间加区间乘呢？(问题暂且保留)