RMQ学习笔记

定义

  RMQ问题是指：对于长度为 n 的数列 A，回答若干询问 RMA（A，i，j）（i，j<=n），返回数列 A中下标在 i，j 里的最小（大）值，也就是说，RMQ问题是指区间内的最值问题。

主要算法及复杂度

1. 爆搜，O(n) ~ O(qn)
2. 线段树，O(n) ~ O(qlogn)
3. ST（实质是动态规划），O(nlogn) ~ O(q)
4. RMQ标准算法：先规约成LCA，再规约成RMQ，O(n) ~ O(q)

ST算法

  爆搜和线段树不多说了，相信大家都很熟悉；
  ST算法，以求最大值为例，设 dp[i][j] 表示 [i,i+2^j-1] 这个区间内的最大值，那么查询到 [a,b] 区间的最大值时，答案就是 max(dp[a][k],dp[b-2^k+1][k])，其中 k 满足 2^k <= b-a+1（即长度），即 k = ln(b-a+1) / ln2。
  转移方程的话：dp[i][j] = max(d[i][j-1],d[i+2^j-1][j-1]).
  O(nlogn)的预处理，O(1)地回答每个询问。

void get_RMQ()
{
    
    for(int j=1;j<20;j++){
    
        for(int i=1;i+(1<<j)-1<=n;i++){
    
            ma[i][j]=max(ma[i][j-1],ma[i+(1<<(j-1))][j-1]);
            mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]);
        }
    }
}

for(int i=1;i<=n;i++){
    
	cin>>num;
    ma[i][0] = mi[i][0] = num;    
}
get_RMQ();
while(q--){
    
	int l,r;
	cint<<l<<r;
	if(l>r) swap(l,r);
	int x = log(double(r-l+1)) / log(2.0);
	int _min = min(mi[l][x],mi[r-(1<<x)+1][x]);
  	int _max = max(ma[l][x],ma[r-(1<<x)+1][x]);
 	cout<<_min<<' '<<_max<<endl;
 }

以最大值为例，说一下 ST 算法是怎么实现的：

1. 预处理：我们设 dp[i][j] 表示 [i,i+2^j-1] 这个区间内的最大值，也就是从第 i 个数起连续 2^j 个数中的最大值，那么dp[i][0]就表示第 1 个数起，长度 2⁰ = 1 的最大值，其实就是 num[i]。
2. 状态转移方程：我们把 dp[i][j]（j>=1）平均分成两段（因为 j>=1 时，dp[i][j]一定是偶数个数字），从而我们把 dp[i][j]（j>=1）平均分成两段，从 i 到 i+2^j-1-1 为一段，i+2^j-1 到 i+2^j-1 为一段（长度都为 2^j-1）。dpj就是这两段的最大值的最大值，于是我们得到动态方程：dp[i][j] = max(d[i][j-1],d[i+2^j-1][j-1])。

例题：http://poj.org/problem?id=3264、
Description

For the daily milking, Farmer John’s N cows (1 ≤ N ≤ 50,000) always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of the cows. To keep things simple, he will take a contiguous range of cows from the milking lineup to play the game. However, for all the cows to have fun they should not differ too much in height.

Farmer John has made a list of Q (1 ≤ Q ≤ 200,000) potential groups of cows and their heights (1 ≤ height ≤ 1,000,000). For each group, he wants your help to determine the difference in height between the shortest and the tallest cow in the group.

Input

Line 1: Two space-separated integers, N and Q.
Lines 2…N+1: Line i+1 contains a single integer that is the height of cow i
Lines N+2…N+Q+1: Two integers A and B (1 ≤ A ≤ B ≤ N), representing the range of cows from A to B inclusive.
Output

Lines 1…Q: Each line contains a single integer that is a response to a reply and indicates the difference in height between the tallest and shortest cow in the range.
Sample Input

6 3
1
7
3
4
2
5
1 5
4 6
2 2
Sample Output

6
3
0

题意

  找寻序列区间[l,r]的max，min，输出 max-min。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
#include<ctime>
#define ll long long
#define ld long double
#define ull unsigned long long
using namespace std;
const int maxn = 50010;
const int inf = 0x3f3f3f3f3f;
const ll lnf = 0x3f3f3f3f3f3f3f;
int ma[maxn][20],mi[maxn][20];
int num,n,q;
void get_RMQ()
{
    
    for(int j=1;j<20;j++){
    
        for(int i=1;i+(1<<j)-1<=n;i++){
    
            ma[i][j]=max(ma[i][j-1],ma[i+(1<<(j-1))][j-1]);
            mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]);
        }
    }
}
int main(void)
{
    
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++){
    
        scanf("%d",&num);
        ma[i][0] = mi[i][0] = num;
    }
    get_RMQ();
    while(q--){
    
        int l,r;
        scanf("%d%d",&l,&r);
        if(l>r) swap(l,r);
        int x = log(double(r-l+1)) / log(2.0);
        int _min = min(mi[l][x],mi[r-(1<<x)+1][x]);
        int _max = max(ma[l][x],ma[r-(1<<x)+1][x]);
        printf("%d\n",_max-_min);
    }
    return 0;
}