RMQ

RMQ是指的是求静态的区间最小值，用暴力可以达到O(n)-O(n)的时间复杂度（O(F1(n))-O(F2(n))指的是用O(F1(n))的时间进行预处理，用O(F2(n))的时间进行1次查询）。可以用线段树做到O(n)-O(logn)，具体的过程略去。

这里推荐的是ST算法，可以做到O(nlogn)-O(1)的复杂度。

可以用动态规划的思想解决：设f[i][j]表示从i开始长度为2^j的序列中的最小值，则Dp方程不难求出：

但是如果需要查询的区间长度不是2的幂次方呢？

设查询的区间为[l,r]，则我们不难得出：

那么这样就可以实现RMQ了。

程序如下：

#include <cstdio>
#include <iostream>
#include <cmath>

using namespace std;

int a[100010];
int f[100010][20];
int x,y;
int n;

void Init_RMQ()
{
	for(int i=1;i<=n;i++) f[i][0] = a[i];
	for(int j=1;(1<<j)<=n;j++)//预处理 
	{
		for(int i=1;i+(1<<j)-1<=n;i++)
		{
			f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
		}
	}
}

int Ask_RMQ(int x,int y)
{
	if(x>y) swap(x,y);
	int k = log(y-x+1.0) / log(2.0);
	return min(f[x][k],f[y-(1 << k )+1][k]);
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);//输入序列 \
	
	while(scanf("%d%d",&x,&y) && x && y)
		printf("%d\n",Ask_RMQ(x,y));
	
	return 0;
}

我们还可以用笛卡尔树，将RMQ转换为LCA查询，然后用+-1RMQ实现O(n)-O(1)的做法。