ST算法

Author: 炎炎龙虾
Created: Jul 12, 2020 7:52 AM
Difficulty: 普及

简介

ST整个算法就是基于倍增的产物，用于解决 RMQ（区间最值）类问题。它可以在 $O(logn)$ 的时间预处理后，用 $O(1)$ 的时间复杂度查找一个区间内的最大值。（如果你想在询问的时候再进行修改，那么还是推荐你使用线段树）。

开始了……

首先，我们知道，任意一个正整数 $n$ 都能标示为 $2^i+j(i,j\in{N})$ 的形式，因此，我们定义 $f[i][j]$ 为从 $i$ 开始 $2^j$ 个数中的最大值。那么，不难想到 $f[i][0]=a[i]$ ，就是 $a[i,i]$ 中的最大值。到这里，可能会让人想到动态规划或递推，那么我们就需要一个转移公式。

初始化 $f$ 数组的整体思想与区间DP有些相似，先附上代码，再解释。

int t=log(n)/log(2)+1;  //换底公式
for (int j = 1; j < t; ++j)  //预处理
    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]);//相当于是状态转移方程

第一重循环像是区间DP中的状态（不懂没关系），是 $f[i][j]$ 中的 $j$ 。第二轮循环枚举起点 $i$ 。 $j$ 的最大值为 $log_2^n$ 。由对数的换底公式得，

$log_2^n=\tfrac{log_{10}^n}{log_{10}^2}$

所以

注意： $cmath$ 库中 $log()$ 函数是以 $10$ 为底的。

int t=log(n)/log(2)+1;

有了 $j$ ， $i$ 的最大值也很好解释了。在循环里，每次将 $f[i][j]$ 从上一个状态中转移。

因为 $2^j=2*2^{j-1}$ ,因此将 $f[i][j]$ 二分，从两个区间中选取最大值。即

$f[i][j]=max\biggl(f[i][j-1],f\biggl[i+\Bigl(1<<(j-1)\Bigr)\biggr]\biggl[j-1\biggr]\biggr)$

下面问题来了，怎么查询呢？

查询时可以将 $[i,j]$ 所表示的区间二分，我们可以找到至少一个数 $x$ 使 $x\in{[i,i+2^j-1]}$ ，因此可以将 $[i,j]$ 分成 $f[i][k]$ 和 $f[j-(1<<k)+1][k]$ （其中 $k=log^{l-r+1}_2$ ），即 $[i,j]$ 中最大值为 $max(f[i][k],f[j-(1<<k)+1][k])$ 。

到这里，基本就解决了，还有几条优化建议：

读入优化（当然输出优化也可以）
为保证查询复杂度为 $O(1)$ ，用数组保存 $log(i)$ 结果。
可以省略 $a$ 数组，直接输入到 $f[i][0]$

例题

某谷有一模板题，名曰“ST表”，在这里：

【模板】ST表

附上 $AC$ 代码供参考：

//
// Created by admin on 2020/7/11.
//
#include <bits/stdc++.h>
using namespace std;
int n,f[105000][40],m;
double lo[105000];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int main()
{
    int x,y;
    n=read();m=read();
    for(int i=1;i<=n;i++)
    {
        f[i][0]=read();
        lo[i]=log(i);
    }
    int t=lo[n]/lo[2]+1;    //换底公式
    for (int j = 1; j < t; ++j)  //预处理
        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]);//相当于是状态转移方程
    while(m--)
    {
        x=read();y=read();
        int k=lo[y-x+1]/lo[2];
        printf("%d\n",max(f[x][k],f[y-(1<<k)+1][k]));
    }
    return 0;
}

备注：此题数组定义请严格按照题目中数据范围，不然会 $RE$ 满天飞。

参考资料：

李煜东《算法竞赛进阶指南》