题目链接
https://www.luogu.org/problemnew/show/P3865
ST表的作用
ST表可以解决RMQ问题，即区间最大值、最小值
优点
速度快：预处理的时间复杂度是o(nlogn)。查询的时间复杂度是o(1)。
缺点
不支持修改操作
实现方法
ST表借助于一个数组实现：st[i][j]表示从i为起点，2j个长度的区间最大值。
预处理：
显然，st[i][0]=a[i]; 即从i开始1个单位长度的最大值就是i。
然后是一个双层循环，第一层是枚举数组的第二维下标，j从1开始（0已经预处理了），一直到log2(n),为什么呢？因为第二维表示的是2j个长度单位，所以2log2(n)<=n。
这里可能对log2不理解，假设log2(n)返回的是k，那么k是2k<=n的最大整数。例如log2(4)=2 log2(5)=2 log2(6)=2 log2(7)=2 log2(8)=3 ……
所以说，j枚举到log2(n)就行了。
第二层循环枚举的是i，是第一维下标，从一开始，一直到i+(1<<j)-1<=n。1<<j意思是1左移j位，等价于2j,但比它要快得多。如果起始位i加上2的j次方再减1（起始位不包括在内）后超过了n，就没有必要继续进行下去了。
我们推出状态转移方程：st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]); //dp的思想，两段的最大值就是整个区间的最大值。依旧不明白可以自己手推一遍试试。
为什么要先循环j呢？因为我们初始化的是st[i][0]，如果先循环i就会有一些分段还未求出。（建议大家手推一遍试试）
这样，预处理就结束了。
查询：
每一次读入要查询的区间l--r，令k=log2(r-l+1).为什么呢？r-l+1其实就是区间的长度。
令len=r-l+1，很显然，len / 2 < 2log2(len) <= len。所以说每一次输出max(st[l][k],st[r-(1<<k)+1][k]) 。
在这里st[i][k]一定越过了l--r区间的中点，st[r-(1<<k)+1][k]就是表示后2k个数，也一定在起点到中点之间，这样操作就覆盖了整个区间。
附上代码：
1 #include<iostream> 2 #include<cmath> 3 #include<cstdio> //注意一定要用scanf和printf，否则会超时 4 using namespace std; 5 int n,m,a[200005],st[200005][35]; 6 int main(){ 7 cin>>n>>m; 8 for(int i=1;i<=n;i++){ 9 scanf("%d",&a[i]); 10 st[i][0]=a[i]; //先初始化st数组。 11 } 12 for(int j=1;j<=log2(n);j++){ //第二维到log2(n)即可，因为2^(j+1)>n 13 for(int i=1;i+(1<<j)-1<=n;i++){ //注意边界 14 st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]); 15 } 16 } 17 for(int i=1;i<=m;i++){ 18 int l,r; 19 scanf("%d%d",&l,&r); 20 int k=log2(r-l+1); 21 printf("%d ",max(st[l][k],st[r-(1<<k)+1][k])); 22 } 23 return 0; 24 }
我建议大家感性理解一下，要准确地证明真的比较难。大家可以手算模拟一遍。