ST算法：
ID数组下标: 1 2 3 4 5 6 7 8 9
ID数组元素: 5 7 3 1 4 8 2 9 8
1、ST算法作用:
主要应用于求区间最值上,可以把所需要求的区间极大的压缩，并且查询的复杂度为O(1)。比如我们要求一段区间上的最大值，就算是用DP的思想去做，用DP[i][j]表示从i到j区间的最大值，如果需要保存数据元素N比较多的时候，比如N=10000的时候，你开个二维数组肯定超内存，如果你用线段树做的，或许能行得通，不过如果N在更大的时候N=100000，估计线段树每次查询的复杂度为O(log n),询问比较多的时候也容易卡掉。这时候ST算法就派上用场啦~
2、ST算法的主要保存形式是F[i][k]：
表示的是从n点为起点,长度为2^k的区间最值等价于ID[i][i+2^k-1]的区间大小，当k越大的时候，所代表的区间也越大。需要注意的一点是，区间长度都是2^k去表示的！！！
3、F[i][k]的预处理:
同样在区间最值求解上，用动态规划的思想去求的每一区间F[i][k]的最值。
当k=0的时候，区间则表示的变成一个点，也就是i位置上的值。所以DP的初始值也就是F[i][0]=ID[i]。
然后，动态规划最重要的就算状态转移方程了，以最大值为例子，也就是
F[i][j]=max(F[i][j-1],F[i+2^(j-1)][j-1]);
说下这个状态转移方程的由来,我们每次求的是F[i][j],也就是ID[]数组所表示的区间[i,i+2^j-1]:
F[i][j]=>ID[i~i+2^j-1]:
[i.........................................................................................................................i+2^j-1]
把这个区间二等分,也就是[i,i+2^j-1]=[i,i+2^(j-1)-1]+[i+2^(j-1),i+2^j-1],也就是F[i][j]是由F[i][j-1]和F[i+2^(j-1)][j-1]组成的，这很容易理解，也就是说，每次从二分的子区间中取最值赋值给当前的区间。从而把所有的区间的最值就这样保存下来、
二等分=>[i,i+2^j-1]=[i,i+2^(j-1)-1]+[i+2^(j-1),i+2^j-1]=>F[i][j-1]和F[i+2^(j-1)][j-1]
[i.........................................................................................................................i+2^j-1]
||
[i............................................i+2^(j-1)-1][i+2^(j-1) .....................................i+2^j-1]
4、求解区间[a,b]的最值
然而，我们需要求的是区间[a,b],并不是这样[i,2^k],这样的区间，求这个F[i][k]表示区间有什么用呢？当然是有用的啦。我们把区间[a,b]转换一下，不就可以了吗、
我们可以知道区间[a,b]的区间长度为b-a+1，如果你想把区间长度转换成两个2^k，然后求解两个区间的最值，你就想错了，那是不可能的，除非你能够证明任意数N=2^k+2^k,k存在整数解，然后这很明显是错误的，比如N=11就无整数解了的。ST算法的查询只有O(1),他是通过求解区间长度最大的2^k的值，也就是找出一个k，使得2^k<=b-a+1,然后通过比较区间[a,a+2^k-1]和[b-2^k+1,b]取最值实现的,这里的a+2^k-1并不一定会等于b-2^k+1，而且一般情况下都是大于的情况、
[a...................................................................b]
[a....................... (a+2^k-1)]
[(b-2^k+1)....................b]
求解这两个区间的最值也就是求解区间[a,b]最值了的。
首先我们要先求出K,计算方法就是:
2^k=b-a+1
=>k=log2(b-a+1)
=>k=lg(b-a+1) /lg(2)
=>k=(int)(log(b-a+1.0)/log(2.0));
(PS:C中的lg的计算是用log表示Orz,Orz,Orz........)
5，一些证明：
求解出的k表示的是长度b-a+1表示成2的N次方,最大能够表示的N,一定会使得:2^k<=b-a+1.
证明：2^k>=(b-a+1)/2。
假设求的的k是最大的次方，如果2^k小于区间长度(b-a+1)的一半，
则说明区间(b-a+1)的长度大于2个2^k,2^k+2^k=2^(k+1),
也就是说这段区间(b-a+1)中还存在n=k+1使得2^n > 2^k,与假设不符，
所以，2^k>=(b-a+1)/2恒成立、
代码：（2015.8.14）
#include <iostream>
#include <stdio.h>
#include <math.h>
#define max(a,b) (a)>(b)?(a):(b)
#define min(a,b) (a)<(b)?(a):(b)
#define MAX 100010
using namespace std;
int maxsum[MAX][];
int minsum[MAX][];
int Num[MAX];
void Cread_ST(int N) //预处理->O(nlogn)
{
for(int i=;i<=N;i++)maxsum[i][]=minsum[i][]=Num[i];
int Len=(int)(log(N)/log(2.0));
for(int j = ; j <=Len; j++){
for(int i = ;i+(<<j)-<= N; i++){
int TMD=i+(<<(j-));
maxsum[i][j]=max(maxsum[i][j-],maxsum[TMD][j-]);
minsum[i][j]=min(minsum[i][j-],minsum[TMD][j-]);
}
}
}
int RMQ(int l,int r)
{
int k,TMD,Max,Min;
k=(int)(log(r-l+1.0)/log(2.0));
TMD=r-(<<k)+;
Max=max(maxsum[l][k],maxsum[TMD][k]);
Min=min(minsum[l][k],minsum[TMD][k]);
return Max-Min;
}
int main()
{
int N,i,Q,a,b,k,Max,Min;
while( scanf("%d%d",&N,&Q)!=EOF)
{
for(i=;i<=N;i++)
scanf("%d",&Num[i]);
Cread_ST(N);
while(Q--)
{
scanf("%d %d",&a,&b);
printf("%d\n",RMQ(a,b));
}
}
return ;
}
**************************************
* 作者: Wurq
* 博客: http://www.cppblog.com/wurq/
* 日期: //
**************************************