RMQ-ST表

以前学RMQ的时候完全不懂，最近写到了类似的题，在看了几篇博客，加上以前整理的笔记，才加深了对RMQ算法的理解。

RMQ

• ，即区间最值查询，是指这样一个问题：对于长度为n的数列A，回答若干询问RMQ（A,i,j）(i,j<=n),返回 [ A[i]~A[j] ] 中的最值。

ST

• ST算法（Sparse Table），ST（Sparse Table）算法是一个非常有名的在线处理RMQ问题的算法，它可以在O(nlogn)时间内进行预处理，然后在O(1)时间内回答每个查询。

• A[i][j]:表示从第i个数起连续2^j个数中的最值状态
  转移方程:A[i, j]=max/min（ A [ i ][ j - 1 ] , A [ i + ( 1 << ( j - 1 ) ) ][ j - 1 ]；
  A[i][j-1]:表示第i个数连续的2^(j-1)个数；
  A[i+ (1<< (j-1) ) ][j-1]：表示第(i+2^(j-1))个数起连续的2^(j-1)个数；
  A[i][j]维护的区间是[i,i+2^j-1]，但在过程中将区间分成了前一半和后一半。

每一个区间[ l , r ]都可以被这种类似的区间所表达。我们假设[ l , r ]中 r-l+1 , 也就是区间的长度能用2^k-1所表示，也就是说我们这个区间的最值就是的最值，也就是所记录的值！
但是万一区间并不能用所表示呢？不必担心，先告诉你们可以用区间和这两个区间的最值 取最值！为什么呢？看：

红区间的最值一定是两个黑区间的最值的并集！因为重合部分分别与两边非重合部分的最值　的最值　也就是整个红区间（询问区间）的最值！

令
维护的是：
维护的是 ：

那么我们只要保证
就能保证


因为



显然成立

Balanced Lineup
求区间的最大值和最小值

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
const int M=1000100;
int minx[M][30];
int maix[M][30];
int n,q,x,y;
void ST(int n)
{
    for(int j=1;j<=25;j++)
    {
        for(int i=1;i+(1<<j)-1<=n;i++)
        {
            maix[i][j]=max(maix[i][j-1],maix[i+(1<<(j-1))][j-1]);
            minx[i][j]=min(minx[i][j-1],minx[i+(1<<(j-1))][j-1]);
        }
    }
}
void query(int i,int j)
{
    int k=log2(j-i+1.0);
    int ans1=min(minx[i][k],minx[j-(1<<k)+1][k]);
    int ans2=max(maix[i][k],maix[j-(1<<k)+1][k]);
    printf("%d\n",ans2-ans1);
    return ;
}
int main( )
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        minx[i][0]=maix[i][0]=x;
    }
    ST(n);
    while(q--)
    {
        scanf("%d%d",&x,&y);
        query(x,y);
    }
    return 0;

}