RMQ (Range Minimum/Maximum Query)问题是指：对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j<=n)，返回数列A中下标在i,j里的最小(大）值，也就是说。RMQ问题是指求区间最值的问题。

Submit Status

6 3

1

7

3

4

2

5

1 5

4 6

2 2

6

3

0

1.朴素（遍历）： 复杂度O(n)-O(qn)。

2.线段树 ：复杂度O(n)-O(qlogn)。

3.ST（Sparse Table）算法 ：O(nlogn)-O(q)

说下ST算法，由于每一个查询仅仅有O(1)。在处理大量查询的时候有优势。

<1>.预处理（动态规划DP）

对A[i]数列，F[i][j] 表示从第i个数起连续2^j 中的最大值(DP的状态)，能够看到，F[i][0] 表示的是A[i]（DP的初始值）。

最后。状态转移方程是

F[i][j]=max(F[i][j-1],F[i+2^(j-1)][j-1])

<2>查询

若查询区间为（a。b），区间长度为b-a+1，取k=log2(b-a+1)，则Max（a。b）=max（F[a][k]。F[b-2^k+1][k]）。

1.ST算法

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstring>

#include<cmath>

#define max(a,b) (a>b?a:b)

#define min(a,b) (a<b?a:b)

using namespace std;

const int MAXN = 50050;

int mins[MAXN][20];

int maxs[MAXN][20];

void RMQ(int n)

{

	for (int j = 1; (1 << j) <= n;j++)

	for (int i = 1; i + (1 << j) - 1 <= n; i++)

	{

		int p = (1 << (j - 1));

		mins[i][j] = min(mins[i][j - 1], mins[i + p][j - 1]);

		maxs[i][j] = max(maxs[i][j - 1], maxs[i + p][j - 1]);

	}

}

int queryMin(int l, int r)

{

	int k = log((double)(r - l + 1))/log(2.0);

	return min(mins[l][k], mins[r - (1 << k) + 1][k]);

}

int queryMax(int l, int r)

{

	int k = log((double)(r - l + 1))/log(2.0);

	return max(maxs[l][k], maxs[r - (1 << k) + 1][k]);

}

int main()

{

	int n, q;

	scanf("%d%d", &n, &q);

	int num;

	for (int i = 1; i <= n; i++)

	{

		scanf("%d", &num);

		maxs[i][0] = mins[i][0] = num;

	}

	RMQ(n);

	int a, b;

	int ans;

	for (int i = 0; i < q; i++)

	{

		scanf("%d%d", &a, &b);

		ans= queryMax(a, b) - queryMin(a, b);

		printf("%d\n", ans);

	}

}

2.线段树

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#define max(a,b) (a>b?a:b)

#define min(a,b) (a<b?a:b)

using namespace std;

const int MAXN = 50050;

int num[MAXN];

struct node

{

	int r;

	int l;

	int Max;

	int Min;

}tree[3*MAXN];

void build(int l, int r, int i)

{

	tree[i].l = l; tree[i].r = r;

	if (l == r)

	{

		tree[i].Max = tree[i].Min = num[l];

		return;

	}

	int m = (l + r) >> 1, ls = i << 1, rs = ls + 1;

	build(l, m, ls);

	build(m + 1, r, rs);

	tree[i].Max = max(tree[rs].Max, tree[ls].Max);

	tree[i].Min = min(tree[rs].Min, tree[ls].Min);

}

int queryMax(int l, int r, int i)

{

	if (tree[i].l == l&&tree[i].r == r)

		return tree[i].Max;

	int m = (tree[i].l + tree[i].r) >> 1, ls = i << 1, rs = ls + 1;

	if (r <= m) return queryMax(l, r, ls);

	else if (l > m) return queryMax(l, r, rs);

	else return max(queryMax(l, m, ls), queryMax(m + 1, r, rs));

}

int queryMin(int l, int r, int i)

{

	if (tree[i].l == l&&tree[i].r == r)

		return tree[i].Min;

	int m = (tree[i].l + tree[i].r) >> 1, ls = i << 1, rs = ls + 1;

	if (r <= m) return queryMin(l, r, ls);

	else if (l > m) return queryMin(l, r, rs);

	else return min(queryMin(l, m, ls), queryMin(m + 1, r, rs));

}

int  main()

{

	int n, q;

	scanf("%d%d", &n, &q);

	for (int i = 1; i <= n; i++)

		scanf("%d", &num[i]);

	build(1, n, 1);

	int a, b;

	int ans;

	for (int i = 0; i < q; i++)

	{

		scanf("%d%d", &a, &b);

		ans = queryMax(a, b, 1) - queryMin(a, b, 1);

		printf("%d\n", ans);

	}

}

參考了http://blog.csdn.net/niushuai666/article/details/6624672/