详解RMQ-ST算法 ST模板-白红宇

详解RMQ-ST算法 ST模板

阅读量：6308 次

发布时间：2019-06-22

本文共 2869 字，大约阅读时间需要 9 分钟。

RMQ问题是求解区间最值的问题。

这里分析的是ST算法，它可以对所有要处理的数据做到O(nlogn)的预处理，对每个区间查询做到O(1)查询

ST算法本质是一个DP的过程

这里通过举一个求最大值实例来理解ST算法：

我们有这样一串数字

数值：35 13 65 99 88 75 64 51 42 55 66 83 12 44 65 12

位置：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

首先我们定义一个dp表达式：st[i][j]表示从i位置开始的2^j个数中的最大值；

具体解释：st[1][0]就是从第一个数字开始的一个数里的最大值，也就是第一个数本身，即st[1][0]=35；

　　 st[2][2]就是从第二个数字开始的四个数里的最大值，也就是13,65,99,88里面的最大值，即st[2][2]=99；

　　　　　以此类推

　　然后我们来看怎么用dp的思想来解决这个问题

　　回到刚刚的实例，我们由我们所定义的st式可以得知st[5][3]是[88,75,64,51,42,55,66,83]中的最大值。

　　现在我们来试着用dp的思想，也就是将整体化为部分求解的思想。

　　要求前面st[5][3]所代表区间的最大值，也就是求[88,75,64,51]和[42,55,66,83]两个区间的最大值中的较大值，即st[5][2]和st[9][2]

而这样的划分是一个二分划分，根据这种思想我们可以类推出，求i至其后2^j个数的最大值，即把2^j分成前后两个2^(j-1)，分别取最大值，再通过比较获得此状态最大值。

到此我们可以得出我们的dp表达式：st[i][j] = max( st[i][j-1],st[i+2^(j-1)][j-1] )

通过这种方法我们可以求出一段段区间的最大值

求ST表代码

void cal_st( int n, int a[] ) {  //n为区间元素个数，a数组存的是区间里的元素    for( int i = 1; i <= n; i ++ ) {        st[i][0] = a[i];    }	for( int j = 1; j <= log2(n); j ++ ) {        for( int i = 1; i <= n-(1<

接下来让我们回到RMQ问题：

　　我们可以知道，任意的i至j之间的j-i+1个连续的值，一定可以分为两个2^n个数的两个区间

　　比如求3到11之间的最大值；

　　因为3到11之间有9个元素，最大可以成8个元素大小的区间；

　　所以我们可以将其分为[3,10]和[4,11]两个区间；（分成的两个区间一个是从开头取八个，一个是从最后往前取八个）

　　然后通过求这两个区间最大值中的较大值得到3到11之间的最大值

抽象成一个广义数学问题：

　　求[i,j]区间最大值；

　　num = j-i+1; p = 2^((int)(log2(num)));

　　rmq(i,j) = max( st[i][p], st[i-2^p+1][p] )

　　num：[i,j]区间元素个数，p：[i,j]区间可以连续分成的最大2^n区间的大小

　　rmq(i,j)：查询[i,j]区间最大值

rmq查询代码：

int rmq( int le, int ri ) {  //le为查询区间开始位置，ri为查询区间结束位置    int p = log2(ri-le+1);    return max(st[le][p],st[ri-(1<

参考博客：https://blog.csdn.net/z287438743z/article/details/8132806

例题：

题目背景

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

请注意最大数据时限只有0.8s，数据强度不低，请务必保证你的每次查询复杂度为

题目描述

给定一个长度为

输入输出格式

输入格式：

第一行包含两个整数

第二行包含

接下来

输出格式：

输出包含

输入输出样例

输入样例

8 89 3 1 7 5 6 0 81 61 52 72 61 84 83 71 8

输出样例

99779879

说明

对于30%的数据，满足：

对于70%的数据，满足：

对于100%的数据，满足： $1≤N≤105,1≤M≤106,ai∈[0,10^9],1≤li≤ri≤N$

$st[i][j]表示以第i个数为首的一共2^j个数的最大值$

if( j == 1 ) {    st[i][j] = a[i]} else {    st[i][j] = max( st[i][j-1], st[i+(1<<(j-1))][j-1] );}

AC代码：

#include #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #define ls (r<<1)#define rs (r<<1|1)#define debug(a) cout << #a << " " << a << endlusing namespace std;typedef long long ll;const ll maxn = 1e5+10;const ll mod = 998244353;const double pi = acos(-1.0);const double eps = 1e-8;ll st[maxn][20]; //ll表示long long,个人习惯整数定义成long longvoid cal_st( ll n, ll a[] ) { for( ll i = 1; i <= n; i ++ ) { st[i][0] = a[i]; } for( ll j = 1; j <= log2(n); j ++ ) { for( ll i = 1; i <= n-(1<