RMQ-ST表
2019-07-24 本文已影响0人
雨落八千里
以前学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;
}