題目大意：給出一串數(shù)字蘸炸，然后給出一個區(qū)間a b，輸出從a到b的最大的數(shù)和最小的數(shù)的差尖奔。
N（1 ≤ N ≤ 50000）, Q（1 ≤ Q ≤ 200000）搭儒；N為數(shù)字個數(shù)穷当，1 ≤每個數(shù) ≤ 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];//存儲線段樹的全局數(shù)組
int n;
//////初始化
void init(int N) {
n = 1;
while (n < N) n <<= 1;//簡單起見铃岔，把元素個數(shù)擴大到2的冪
for (int i = 0; i < 2 * n - 1; ++i) {
dat[i].first = INF;//存儲區(qū)間最小值
dat[i].second = -INF;//存儲區(qū)間最大值
}
}
//把第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是節(jié)點編號
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）毁习。
-
稀疏表
實質為動態(tài)規(guī)劃智嚷。
預處理: 預處理是采用dp的思想，用f[i][j]表示區(qū)間[i,i+2j-1]中的最大值(即從i開始纺且，長度為2j的閉區(qū)間)盏道。開始時，f[i][0] 就是區(qū)間[i][i]的值载碌，即f[i][0] = num[i]猜嘱，好了，初始值找到了嫁艇，下面是狀態(tài)轉移方程：f[i][j] = max (f[i][j-1],f[i+2(j-1)][j-1])朗伶。即把[i,i+2j-1]區(qū)間分為[i,i+2(j-1)-1]和[j+2(j-1),j+2(j-1)+2(j-1)-1]兩個等長度的區(qū)間(區(qū)間長度都是2^(j-1))，有了初始值和狀態(tài)轉移方程步咪，我們可以自底向上遞推出所有的f[i][j]的值论皆。
邊界值的處理: 由于區(qū)間最大長度為n，所以二維邊界最大值為log(n)/log(2.0)猾漫；一維邊界為i+2^j-1<=n纯丸。
查詢： 假設要查詢區(qū)間[a,b]的最大值，由于區(qū)間的長度很可能不是2的整數(shù)冪静袖，所以我們要把區(qū)間劃分為長度為2的整數(shù)冪的兩部分觉鼻，而且這兩個的并集必須是[a,b]。為了實現(xiàn)這個方案队橙，我們需要先求出一個最大k坠陈，使得2k<=(b-a+1)，這樣就可以把區(qū)間分為兩部分[a捐康，a+2k-1]和[b-2^k+1,b]仇矾，使它們既能不超過[a,b]區(qū)間的范圍，又能把區(qū)間全部覆蓋解总。于是贮匕，[a,b]區(qū)間的最大值就等于上述兩個區(qū)間的最大值中最大的那個。
#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)的預處理以后實現(xiàn)O(1)的查詢效率花枫，從而解決了數(shù)很多(如大于100萬)的RMQ問題刻盐√透啵基于ST的RMQ在預處理時的時間復雜度和空間復雜度都達到了O（nlogn）,與線段樹的RMQ相比，無法高效地對值進行更新敦锌。
參考資料：http://blog.csdn.net/xiao_niu_1/article/details/7393196
