一.作用

求区间最大最小值

二.算法流程

1.预处理 $ST算法本质是动态规划，我们用a[1…n]表示一组数，设F[i,j]表示从a[i]到a[i+$2^{j-1}$]这个范围的最大值，也就是以a[i]为起点的连续$2^j$个数的最大值。由于元素个数为$2^j$个，所以可以从中间平均分成2部分，每一部分的个数刚好是$2^{j-1}$个，也就是说，把f[i,j]分为f[i,j-1]和f[i+$2^{j-1},j-1]$注意F的意义，不然会搞不懂F$ 整个区间的最大值一定是左右两个部分的最大值或者较大值，满足动态规划的最优化原理，分析得到状态转移方程:f[i][j] = max(f[i][j-1],f[i+$2^{j-1}$,j-1]),边界条件为f[i][0] = a[i]，这样就可以在O($nlogn$)的时间复杂度内预处理f数组。

二.询问

若要询问区间[l,r]的最大值，则先求出最大的x满足$2^x\leq r-l+1$,那么区间[l,r] = [l,l+$2^x-1$]$\cup$[r-$2^x-1,r]$两个区间元素个数都为$2^x$,所以[l,r]的最大值为max(f[l][x],f[r-$2^x+1$,r],可以在O(1)的时间内计算出来，虽然区间有交集，但是对于最值没有影响，但是ST也只适用于区间最值，求[x,y]的最大值，可以这样：

k = log2(y-x+1); ans = max(f[x][k],f[y-$2^k$+1][k]);

三.处理技巧

预处理出O(N),设log[d]为$log_2d$向下取整的结果，那么log[d] = log[d/2]+1;//介个，应该很容易明白吧？？？