RMQ算法 NYOJ-119 士兵杀敌（三）
描述
南将军统率着N个士兵，士兵分别编号为1~N,南将军经常爱拿某一段编号内杀敌数最高的人与杀敌数最低的人进行比较，计算出两个人的杀敌数差值，用这种方法一方面能鼓舞杀敌数高的人，另一方面也算是批评杀敌数低的人，起到了很好的效果。
所以，南将军经常问军师小工第i号士兵到第j号士兵中，杀敌数最高的人与杀敌数最低的人之间军功差值是多少。
现在，请你写一个程序，帮小工回答南将军每次的询问吧。
注意，南将军可能询问很多次。
输入
只有一组测试数据
第一行是两个整数N,Q，其中N表示士兵的总数。Q表示南将军询问的次数。(1<N<=100000,1<Q<=1000000)
随后的一行有N个整数Vi(0<=Vi<100000000)，分别表示每个人的杀敌数。
再之后的Q行，每行有两个正正数m,n，表示南将军询问的是第m号士兵到第n号士兵。
输出
对于每次询问，输出第m号士兵到第n号士兵之间所有士兵杀敌数的最大值与最小值的差。
样例输入
5 2
1 2 6 9 3
1 2
2 4
样例输出
1
7
概述
RMQ（Range Minimum/Maximum Query），即区间最值查询，是指这样一个问题：对于长度为n的数列A，回答若干询问RMQ（A,i,j）(i,j<=n)，返回数列A中下标在i，j之间的最小/大值。这两个问题是在实际应用中经常遇到的问题，当然，该问题也可以用线段树（也叫区间树）解决，算法复杂度为：O(N)~O(logN)
如果只有一次询问，那样只有一遍for就可以搞定，但是如果有许多次询问就无法在很快的时间处理出来。
这是一种在线算法。所谓在线算法，是指用户每输入一个查询便马上处理一个查询。该算法一般用较长的时间做预处理，待信息充足以后便可以用较少的时间回答每个查询。
O(nlogn)时间内进行预处理，然后在O(1)时间内回答每个查询。
首先是预处理，用动态规划（DP）解决。
设A[i]是要求区间最值的数列，F[i, j]表示从第i个数起连续2^j个数中的最大值。（DP的状态）
例如：
A数列为：3 2 4 5 6 8 1 2 9 7
F[1，0]表示第1个数起，长度为2^0=1的最大值，其实就是3这个数。同理 F[1,1] = max(3,2) = 3, F[1，2]=max(3,2,4,5) = 5，F[1，3] = max(3,2,4,5,6,8,1,2) = 8;
并且我们可以容易的看出F[i,0]就等于A[i]。（DP的初始值）
这样，DP的状态、初值都已经有了，剩下的就是状态转移方程。
我们把F[i，j]平均分成两段（因为f[i，j]一定是偶数个数字），从 i 到i + 2 ^ (j - 1) - 1为一段，i + 2 ^ (j - 1)到i + 2 ^ j - 1为一段(长度都为2 ^ (j - 1))。用上例说明，当i=1，j=3时就是3,2,4,5 和 6,8,1,2这两段。F[i，j]就是这两段各自最大值中的最大值。于是我们得到了状态转移方程F[i, j]=max（F[i，j-1], F[i + 2^(j-1)，j-1]）。
查询
假设我们需要查询区间[l, r]中的最小值，令k = log2(r - l + 1); 则区间[l, r]的最小值RMQ[l,r] = min(mn[l][k], mn[r - (1 << k) + 1][k]);
那么为什么这样就可以保证为区间最值?
mn[l][k]维护的是[l, l + 2 ^ k - 1], mn[r - (1 << k) + 1][k]维护的是[r - 2 ^ k + 1, r] 。
区间前后维护！
那么我们只要保证r - 2 ^ k + 1 <= l + 2 ^ k - 1就能保证RMQ[l,r] = min(mn[l][k], mn[r - (1 << k) + 1][k])；
我们用分析法来证明下：
若r - 2 ^ k + 1 <= l + 2 ^ k - 1;
则r - l + 2 <= 2 ^ (k + 1);
又因为 k = log2(r - l + 1)；
则r - l + 2 <= 2 *(r - l + 1);
则r - l >= 0;
显然可得。我们来举个例子 l = 4, r = 6;
此时k = log2(r - l + 1) = log2(3) = 1;
所以RMQ[4, 6] = min(mn[4][1], mn[5][1]);
mn[4][1] = 4, mn[5][1] = 2;
所以RMQ[4, 6] = min(mn[4][1], mn[5][1]) = 2;
我们很容易看出来了答案是正确的。dp，我的dp，我要拿到大国一！
NYOJ-119 士兵杀敌（三）【RMQ算法】
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 100010;
int maxsum[N][20], minsum[N][20];
void RMQ(int num) //预处理->O(nlogn)
{
for(int j = 1; j < 20; ++j)
for(int i = 1; i <= num; ++i)
if(i + (1 << j) - 1 <= num)
{
maxsum[i][j] = max(maxsum[i][j - 1], maxsum[i + (1 << (j - 1))][j - 1]);
minsum[i][j] = min(minsum[i][j - 1], minsum[i + (1 << (j - 1))][j - 1]);
}
}
int main()
{
int num, query;
int src, des;
scanf("%d %d", &num, &query);
for(int i = 1; i <= num; ++i) //输入信息处理
{
scanf("%d", &maxsum[i][0]);
minsum[i][0] = maxsum[i][0];
}
RMQ(num);
while(query--) //O(1)查询
{
scanf("%d %d", &src, &des);
int k = (int)(log(des - src + 1.0) / log(2.0));
int maxres = max(maxsum[src][k], maxsum[des - (1 << k) + 1][k]);
int minres = min(minsum[src][k], minsum[des - (1 << k) + 1][k]);
printf("%d\n", maxres - minres);
}
return 0;
}