前言
想说的话
最近在学校的天梯赛选拔中遇到了一道不会做的题目（肯定不是因为前面的题目都不会做，导致连看都没有看一眼），比赛结束后看题解才发现需要用到ST表。作为一名初学算法的大一萌新，我当然是没有接触过这个算法的，在我（刻苦研究）边摆烂边学习后，终于大概了解了ST表，然后发现软工的同学都在写关于java的博客（肯定不能比别人落后吧，虽然我java都还不会），于是写下了这篇随笔来记录我的学习成果（摆烂日常）。
原本想要画图讲解的，但是突然想起自己没有工具，只能全靠文字和代码讲解（极其枯燥无味而且难懂）。
注意：ST表基于倍增思想，在学习ST表前需要学会倍增法。
倍增法的简单介绍
倍增与二分
我之前以为倍增和二分是相反的两种算法，后来查找资料发现，倍增法与二分法是紧密相关的，二分法可以看作是一种倍增法。在写较大数据的题目时，为了防止TLE，我们往往需要使用二分法来提高运行效率。倍增法与二分法相同，都是效率很高的算法。他们直接的差别在于，二分法是从最大范围开始，每次缩小一半，直到找到需要的数；倍增则刚好相反，从最小范围出发，每次成倍增加（常常以二为基底），直到获得所需要的值。
倍增法运用
倍增法常常运用于静态数据的题目中，通过快速增长来实现快速查找。
其实快速幂也是一种具有倍增思想的算法。具体体现在将指数不断除以2，每次将结果平方，直到指数为0为止。这样可以将幂运算的次数从n降低到logn，大大提高了算法的效率。例如，计算a^10时，可以先计算a^5，再将结果平方得到a^10，而不是直接计算aaaaaaaaa*a，这样的计算次数更少，效率更高。
下面是快速幂代码
1 int quickPow(int a,int b){ 2 int ans = 1; 3 while(b > 0){ 4 if(b & 1) 5 ans *= a; 6 a *= a; 7 b >>= 1; 8 } 9 return ans; 10 }
倍增法通常运用于：快速幂、最近公共祖先、区间最大值/最小值、矩阵快速幂、等比数列求和。
经典题目：洛谷P4155
ST表
介绍
ST表是一种基于倍增法的数据结构，通常用来求解某个区间中的最值问题。在需要频繁查询区间最值的情况下是一种非常高效的数据结构。可以实现O(nlogn)预处理和O(1)查询。
核心思想
预处理思想、倍增思想。
通过倍增法预处理出所有可能的区间最值，然后使用这些预处理结果来快速查询任意区间的最值。
文字讲解
假设我们需要查找一个数组a[ n ]中某个区间的最大值，我们可以从每个小区间开始依次倍增。
预处理
我们把区间分为多层，第一层每个区间只包含两个数，第二层区间包含四个数，第三层区间包含八个数……以指数形式扩增。其中每层区间的值是其区间中数的最大值，用st[ i ][ j ]表示，其中i表示是该区间是从下标为 i 是数组即a[ i ]开始，j表示该区间是位于那一层，每层包括的数组长度为 2j ，因此该区间是以 2j + i - 1为下标的数组即a[ 2j + i - 1 ]结尾,即同层中与该区间相连的下一个区间为st[2j + i ][ j ]。因此容易得到st[ i ][ j + 1 ] = max( st[ i ][ j ] ,st[ (1 << j) + i ][ j ] ) )。注意：2j <= n
从第一层区间开始预处理，因为第二层区间需要两个第一层区间合并，依次类推，每次处理完该层中所有的区间后才开始处理下一层区间。
输出
当我们需要输出 l 到 r 区间中最大值时，我们需要自己计算出该区间是在第几层，k = log2( r - l + 1)。
因为 2k <= r - l + 1,所以我们只要从选两个k层的区间，第一个起点为 l ，第二个终点为 r，找到这两个区间的最大值，即可以得到 l 到 r 区间的最大值。
则 l 到 r 区间的最大值为 max(st[ l ][ k ], st[r - (1 << k) + 1 ][k])。
代码描述
预处理
1 int k = log2(n);//k是可倍增区间的最大次方 2 for (int i = 1; i <= k; i++){ 3 for(int j = 1; j + (1 << k) - 1 <= n ; j++){ 4 //j + (1 << k) - 1是下一个st数组的开始下标，该下标不会超出n的范围 5 st[j][i] = max(st[j][i - 1],st[j + (1 << (i - 1))][i - 1]); 6 //上文文字描述中为了描述的更加清晰，用的是st[i][j + 1]，与此处有所不同 7 } 8 }
输出
1 int k = log2(r - l + 1); 2 //l,r分别为区间的左边和右边 3 int ans = max(st[l][k], st[r - (1 << k) + 1][k]);
注意事项
1.ST表的空间复杂度为O(nlogn),因此需要注意空间的使用。
2.预处理时需要注意从下层开始处理。
3.需要注意大区间的值是否能用小区间的值进行结合处理。
后记
关于这次ST表
这篇博客我只用了求区间最大值的例子，需要求其它最值时，只需要将代码简单改改（虽然我也没贴什么代码）。感觉就算会ST表的人看了也会摇头，发现完全看不懂，或者越看越混乱，因为讲的真的超级差。
最后的话
第一次写博客，可能有很多不足（希望得到体谅），如果各位有对我的建议欢迎提出。
作为一名大一算法萌新（强调），我对ST表的理解可能还不够，如果哪里讲错了或讲的不清楚，欢迎指正。
本文来自博客园，作者tunecoming，转载请注明链接：https://www.cnblogs.com/tunecoming/p/17264452.html;