ST表学习笔记

浅谈ST表

ST表通常用来解决这个问题

有N个数，M次询问，每次给定区间[L,R]，求区间内的最大值。

ST表的功能很简单

它是解决RMQ问题(区间最值问题)的一种强有力的工具

它可以做到 \(O(nlogn)\) 预处理， \(O(1)\) 查询最值

思想

我们现在要 \(O(1)\) 求最大值，最暴力的方法就是记录 \(f_{i,j}\) 为 \([i,j]\) 内的最大值，显然有转移方程 \(f_{i,j}=\max \left(f_{i,j-1},a_{j}\right)\)

但这样的预处理是 \(O(n^{2})\) 的，会 TLE ，我们考虑进一步优化

通过观察可以发现，\(\max (a,b,c) = \max (\max(a,b),\max(b,c))\) ，\(\min\) 也支持这个原理

需要注意的是，ST表基于这个原理，所以求区间最值的正确性是能保证的，但是ST不能维护区间和，因为\(a+b+c \neq (a+b)+(b+c)\)

让我们重新定义 \(f_{i,j}\) 为从 \(i\) 开始连续 \(2^{j}\) 个数最大值

举个栗子，设这个序列为 \([2，7，3，6，9]\)

现在我们考虑 \(f_{1,2}\) ,也就是 \([1,4]\) 的最大值

我们可以把 \([1,4]\) 分成 \([1,2]\) 和 \([3,4]\) 两个小区间，这两个区间就是 \(f_{1,1}\) 与 \(f_{3,1}\) ，而 \(f_{1,1}=7,f_{3,1}=6\) ，所以 \(f_{1,2}=\max(f_{1,1},f_{3,1})=7\)

我们发现，在这种方式下，以每个起点开始都有 $ \log(n)$ 个区间，每个区间都可以 \(O(1)\) 求出，所以预处理的复杂度就是 \(O(n \log n)\)

如何查询？

可设这段区间的左右端点为 \(l,r\)，长度为 \(len\)

我们从左端点向右找一段 \(2^{\log(len)}\) 的区间，从右端点向左找一段 \(2^{\log(len)}\) 的区间，显然这两段区间已经覆盖了整个区间，去这两个区间的最大值即可

在 cmath 库中，\(\log\) 的复杂度是 \(O(\log(n))\) 的，为了保证 \(O(1)\) 查询，我们需要提前预处理出 \(\log(i)\) 向下取整的值

示例代码

P3865 【模板】ST表

#include 
#include 
#include 
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
const int N=1e5+7,LOGN=160;
int f[N][LOGN];
int LOG[N];
int a[N];
int n,m;
int main() {
	scanf("%d%d",&n,&m);
	LOG[0]=-1;
	for(int i=1;i<=n;++i)
		LOG[i]=LOG[i>>1]+1;//预处理LOG数组
	for(int i=1;i<=n;++i) {
		scanf("%d",a+i);
        f[i][0]=a[i];
    }
	for(int j=1;j<=LOG[n];++j) 
		for(int i=1;i<=n-(1<

#include 
#include 
#include 
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int N=1e5+7,LOGN=160;
int maxx[N][LOGN],minn[N][LOGN];
int LOG[N];
int a[N];
int n,m;
int main() {
	scanf("%d%d",&n,&m);
	LOG[0]=-1;
	for(int i=1;i<=n;++i)
		LOG[i]=LOG[i>>1]+1;
	for(int i=1;i<=n;++i) {
		scanf("%d",a+i);
		minn[i][0]=maxx[i][0]=a[i];
	}
	for(int j=1;j<=LOG[n];++j) 
		for(int i=1;i<=n-(1<

#include 
#include 
#include 
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
const int N=1e5+7,LOGN=160;
int f[N][LOGN];
int LOG[N];
int a[N];
int n,m;
int main() {
	scanf("%d%d",&n,&m);
	LOG[0]=-1;
	for(int i=1;i<=n;++i)
		LOG[i]=LOG[i>>1]+1;
	for(int i=1;i<=n;++i)
		scanf("%d",a+i);
	for(int i=1;i<=n;++i)
		f[i][0]=a[i];
	for(int j=1;j<=LOG[n];++j) 
		for(int i=1;i<=n-(1<

#include 
#include 
#include 
#include 
#define max(a,b) ((a)>(b)?(a):(b))
typedef long long ll;
using namespace std;
const int inf=0x3f3f3f3f;
const int M=2e5+7;
ll f[M][21];
int LOG[M];
ll t,mod;
int n,m;
char c;
inline void change(int u,int val) {
    f[u][0]=val;
    for(int i=1;(u-(1<=0;++i) 
    	f[u][i]=max(f[u][i-1],f[u-(1<<(i-1))][i-1]);
}
inline ll find(int l,int r) {
    int k=LOG[r-l+1];
    return max(f[r][k],f[l+(1<>1]+1;
    for(ll x,val;m;--m) {
        cin>>c;
        if(c=='A') {
            scanf("%lld",&x);
            val=(x+t)%mod;
            ++n;
            change(n,val);
        }
        else {
            scanf("%lld",&x);
            printf("%lld\n",find(n-x+1,n));
            t=find(n-x+1,n);
        }
    }
    return 0;
}