视频大法好：https://www.bilibili.com/video/av18735440?from=search&seid=13498212845468537633qew

模板：

O(nlogn)预处理，O(1)查询。空间O(nlogn)。

int d[1000006][25];//预处理得到的dp[i][j]表示从第i位开始长度为2^j当中最小的值
int mn[1000006];//预处理出比每个数小的最大的2^i的数字以便查询
void rmq_init()
{
    for(int i=1;i<=n;i++)
        d[i][0]=a[i];
    for(int j=1;(1<<j)<=n;j++)
      for(int i=1;i+(1<<j)-1<=n;i++)
        d[i][j]=min(d[i][j-1],d[i+(1<<(j-1))][j-1]);
    for(int len=1;len<=n;++len){
        int k=0;
        while((1<<(k+1))<=len)
            k++;
        mn[len]=k;
    }
}
int rmq(int L,int R)
{
    int k=mn[R-L+1];
    return min(d[L][k],d[R-(1<<k)+1][k]);
}