文章目录

• 一、介绍
• • 1.作用——可重复贡献问题
  • 2.ST表的优劣
• 二、实现（基于RMQ）
• • 1.预处理
  • 2.查询
  • 3.对数优化
  • 4.模板代码

一、介绍

1.作用——可重复贡献问题

对于操作 o p t opt opt，满足 ∀ l ≤ k ≤ r , o p t [ l , r ] = o p t ( o p t [ l , k ] , o p t [ k , r ] ) \forall l \leq k \leq r,opt[l,r]=opt( opt[l,k],opt[k,r]) ∀l≤k≤r,opt[l,r]=opt(opt[l,k],opt[k,r])，例如 R M Q RMQ RMQ区间求最值，又如区间 G C D GCD GCD，都可以称为可重复贡献问题。
而ST表就是用于解决以 R M Q RMQ RMQ问题为代表的可重复贡献问题。

2.ST表的优劣

之前我们学习过线段树，同样可以用于解决 R M Q RMQ RMQ问题，与线段树相比，稀疏表的码量更少，但同样，稀疏表所适合的情况也更局限一些。
稀疏表包含两个过程，分别是预处理和查询，预处理的时间复杂度为 O ( n   l o g n ) O(n\ logn) O(n logn),而查询可以在 O ( 1 ) O(1) O(1)内实现。
稀疏表的局限在于不支持在线修改，一旦预处理结束后，就只能对静态的区间进行查询（一般情况）。

二、实现（基于RMQ）

我们以 s t [ i ] [ j ] st[i][j] st[i][j]表示 m a x { a [ k ] ∣ i ≤ k ≤ i + 2 j − 1 } max\{a[k]\mid i\leq k \leq i+2^j-1\} max{a[k]∣i≤k≤i+2j−1}

1.预处理

思路与动态规划一致，自左向右，自上往下递推出结果。
需要注意一下计算顺序！！！

递推式： s t [ i ] [ j ] = m a x ( s t [ i ] [ j − 1 ] , s t [ i + ( 1 < < ( j − 1 ) ) ] [ j − 1 ] ) st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]) st[i][j]=max(st[i][j−1],st[i+(1<<(j−1))][j−1])
基于 ∀ l ≤ k ≤ r , o p t [ l , r ] = o p t ( o p t [ l , k ] , o p t [ k , r ] ) \forall l \leq k \leq r,opt[l,r]=opt( opt[l,k],opt[k,r]) ∀l≤k≤r,opt[l,r]=opt(opt[l,k],opt[k,r])

for(int j=1;j<=logn;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	}

2.查询

若给定任意区间范围 [ l , r ] [l,r] [l,r]，如何根据 s t [ i ] [ j ] st[i][j] st[i][j]求出对应结果？
a n s = m a x { s t [ l ] [ k ] , s t [ r − ( 1 < < k ) + 1 ] [ k ] } ans=max\{st[l][k],st[r-(1<<k)+1][k]\} ans=max{st[l][k],st[r−(1<<k)+1][k]}

s t [ l ] [ k ] st[l][k] st[l][k]表示区间 [ l , l + 2 k − 1 ] [l,l+2^k-1] [l,l+2k−1]
s t [ r − ( 1 < < k ) + 1 ] [ k ] st[r-(1<<k)+1][k] st[r−(1<<k)+1][k]表示区间 [ r − 2 k + 1 , r ] [r-2^k+1,r] [r−2k+1,r]
为了保证区间的重叠，应满足 r − 2 k + 1 ≤ l + 2 k − 1 r-2^k+1 \leq l+2^k-1 r−2k+1≤l+2k−1
化为: r − l 2 + 1 ≤ 2 k \frac{r-l}{2}+1\leq 2^k 2r−l​+1≤2k
对式子两边取对数，
得： l o g 2 ( r − l 2 + 1 ) ≤ k log_2(\frac{r-l}{2}+1)\leq k log2​(2r−l​+1)≤k

若 k k k直接取 l o g 2 ( r − l 2 + 1 ) log_2(\frac{r-l}{2}+1) log2​(2r−l​+1),可以得到一个唯一的中间点 r + l 2 \frac{r+l}{2} 2r+l​，看上去这应该是理想的值，但实际上我们很难使得 k k k恰好等于 l o g 2 ( r − l 2 + 1 ) log_2(\frac{r-l}{2}+1) log2​(2r−l​+1)，首先是计算 r − l 2 \frac{r-l}{2} 2r−l​要考虑结果会自动舍去小数部分，其次是计算对数也需要化为整型，依然会舍去小数部分，这些都会使得最终计算出来的 k k k小于 l o g 2 ( r − l 2 + 1 ) log_2(\frac{r-l}{2}+1) log2​(2r−l​+1)。

所以我们令 k k k等于 l o g 2 ( r − l + 1 ) log_2(r-l+1) log2​(r−l+1),不必考虑除法计算，虽然计算过程中仍然要考虑对数化为整型的情况，但可以保证两个子区间可以覆盖大的区间。

3.对数优化

过程中需要多次使用log，本来可以直接使用 S T L STL STL中的函数，但为了避免超时，可以直接打表。
l o g [ i ] = { − 1 i = 0 l o g [ i 2 ] + 1 i > 0 log[i]=\begin{cases} -1 & i=0 \\ log[\frac{i}{2}]+1 & i>0\\ \end{cases} log[i]={−1log[2i​]+1​i=0i>0​

4.模板代码

模板题

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
const int logn=log2(N);
int n,m;
int st[N][logn];
int Logn[N]; 
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();
	Logn[0]=-1;
	for(int i=1;i<=n;i++){
		st[i][0]=read();
		Logn[i]=Logn[i/2]+1;//计算以2为底的对数 
	}
	for(int j=1;j<=logn;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	}
	int l,r,k;
	while(m--){
		l=read();
		r=read();
		k=Logn[r-l+1];
		printf("%d\n",max(st[l][k],st[r-(1<<k)+1][k]));
	}
}