# RMQ 模板

# 一、RMQ 简介

中文全名为区间最值查询，有人说区间最值不就循环扫一遍就出来了吗，好想法。但是，如果区间长度为 100000 以上而且需要连续查询 m 次呢

显然你会看到满屏的 <font color="#ffc116" size="6">TLE</font>，谁不喜欢绿色的 < font color="#52a41a" size="6">AC</font > 呢？所以 RMQ 算法就是把黄色绿掉的算法

RMQ 算法一般预处理时间较长，时间复杂度为$O(nlogn)$, 但查询速度很快，只需要$O(1)$，$RMQ$ 本质上还是用到了倍增的思想，记录连续$2^j$ 个数的最值，因此提高查找效率

# 二、例题及代码

例题：忠诚

Code:

#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int N=100001;
int z[N][20];
int n,m;
int count1(int x)
{
    int need=1;
    for(int i=0;i<x;i++)
        need=need*2;
    return need;
}
void create(int n)
{
    for(int i=1;count1(i)<=n;i++)
    {
        for(int j=1;j+count1(i)-1<=n;j++)
            z[j][i]=min(z[j][i-1],z[j+(1<<(i-1))][i-1]);
    }
    return;
}
int work(int l,int r)
{
    int t=(int)(log((r-l+1)*1.0)/log(2.0));
    return min(z[l][t],z[r-(1<<t)+1][t]);
}
int main()
{
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++)
        scanf("%d",&z[i][0]);
    create(m);
    for(int i=1;i<=n;i++)
    {
        int a,b;
        scanf(" %d %d",&a,&b);
        printf("%d ",work(a,b));
    }
    return 0;
}

具体算法原理请移步另一篇文章