ST 表

simple_child · 2025-08-23 15:47:54 · 算法·理论

上课没认真听，现在忘了，重学一下。

ST 表（Sparse Table，稀疏表）是用于解决 可重复贡献问题 的数据结构。 ::::info[什么是可重复贡献问题]{open} 可重复贡献问题 是指对于运算 \operatorname{opt}，满足 x\operatorname{opt} x=x，则对应的区间询问就是一个可重复贡献问题。例如，最大值有 \max(x,x)=x，gcd 有 \operatorname{gcd}(x,x)=x，所以 RMQ 和区间 GCD 就是一个可重复贡献问题。另外，\operatorname{opt} 还必须满足结合律才能使用 ST 表求解。 ::::info[什么是RMQ] RMQ 是英文 Range Maximum/Minimum Query 的缩写，表示区间最大（最小）值。 ::::

模板题。

考虑暴力。时间复杂度 O(nm)，会超时。

考虑线段树区间查询最大值。时间复杂度 O(m\log n)，貌似可以，但会被卡常。优化优化可以卡过去，但没有必要，毕竟线段树板子可是个绿题，这题只不过是黄题。
那为什么这题是个黄题呢？注意到这道题是求静态区间最大值，而线段树还支持区间修改操作。

考虑离线。我们可以仿照前缀和的预处理思路来尝试解决这道题。
基于倍增思想，我们考虑如何求出区间最大值。
可以发现，如果按照一般的倍增流程，每次跳 2^i 步的话，单次询问时的复杂度是 O(\log n)，并没有比线段树更优。 ::::info[如何基于一般的倍增流程实现求 RMQ] 要使用 一般倍增思想 求区间最大值，核心是保留倍增思想的 “幂次步长预处理”，查询时通过 “从大到小用 2 的幂次步长逐步拆分目标区间”，用多个不重叠的幂次区间 “拼凑” 出完整目标区间，最终取这些区间的最大值。

设 \mathrm{dp}[i][j] 表示从数组第 j 个元素开始，长度为 2ⁱ 的区间的最大值。

1. 初始化：当 i=0 时，区间长度为 1，最大值就是元素本身。
2. 长度为 2ⁱ 的区间可拆成两个长度为 2ⁱ⁻¹ 的子区间，因此 \mathrm{dp}[i][j] = \max(\mathrm{dp}[i-1][j],\mathrm{dp}[i-1][j + 2ⁱ⁻¹])。 :::: 那我们重新回归问题的根本。发现 \max(x,x)=x，即这个问题是一个 可重复贡献问题。
   那该如何求解呢？

令 f(i,j) 表示区间 [i,i+2^j-1] 的最大值，即 f(i,j) 表示以第 i 个元素为开头区间长度长度为 2^j 的区间最大值。
显然 f(i,0)=a_i。

根据定义式，第二维就相当于倍增的时候「跳了 2^j-1 步」，依据倍增的思路，写出状态转移方程：

::::info[如果你还不太理解这个状态转移方程] 我们可以先把每一项展开：

观察到第三个式子还可以进一步化简，我们合并两个 2^{j-1}，得到：

所以说 f(i,j)=\max(f(i,j-1),f(i+2^{j-1},j-1))。
再给出 OI-Wiki 上的图：
:::align{center} ::: :::: 综上，我们就可以写出预处理每个区间最大值的代码：

for(int i=1;i<=n;i++) f[i][0]=a[i];
for(int j=1;j<=log2(n);j++)
{
    //1<<j=2^j 1<<(j-1)=2^{j-1}
    for(int i=1;i<=n-(1<<j)+1;i++)
    {
        f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
    } 
}

时间复杂度为 O(n\log n)。 :::::info[如果你还不太理解循环的边界] 第一个循环没什么好说的，跳过了，考虑剩下的双重循环。

考虑第一重循环。
注意到第一重循环枚举的是 j，我们用 2^j 表示区间长度，所以我们只需枚举到 \log n 即可。 ::::info[std::log2 时间复杂度] 这一点在 OI-Wiki 上有一定争议，OI-Wiki 认为我们需要预处理一个数组 \texttt{Logn}：

但是预处理的时间复杂度为 O(n)。

同时，std::log2 的时间复杂度为 O(1)，我们同样可以 O(n) 处理对于 n 个数其中每个数 x 的 \log x。 :::: 考虑第二重循环。
因为 i+2^j-1≤n，所以有 i<=n-(1<<j)+1，自己推一下就行了。 ::::: 接下来我们只需要将每个查询的区间拆成若干的已处理出的区间即可。

当询问任意区间 [l, r] 的最大值时，我们先计算出一个 k，满足：2^k \leq r - l + 1 < 2^{k+1}。也就是在小于等于区间长度的前提下，找到最大的 2^k。
此时，从 [l, r] 左起的 2^k 个数，也就是 [l,l+2^k-1] 和以 [l, r] 右起的 2^k 个数，也就是 [r-2^k+1,r]，这两段一定覆盖 [l, r]。
很容易注意到，即使区间有重复部分，也不会影响最终整个区间的结果。我们只需要在这两个最大值区间内取一个更大的数即可。 :::info[正确性证明]{open} 为什么中间有重复部分是正确的，很明显，我们先令 l < i < j < r ，那么 f(l,r) = \max(f(l,j), f(j+1,r)) = \max(f(l,i), f(i+1,r)) = \max(f(l,j), f(i,r)) ，即使中间重叠了 [i,j] 这段区间也没有问题，重复算对 \max 没有影响。 ::: 那么我们该如何求 k 的值呢？
我们注意到 2^k\leq r - l + 1，我们只需要式子整体取一个 \log 就可以得到 k 的范围了。k \leq \log_2(r-l+1) ，即 \max(k)=\left\lfloor \log_2(r-l+1) \right\rfloor。显然这里不能上取整，否则 k 会大于 \log_2(r-l+1)。

