总的来说 ST算法是一种采用空间换时间的算法，最后达到的目的是将查询连续数的最小值和最大值的时间优化为O（1）
从查询连续数的最小值和最大值这个问题起步，
首先，我们考虑直接算，如果查询m-n，
然后我们可以考虑使用线段树，我们可以将线段树的每个节点定义为子树中的最小值和最大值，这样如果我们需要检查一段数据的最小值的时候只需要提取能完全包含这段线段的节点的就行了，时间复杂度到了
O（log2 n）
比起直接查找有了一定的优化,但是还不够，
最后就要看ST算法。ST算法基于的原理是：如果我们需要查R-L
，2Len
>（L-R+1），这样我们找min（r，l）
如果我们在查询前将min的数据全部生成的话，那么我们需要的时间复杂度为O（1）
具体的是我们定义一个二维数组
第i个数开始的2^j个数中的最小是的数
那么如果我们需要获取R-L上的最小的数，那么只需要找出min（data[R][k],data[L-2^k+1][k]）
data的数据可以动态生成
具体事例可以参考
下面是一个大神的源码
#include
#include
#include
#define max(a,b) a>b?a:b
#define min(a,b) a
const int N=100005;
int n,Q,c[N],a,b,k;
int dp_max[20][N];
//20不一定是唯一的。需要计算log(N)/log(2)
int dp_min[20][N];
//用来从输入流中获取一个数字
inline int Input()
{
int res=0,f=1,c;
while(!isdigit(c = getchar()) && c!='-');
c=='-' ? f=0 : res=c-'0';
while(isdigit(c = getchar()))
res = res*10 + c-'0';
return f ? res : -res;
}
void Init()
{
for(int i=1;i<=n;i++)
dp_max[0][i] = dp_min[0][i] = c[i];
//这里是生成稀疏矩阵
for(int j=1;j<20;j++)
for(int i=1;i+(1<<j)-1<=n;i++)
{
dp_max[j][i] =
max(dp_max[j-1][i],dp_max[j-1][i+(1<<(j-1))]);
dp_min[j][i] =
min(dp_min[j-1][i],dp_min[j-1][i+(1<<(j-1))]);
}
}
int Get_Max(int a,int b)
{
k = (int)(log(b-a+1)/log(2.0));
return max(dp_max[k][a],dp_max[k][b-(1<<k)+1]);
}
int Get_Min(int a,int b)
{
return min(dp_min[k][a],dp_min[k][b-(1<<k)+1]);
}
int main()
{
scanf("%d%d",&n,&Q);
for(int i=1;i<=n;i++)
c[i] = Input();
Init();
while(Q--)
{
a = Input();
b = Input();
printf("%d\n",Get_Max(a,b)-Get_Min(a,b));
}
return 0;
}