ST表简介

主要作用

ST 表是用于解决 可重复贡献问题 的数据结构。

可重复贡献问题：是指对于运算$ opt $，满足$ x $ $ opt $ $ x $ = $ x $，则对应的区间询问就是一个可重复贡献问题。例如，最大值有$ max(x,x) $，gcd有$ \gcd(x,x)=x $，所以RMQ和区间GCD就是一个可重复贡献问题。像区间和就不具有这个性质，如果求区间和的时候采用的预处理区间重叠了，则会导致重叠部分被计算两次，这是我们所不愿意看到的。另外，$ opt $还必须满足结合律才能使用 ST 表求解。

什么是RMQ：RMQ 是英文Range Maximum/Minimum Query的缩写，表示区间最大（最小）值。

时间复杂度

预处理：$$ O(n \log n) $$

查询：$$ O(1) $$

基本形态

运用了倍增的思想，$ f[i][j] $ 表示区间 $[i,i+2^j-1] $

ST表的建立

原理

因为$ f[i][j] $ 表示区间 $[i,i+2^j-1] $，我们可以得出$ f[i][0]=a[i] $，根据倍增的思想，我们可以得到转移方程：$ f[i][j]=max(f[i][j-1],f[i^{j-1}][j-1]) $其中$ f[i][j-1] $ 表示的是从 $ i $到$ i^{j-1}-1 $区间的最大值，$ f[i^{j-1}][j-1] $表示的是从$ i^{j-1} $ 到$ 2^j-1 $这个区间的最大值，因为最大值是可重复贡献问题，所以取这两个区间的最大值即为区间 $ [i,2^j-1] $的最大值。

如图：

来自于作者Pecco算法学习笔记（12）：ST表

代码

for(int j=1;j<=21;j++)//21是相对而言的，严格来说是ceil(log(n))，n表示数据个数
{
    for(int i=1;i+(1<<j)-1<=n;i++)
    {
        f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);//转移方程，原理见上方文字
    }
}

ST表的查询

原理

对于每个询问 $ [l,s] $，我们把它分成两部分：$ [l,l+2^s-1] $与$ [r-2^s+1,s] $，其中 $ s=\lfloor \log(r-l+1) \rfloor $。两部分的结果的最大值就是回答。

代码

int f(int l,int r)//l表示查询区间的左端点，r表示查询区间的右端点
{
    int k;
    k=log2(r-l+1); 
    return max(a[l][k],a[r-(1<<k)+1][k]);
}

ST表中的优化

原理

因为在查询过程中，多次使用$ \log $计算，为了节省时间，我们可以预处理$ \log $的值。方法：

$$ \begin{cases} logn[1]=0, \\ logn[i]=logn[\frac{i}{2}]+1. \end{cases} $$

代码

void pre()
{
    logn[1]=0;
    logn[2]=1;
    for(int i=3;i<maxn;i++)
    {
        logn[i]=logn[i/2]+1;
    }
}

代码

来源：洛谷：P3865 【模板】ST 表

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int a[1000001][21],logn[100001];
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;
}
void pre()
{ 
	logn[1]=0; 
	logn[2]=1; 
	for(int i=3;i<64;i++) 
	{ 
		logn[i]=logn[i/2]+1; 
	} 
}

int f(int l,int r)
{
    int k;
    k=logn[r-l+1]; 
    return max(a[l][k],a[r-(1<<k)+1][k]);
}
int main()
{
    int n=read(),m=read();
    pre();
    for(int i=1;i<=n;i++)
    {
    	a[i][0]=read();
    }
    for(int j=1;j<=21;j++)
    {
        for(int i=1;i+(1<<j)-1<=n;i++)
        {
            a[i][j]=max(a[i][j-1],a[i+(1<<(j-1))][j-1]);
        }
    }
    for(int i=1;i<=m;i++)
    {
        int l=read(),r=read();
        printf("%d\n",f(l,r));
    }
    return 0;
}