综上，我们可以写出代码：

int l,r;
for(int i=1;i<=m;i++) 
{
    cin>>l>>r;
    int k=log2(r-l+1);
    cout<<max(f[l][k],f[r-(1<<k)+1][k])<<endl;
}

时间复杂度 O(m)，单次求解O(1)。
注意一点，容易让人走不出去，这里的 f(l,k) 所表示的区间等价于 [l,l+2^k-1]。

整体代码如下，因为模板题比较卡常，所以有一些细微优化。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10,MAXJ=log2(MAXN)+10;
int f[MAXN][MAXJ];
int a[MAXN];
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()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    //ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;++i) a[i]=read();
    for(int i=1;i<=n;++i) f[i][0]=a[i];
    int t=log2(n);
    for(int j=1;j<=t;++j)
    {
        //1<<j=2^j 1<<(j-1)=2^{j-1}
        for(int i=1;i<=n-(1<<j)+1;++i)
        {
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        } 
    }
    int l,r;
    for(int i=1;i<=m;++i) 
    {
        l=read(),r=read();
        int k=log2(r-l+1);
        cout<<max(f[l][k],f[r-(1<<k)+1][k])<<'\n';
    }
    return 0;
}

P8818 [CSP-S 2022] 策略游戏

小 L 在 A[l_1…r_1] 中选择一个 x，然后小 Q 在 B[l_2…r_2] 中选择一个 y，分数是 x×y。小 L 想让分数尽可能大，小 Q 想让分数尽可能小。求分数。

肯定先思考小 Q 再思考 小 L，因为小 L 会思考小 Q 的思考。

小 Q 的行为就是对于 x，找到一个 B[l_2…r_2] 中的 y，使得 x×y 最小。

自然的，

那么小 L 的行为是什么呢？还是按照正负分类讨论：

如果小 L 这次想让 x \geq 0 ，那么小 Q 会选择最小的 y 。如果这个 y \geq 0 ，那么小 L 一定会选最大的 x ；如果这个 y < 0 ，那么小 L 一定会选最小的非负数 x 。

如果小 L 这次想让 x < 0 ，那么小 Q 会选择最大的 y 。如果这个 y \geq 0，那么小 L 一定会选最大的负数 x ；如果这个 y < 0 ，那么小 L 一定会选最小的 x 。

因此小 L 的行为只有四种：选择最大的 x ；最小的 x ，最大的负数 x ，最小的非负数 x 。

分别讨论小 L 选择四种行为时小 Q 的选择，答案取最大值即可。

本题要做 q(q\leq 10^5) 次询问，所以用 ST 表分别维护 6 个 RMQ 即可，预处理时间复杂度 O(n\log n)，其中 n 为数列长度。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
const int MALN=log2(MAXN)+5;
const long long inf=LONG_LONG_MAX,minn=LONG_LONG_MIN;
long long amx[MAXN][MALN],amn[MAXN][MALN],afx[MAXN][MALN],azn[MAXN][MALN];
long long bmx[MAXN][MALN],bmn[MAXN][MALN];
long long a,b;
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++) 
    {
        cin>>a;
        amx[i][0]=amn[i][0]=a,afx[i][0]=(a<0?a:minn),azn[i][0]=(a>=0?a:inf);
    }
    for(int i=1;i<=m;i++) 
    {
        cin>>b;
        bmx[i][0]=bmn[i][0]=b;
    }
    int ln=log2(n),lm=log2(m);
    for(int j=1;j<=ln;j++)
    {
        for(int i=1;i<=n-(1<<j)+1;i++)
        {
            int jj=j-1;
            int p=i+(1<<(jj));
            amx[i][j]=max(amx[i][jj],amx[p][jj]);
            afx[i][j]=max(afx[i][jj],afx[p][jj]);
            amn[i][j]=min(amn[i][jj],amn[p][jj]);
            azn[i][j]=min(azn[i][jj],azn[p][jj]);
        } 
    }
    for(int j=1;j<=lm;j++)
    {
        for(int i=1;i<=m-(1<<j)+1;i++)
        {
            int jj=j-1;
            int p=i+(1<<(j-1));
            bmx[i][j]=max(bmx[i][jj],bmx[p][jj]);
            bmn[i][j]=min(bmn[i][jj],bmn[p][jj]);
        }
    }
    int l1,r1,l2,r2;
    while(q--)
    {
        cin>>l1>>r1>>l2>>r2;
        int lo1=log2(r1-l1+1),lo2=log2(r2-l2+1);
        int x=r1-(1<<lo1)+1,y=r2-(1<<lo2)+1;
        long long mamx=max(amx[l1][lo1],amx[x][lo1]);
        long long mamn=min(amn[l1][lo1],amn[x][lo1]);
        long long mafx=max(afx[l1][lo1],afx[x][lo1]);
        long long mazn=min(azn[l1][lo1],azn[x][lo1]);
        long long mbmx=max(bmx[l2][lo2],bmx[y][lo2]);
        long long mbmn=min(bmn[l2][lo2],bmn[y][lo2]);
        long long ans=minn;
        ans=max(ans,mamx*(mamx>=0?mbmn:mbmx));
        ans=max(ans,mamn*(mamn>=0?mbmn:mbmx));
        if(mafx!=minn) ans=max(ans,mafx*(mafx>=0?mbmn:mbmx));
        if(mazn!=inf) ans=max(ans,mazn*(mazn>=0?mbmn:mbmx));
        cout<<ans<<endl;
    }
    return 0;
}