（RMQ）Range Minimum/Maximum Query

RMQ适用范围：给定区间，求最值。

RMQ最大值图示

预处理（构造）：
对于第0行：存取范围为j~j的数字（本身）
对于第1行：存取范围为j~j+2^i-1的最大值（范围为2）
dp[i][j]=max（dp[i-1][j]，dp[i-1][j+(2^(i-1))]）
对于第2行：存取范围为j~j+2^i-1的最大值（范围为4）
dp[i][j]=max（dp[i-1][j]，dp[i-1][j+(2^(i-1))]）
对于第3行：存取范围为j~j+2^i-1的最大值（范围为8）
dp[i][j]=max（dp[i-1][j]，dp[i-1][j+(2^(i-1))]）

void RMQ(int n)
{
    int i, j;
    for(i=1; (1<<i)<=n; i++)
    {
        for(j=1; (j+(1<<(i-1)))<=n; j++)
        {
            dp[i][j]=max(dp[i-1][j],dp[i-1][j+(1<<(i-1))]);
        }
    }
}

询问：

int Find(int l, int r)
{
    int k=0;
    while((1<<(k+1)) <= (r-l+1)) k++;
    return max(dp[k][l],dp[k][r-(1<<k)+1]);
}

例题：https://vjudge.net/contest/160175#problem/O
输入n个数字，m个询问，每个询问给定区域l，r输出该区域的最小值。

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

int dp[21][1000005];
void RMQ(int n)
{
    int i, j;
    for(i=1; (1<<i)<=n; i++)
    {
        for(j=1; (j+(1<<(i-1)))<=n; j++)
        {
            dp[i][j]=min(dp[i-1][j],dp[i-1][j+(1<<(i-1))]);
        }
    }
}

int Find(int l, int r)
{
    int k=0;
    while((1<<(k+1)) <= (r-l+1)) k++;
    return min(dp[k][l],dp[k][r-(1<<k)+1]);
}

int main()
{
    int i, n, m, l, r;
    scanf("%d", &n);
    for(i=1; i<=n; i++)
        scanf("%d", &dp[0][i]);
    RMQ(n);
    scanf("%d", &m);
    for(i=1; i<=m; i++)
    {
        scanf("%d%d", &l, &r);
        printf("%d\n", Find(l, r));
    }
    return 0;
}