🥍
ST算法
Created
Oct 21, 2020 08:28 AM
Tags
RMQ
ST算法

简介

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

开始了……

首先,我们知道,任意一个正整数都能标示为的形式,因此,我们定义为从开始个数中的最大值。那么,不难想到,就是中的最大值。到这里,可能会让人想到动态规划或递推,那么我们就需要一个转移公式。
初始化数组的整体思想与区间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中的状态(不懂没关系),是中的。第二轮循环枚举起点的最大值为。由对数的换底公式得,
所以
注意:库中函数为底的。
int t=log(n)/log(2)+1; 
 
有了的最大值也很好解释了。在循环里,每次将从上一个状态中转移。
因为,因此将二分,从两个区间中选取最大值。即
下面问题来了,怎么查询呢?
查询时可以将所表示的区间二分,我们可以找到至少一个数使,因此可以将分成 (其中),即中最大值为
到这里,基本就解决了,还有几条优化建议:
  1. 读入优化(当然输出优化也可以)
  1. 为保证查询复杂度为,用数组保存结果。
  1. 可以省略数组,直接输入到

例题

某谷有一模板题,名曰“ST表”,在这里:
附上代码供参考:
//
// 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;
}
备注:此题数组定义请严格按照题目中数据范围,不然会满天飞。
 
 
 



参考资料:
  1. 李煜东 《算法竞赛进阶指南》

Loading Comments...