知识点

一 . 基本概念

ST表：又名稀疏表，用来处理区间最值查询的离线算法，用到了倍增的思想

某个区间查询问题是否适用ST表，关键在于其进行的操作是否允许区间重叠。

例如max(a,b,c) = max{max(a,b),max(b,c)}就可以用ST表维护，而区间和问题则不能维护。

在时间复杂度上：预处理时间O(nlogn)，单词查询O(1)，时间复杂度：O(nlogn+m) 。

二 . 实现方式

设二维数组f[i][j]代表从i号位置开始往后推 $2^j$ 个单位长度的区间里的最大值，即 $[i,i+2^j-1]$ 区间的最大值

① 预处理

这里要注意更新顺序，因为其中 j （第二维）才是阶段，而第一维 x 是状态，所以对于 j 的循环要放在最外层。

② 查询

当查询任意区间的最大值时，先计算出指数k，满足不等式 $2^k \leqslant r-l+1<2^{k+1}$ ，将该不等式同时转换为以 $log_2$ 为底的数： $k \leqslant log_2(r-l+1) <k+1$ ，可得：k为当前小于区间长度且能满足2的k次幂的值最大的数。

左端点：num[l][l+2^k-1]

右端点：num[r-2^k+1][r]

注意这里的 $2^k$ 的表示方法：(1<<k)=pow(2,k)= $2^k$

！！位运算优先级很低但是运算速度快，需要加括号

模板题

例题：洛谷 P3865 【模板】ST 表 / 洛谷 P1816 忠诚

题目背景

这是一道 ST 表经典题——静态区间最大值（静态RMQ问题）

题目描述

给定一个长度为 N 的数列，和 M 次询问，求出每一次询问的区间内数字的最大值。

输入格式

第一行包含两个整数 N,M，分别表示数列的长度和询问的个数。

第二行包含 N 个整数（记为 $a_i$ ），依次表示数列的第 i 项。

接下来 M 行，每行包含两个整数 $l_i,r_i$ ，表示查询的区间为 $[l_i,r_i]$ 。

输出格式

输出包含 M 行，每行一个整数，依次表示每一次询问的结果。

输入输出样例

输入 #1

8 8
9 3 1 7 5 6 0 8
1 6
1 5
2 7
2 6
1 8
4 8
3 7
1 8

输出 #1

说明/提示

对于 30% 的数据，满足 $1\leqslant N,M\leqslant 10$ 。

对于 70% 的数据，满足 $1\leqslant N,M\leqslant {10}^5$ 。

对于 100% 的数据，满足 $1\leqslant N\leqslant {10}^5$ ， $1\leqslant M\leqslant 2\times{10}^6$ ， $a_i\in[0,{10}^9]$ ， $1\leqslant l_i\leqslant r_i\le N$ 。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define re register
using namespace std;
const int maxn=1e5+5;
int f[maxn][21];
int n,m;
inline int read()  //快读模板
{
    re int x=0,f=1;
    re char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return x*f;
}

inline int rmq(int l,int r)
{
    re int k=log2(r-l+1); 
        //如果2k+1<=r-l+1
        //while (1<<(k+1)<=r-l+1) ++k; 同样的效果
    return max(f[l][k],f[r-(1<<k)+1][k]);
}

int main()
{
    n=read(),m=read();
    for(re int i=1;i<=n;++i)
    {
        f[i][0]=read();
    }

    for(re int j=1;j<=21;++j)
    {
        for(re int i=1;i+(1<<j)-1<=n;++i)
        {
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }

    for(re int i=1;i<=m;++i)
    {
        re int g=read(),b=read();
        printf("%d\n",rmq(g,b));
    }
    return 0;
}

相关练习

1 . 洛谷 P1440 求m区间内的最小值

朴素ST表（80pts）：会存在两个数据MLE。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define ll long long 
#define re register
using namespace std;
int n,m,t;
const int maxn=2e7+5;
int a[maxn],f[maxn][21];
inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return x*f;
}

inline void ST() //ST表预处理
{
	for(re int i=1;i<=n;++i)
	{
		f[i][0]=a[i];
	}
	for(re int j=1;j<=20;++j)
	{
		for(re int i=1;i+(1<<j)-1<=n;++i)
		{
			f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
		}
	}
}

inline int query(int l,int r) //ST表查询
{
	int k=log2(r-l+1);
	return min(f[l][k],f[r-(1<<k)+1][k]); //要注意这里r-(1<<k)+1的写法，不要写漏东西
}

int main()
{
	n=read(); m=read();
	for(re int i=1;i<=n;++i)
	{
		a[i]=read();
	}
	ST();
	for(re int i=1;i<=n;++i)
	{
		re int l=i-m,r=i-1;
		if(r<1) //第一个数据输出为0
		{
		printf("0\n");	
		continue;
		} 
		if (l<1) l=1;
             //如果查询的范围大到超出i之前的所有数，从边界1开始处理
		printf("%d\n",query(l,r));
	}
	return 0;
}

（待填坑）滚动数组优化

我不会。。。

2 . 洛谷 P2251 质量检测

该题注意查询部分：第 i 行的数表示 Q[i + M - 1] 即可。

原文链接：https://blog.csdn.net/gzkeylucky/article/details/126736392