看到全网并没有太多对ST表详细的解释，本蒟蒻决定写一篇相对详细的对ST表解析的blog，希望能让更多的萌新听懂qwq。
进入正题：
语言：会C（C++）就行
数学知识：对数,指数（不会的可以点这里以及这里）
思想：有一些dp（动态规划）的思想（不会dp的别走啊，你还可以在这里学到一点dp呢！）
下面我们从这一道题目讲起：（原题在这：点这里）
给定一个长度为 的数列，和 次询问，求出每一次询问的区间内数字的最大值。
最暴力朴素的想法：对每次询问，都把这个数列相应的区间扫一遍找出最大值。
时间复杂度是 ,最坏情况就是每次都要求你把整个数列扫一遍，根据题目给出的范围，肯定会超时！
有没有更快的方法呢？
有。
怎么做呢？
比如说对于一次查询，从起点开始，对给出的区间一个个元素扫实在是太慢了。考虑一个区间 ，我们先设想是足够大的，先不去管它，而是先去考虑起点。
看看下面这组例子，并考虑起点在第一个数 .
19260817
（从起点开始）
区间长度为 2 的区间最大值为
接下来，我们开始移动起点，因为前两个已经被统计过了，于是我们将起点移到第三个数，对第三、第四个数（区间长度为2）的最大值进行更新，如此下去，直到边界。依次可以得到最大值：
9687
你一定发现接下来要做什么了吧，就是依次更新下去，直到更新完毕。
因为区间的长度依次为 于是可以用函数表示 的最大值。
更新的方程如下：
方程还是很好理解的，不过如何进行数据的更新呢（进一步说，如何枚举呢）？
就按我们刚才模拟的顺序即可：
我们是以区间长度为第一关键字，起点为第二关键字展开的，于是依次枚举即可：
for(int j=1;j<=21;j++) for(int i=1;i+(1<<j)-1<=n;i++) f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);（你不会位运算？没事，在这里你只需要知道（ 表示2的j-1次方即可）
更新完毕后，我们就可以进行查询操作了：
对一个区间 只需考虑找到两个区间覆盖这个区间（第一个区间起点和该区间相同，第二个区间终点和该区间相同），那么查询的区间最大值一定在这两个区间之中，取一下两个区间最大值的最大值即可。
（简证：假设查询的区间最大值不在这两个区间最大值之中，对第一个区间，一定不在里面，类似地，亦不在第二个区间中，于是不在两个区间的并集（即该区间中），显然矛盾）
下面我们考虑构造这两个区间的方法：
对第一个区间，记相应的对应 该区间。
那么应有 在 中（s为自然数）
进而有：
类似地，第二个区间对应
所以所求的最大值就是： 问题解决！
下面是代码：
#define logn 21 #define maxn 100000 inline int read()//快读 { int x=0,f=1;char ch=getchar(); while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();} while (isdigit(ch)){x=x*10+ch-48;ch=getchar();} return x*f; } int n,m; int f[maxn+1][logn+1]; int Logn[maxn+1]; void pre()//这一步是为了求log（不用系统的log节省时间） { Logn[1]=0; for(int i=2;i<=n;i++) Logn[i]=Logn[i/2]+1; } int main(){ n=read(); m=read(); for(int i=1;i<=n;i++) f[i][0]=read(); for(int j=1;j<=21;j++) for(int i=1;i+(1<<j)-1<=n;i++) f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]); pre(); while(m--){ int x=read(); int y=read(); int s=Logn[y-x+1]; int ans; ans=max(f[x][s],f[y-(1<<s)+1][s]); printf("%d\n",ans); } return 0; }
