poj3264（区间最值问题RMQ）

题目大意：给出一串数字，然后给出一个区间a b，输出从a到b的最大的数和最小的数的差。

N(1 ≤ N ≤ 50000), Q(1 ≤ Q ≤ 200000)；N为数字个数，1 ≤每个数 ≤ 1,000,000。。。如：
输入：
6 3
1
7
3
4
2
5
1 5
4 6
2 2
输出：
6
3
0

解题方法：用线段树和稀疏表均可以做。

• 线段树

#include <cstdio>
#include <algorithm>
using namespace std;
///
const int MAX_N = 5e4 + 5;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> P;
///
P dat[4 * MAX_N];//存储线段树的全局数组
int n;
//初始化
void init(int N) {n = 1;while (n < N) n <<= 1;//简单起见，把元素个数扩大到2的幂for (int i = 0; i < 2 * n - 1; ++i) {dat[i].first = INF;//存储区间最小值dat[i].second = -INF;//存储区间最大值}
}
//把第k个值更新为x
void update(int k, int x) {k += n - 1;dat[k] = P(x, x);while (k > 0) {//向上更新k = (k - 1) / 2;dat[k].first = min(dat[2 * k + 1].first, dat[2 * k + 2].first);dat[k].second = max(dat[2 * k + 1].second, dat[2 * k + 2].second);}
}
//查询
P query(int a, int b, int k, int l, int r) {//k是节点编号if (a <= l && r <= b) return dat[k];if (a > r || b < l) return P(INF, -INF);P vl = query(a, b, 2 * k + 1, l, (l + r) / 2);P vr = query(a, b, 2 * k + 2, (l + r) / 2 + 1, r);return P(min(vl.first, vr.first), max(vl.second, vr.second));
}
int main() {int N, Q;scanf("%d%d", &N, &Q);init(N);for (int i = 0; i < N; ++i) {int x;scanf("%d", &x);update(i, x);}for (int i = 0; i < Q; ++i) {int a, b;scanf("%d%d", &a, &b);P p = query(a - 1, b - 1, 0, 0, n - 1);printf("%d\n", p.second - p.first);}return 0;
}

n个元素的线段树的初始化的时间复杂度和空间复杂度都是O(n)，对于n个元素，每一次操作的复杂度是O(logn)。

• 稀疏表
  实质为动态规划。

预处理: 预处理是采用dp的思想，用f[i][j]表示区间[i,i+2^{j-1]中的最大值(即从i开始，长度为2}j的闭区间)。开始时，f[i][0] 就是区间[i][i]的值，即f[i][0] = num[i]，好了，初始值找到了，下面是状态转移方程：f[i][j] = max (f[i][j-1],f[i+2^{(j-1)][j-1])。即把[i,i+2}j-1]区间分为[i,i+2^{(j-1)-1]和[j+2}(j-1),j+2^(j-1)+2(j-1)-1]两个等长度的区间(区间长度都是2^(j-1))，有了初始值和状态转移方程，我们可以自底向上递推出所有的f[i][j]的值。边界值的处理: 由于区间最大长度为n，所以二维边界最大值为log(n)/log(2.0)；一维边界为i+2^j-1<=n。查询： 假设要查询区间[a,b]的最大值，由于区间的长度很可能不是2的整数幂，所以我们要把区间划分为长度为2的整数幂的两部分，而且这两个的并集必须是[a,b]。为了实现这个方案，我们需要先求出一个最大k，使得2^{k<=(b-a+1)，这样就可以把区间分为两部分[a，a+2}k-1]和[b-2^k+1,b]，使它们既能不超过[a,b]区间的范围，又能把区间全部覆盖。于是，[a,b]区间的最大值就等于上述两个区间的最大值中最大的那个。

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
//
const int INF = 0x3f3f3f3f;
const int MAX_N = 5e4 + 5;
typedef pair<int, int> P;
/
int num[MAX_N];
P dp[MAX_N][20];
void init(int n) {int k = (int)(log(n) / log(2.0));for (int i = 0; i < n; ++i)for (int j = 0; j <= k; ++j) {dp[i][j].first = INF;dp[i][j].second = -INF;}       
}
void creat(int n) {for (int i = 0; i < n; ++i)dp[i][0].first = dp[i][0].second = num[i];int k = (int)(log(n) / log(2.0));for (int j = 1; j <= k; ++j)for (int i = 0; i + (1 << j) - 1 < n; ++i) {dp[i][j].first = min(dp[i][j - 1].first, dp[i + (1 << (j - 1))][j - 1].first);dp[i][j].second = max(dp[i][j - 1].second, dp[i + (1 << (j - 1))][j - 1].second);}
}
P query(int s, int e) {int k = (int)(log(e - s + 1) / log(2.0));return P(min(dp[s][k].first, dp[e - (1 << k) + 1][k].first), max(dp[s][k].second, dp[e - (1 << k) + 1][k].second));
}
int main() {int N, Q;scanf("%d%d", &N, &Q);for (int i = 0; i < N; ++i)scanf("%d", &num[i]);init(N);creat(N);for (int i = 0; i < Q; ++i) {int a, b;scanf("%d%d", &a, &b);P p = query(a - 1, b - 1);printf("%d\n", p.second - p.first);}return 0;
}

Sparse Table 算法可以在O(nlogn)的预处理以后实现O(1)的查询效率，从而解决了数很多(如大于100万)的RMQ问题。基于ST的RMQ在预处理时的时间复杂度和空间复杂度都达到了O(nlogn),与线段树的RMQ相比，无法高效地对值进行更新。
参考资料：http://blog.csdn.net/xiao_niu_1/article/details/7393196