RMQ区间最值

古城微笑少年丶 2021-09-20 10:02 273阅读 0赞

# 前言 #

区间最值问题就是一类求一段区间的最大值或者最小值的问题(好像是废话。。。)，有时候区间很大，

比如\[1~100000000\]，这样的长度，暴力是肯定不行的，所以这个时候就必须用更高效的算法来解决问题。

高级写法有两种解决方法：

一种是ST表，另一种是线段树。

这里只给出ST算法的形式，适合于静态区间，如果要求动态区间，那就老老实实线段树。

# ST表 #

此算法是基于dp思想的一种解法

## 定义 ##

**dp( i,j )**表示从第**i**位到第**i+2j-1**位这个**2**j长度的区间的最大值

## 预处理 ##

**dp( i, 0 )**表示区间**\[ i, i \]**，所以初始化为**a\[i\]**，表示区间**\[ i, j \]**的最大值为**a\[ i \]**

## **递推式** ##

将长度为2j的区间分为两段长度为2j-1的区间，也就是\[i,i+2j-1\-1\]和\[i+2j-1,i+2j\-1\]两个区间，然后选取两个区间的最值。

**dp( i,j )**=**max(dp( i, j-1 ),dp( i+2j-1, j-1 )**

**注意：上式圆括号后面都是 j-1,是因为i+2j-1\+2j-1\-1 = i+2j\-1    ! ! !**

## **建立代码** ##

1 //创建RMQ 
     2 void RMQ(int n){ 3     init(n);//初始化dp[i,0] 4     //使用了左移符号 
     5     for(int j=1;(1<<j)<=n;j++){ 6         for(int i=1;i+(1<<j)-1<=n;i++){ 7             dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]); 8 } 9 } 10 }

注意外部循环从j开始， 因为初始状态为dp\[i\]\[0\], 以 i 为外层会有一些状态遍历不到。

## 查询过程 ##

![1687284-20190612200931206-1224784625.png][]

如上图，一个区间为**\[ l, r \]**，长度为 **r-l+1**，将其转化为**2k**这种形式

也就是**k=log2(r-l+1)**，那么就可以把原区间分成两个部分**\[l,l+2k-1\-1\]**和**\[l+2k-1,r\]**

**dp( l, r )=dp(l,k-1),dp(l+2k-1,k-1)**

然而，由于log是向下取整，所以2k可能小于r-l-1，所以要用"两边夹"的方法来实现区间分离,如上图

则分开的区间为**\[l,i+2k\-1\]**和**\[r-2k\+1,r\]，**并不需要担心重复，毕竟是求最值

也就是：

**dp( l, r )=max(dp( l, k ),dp(r-2k\+1,k))**

## **最终代码** ##

1 #include<iostream>
     2 #include<cmath>
     3 using namespace std; 4 const int maxn=200; 5 int dp[maxn][maxn]; 6 //快速写入 
     7 inline int read(){ 8     int w=0,f=1; 9     char ch=getchar(); 10     while(ch<'0'||ch>'9'){ 11         if(ch=='-') f=-1; 12         ch=getchar(); 13 } 14     while(ch>='0'&&ch<='9'){ 15         w=(w<<3)+(w<<1)+ch-48; 16         ch=getchar(); 17 } 18     return w*f; 19 } 20 //初始化 
    21 inline void init(int n){ 22     for(int i=1;i<=n;i++){ 23         dp[i][0]=read(); 24 } 25 } 26 //创建RMQ 
    27 void RMQ(int n){ 28 init(n); 29     //使用了左移符号 
    30     for(int j=1;(1<<j)<=n;j++){ 31         for(int i=1;i+(1<<j)-1<=n;i++){ 32             dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]); 33 } 34 } 35 } 36 int main(){ 37     int n=read(); 38 RMQ(n); 39     int l=read(); 40     int r=read(); 41     //查询 
    42     int k=log2(r-l+1); 43     printf("%d",max(dp[l][k],dp[r-(1<<k)+1][k])); 44     return 0; 45 }

转载于:https://www.cnblogs.com/lastonepersonwhohavebitenbycompanies/p/11011967.html

[1687284-20190612200931206-1224784625.png]: /images/20210726/d25da9e185ea4d9686d4807a4d59367a.png