博客

对于数组A[i] ，现要求下标l 到 r 的最值。

这是很常见的题目。

其解决方法也有很多，这两天重新学习了一下，终于更明白了。

方法之一：

朴素算法（搜索）：也就是一个一个看。。。。

对于某一次求复杂度最大为O(N) q 次的话那就是O（qN）了

好大。。

//对于minn同理
int maxn=-inf;
for(int i=l ;i<=r ;i++)
{
  if(maxn<a[i])maxn = a[i];
}
printf("%d",maxn);

方法二

：线段树

时间复杂度O（qlogn） 额还好

用线段树来解决区间最值问题是很经典的 就不多赘述了

#include <cstdio>
#include <algorithm>
using namespace std;

#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int maxn = 10000;
int MAX[maxn<<2];

void PushUP(int rt) {
    MAX[rt] = max(MAX[rt<<1] , MAX[rt<<1|1]);
}
void build(int l,int r,int rt) {
    if (l == r) {
        scanf("%d",&MAX[rt]);
        return ;
    }
    int m = (l + r) >> 1;
    build(lson);
    build(rson);
    PushUP(rt);
}
int query(int L,int R,int l,int r,int rt) {
    if (L <= l && r <= R) {
        return MAX[rt];
    }
    int m = (l + r) >> 1;
    int ret = 0;
    if (L <= m) ret = max(ret , query(L , R , lson));
    if (R > m) ret = max(ret , query(L , R , rson));
    return ret;
}

int main(){
 int n,m;
 scanf("%d%d",&n,&m); // n 是长度    m是查询次数 
 build(1, n, 1);
 while(m--){
   int a,b;
   scanf("%d%d",&a,&b);
   printf("%d\n",query(a , b , 1 , n , 1)); 
 }
 return 0;
}

方法三：


RMQ 之ST 算法

O(nlogn)时间内进行预处理，然后在O(1)时间内回答每个查询。

实质上这是一个动态规划

F[1，0]表示第1个数起，长度为2^0=1的最大值

f[i][j] 从 i 长度为2^j 即 1<

void rmqst(int n){
  for(int j=1;j<=20 ;j++)     //注意顺序!!!!!
    for(int i=1 ;i<=n ;i++)
  {if((i+(1<<j)-1) <=n)
     {
       maxsum[i][j] = max(maxsum[i][j - 1], maxsum[i + (1 << (j - 1))][j - 1]);  //最大
       minsum[i][j] = min(minsum[i][j - 1], minsum[i + (1 << (j - 1))][j - 1]); //最小
     }
  }  
}

先更新所有长度为F[i,0]即1个元素，然后通过2个1个元素的最值，

获得所有长度为F[i,1]即2个元素的最值，然后再通过2个2个元素的最值，获得所有长度为

F[i,2]即4个元素的最值，以此类推更新所有长度的最值。

然后查询

对于区间为【i,j】

最值maxn = max(maxsum[l,k], maxsum[r-2^k+1,k])

k是满足2^k<=r-l+1(即长度)的最大的k,即（int）k=(b-a+1)/log（2.0）。

int maxx,minn;
int k = (int)((log(r-l+1))/log(2.0));
   maxx = max(maxsum[l][k] , maxsum[r - (1<<k) +1][k]); 
   minn = min(maxsum[l][k] , maxsum[r - (1<<k) +1][k]); 

我觉得其实上面的方法就够了

下面这个感觉都好麻烦，没用过。。。。

方法四：

先规约成LCA（Lowest Common Ancestor），再规约成约束RMQ。

首先根据原数列，建立笛卡尔树，从而将问题在线性时间内规约为LCA问题。LCA问题可以在线性时间内规约为约束RMQ，也就是数列中任意两个相邻的数的差都是+1或-1的RMQ问题。