题目描述
给定一个长度为 N 的数组 a，其值分别为 a1,a2,...,aN
现有 Q 个询问，每个询问包含一个区间，请回答该区间的最大值为多少。
输入描述
输入第 1 行包含两个正整数 N,Q，分别表示数组 a 的长度和询问的个数。
第 22 行包含 N 个非负整数 a1,a2,...,aN，表示数组 a 元素的值。
第 3∼Q+2 行每行表示一个询问，每个询问包含两个整数 L,R，表示区间的左右端点
1≤N,Q≤5×10^5，1≤l≤r≤N，−10^9≤ai≤10^9。
输出描述
输出共 Q 行，每行包含一个整数，表示相应询问的答案。
输入输出样例
输入
5 5
1 2 3 4 5
1 1
1 2
1 3
3 4
2 5
输出
1
2
3
4
5
解题思路
一、适用场景
ST表用的是倍增思路，专门用来求静态数组的区间最大值或者最小值。
静态意思就是数组里面的数字不会变，如果题目有修改数字的操作，这个算法就不能用了。
查询非常快，蓝桥杯经常考裸题，背好模板就能拿分
二、两个核心数组（今天大部分疑问都在这）
1. st[k][i] ：从i这个下标开始，往后一共 2^k 个数字的最大值
st[0][i] ：2^0=1，就一个数，所以这一行就是原始数组
k越大，代表这一段的长度越长
2. log_table[] ：重点：这里面存的不是2的k次方结果，存的是指数k
我自己琢磨出来一个规律：奇数长度对应的k，和它前面最近那个偶数的k是一样的
公式： log_table[i] = log_table[i / 2] + 1
举个例子：
log_table[3]=1，块长就是 2^1=2
log_table[4]=2，块长就是 2^2=4
log_table[5]=2，块长就是 2^2=4
一开始我还想着i能不能每次+2只算偶数，发现不行，必须i从2循环到n一个个算，奇数如果不赋值，数组默认是0，后面查表会错
三、查询思路
每次查询给出 L、R，求区间 [L,R] 的最大值：
1. 先算出区间长度： len = R - L + 1
2. 拿着 len 去 log_table 查表，拿到 k，块长 = 1 << k也就是不超过区间长度的最大2的幂。
3. 取出两块长度等于该块长的区间：
左块：起点是 L， st[k][L] ，从L向右覆盖
右块：终点固定在 R，起点公式 R - (1 << k) + 1 ，从这个起点向右延伸，尾巴刚好卡在R
4. 把这两块的最大值对比，更大的值就是区间答案。
我之前一直搞不懂重叠到底是什么意思：
我们提前预处理好的块只能是2的幂长度，没法刚好匹配任意长度。所以用两块一样长的块，一块靠左、一块靠右铺开。只要 [L,R] 里面每一个数字，至少被其中一块包住就行。
就算中间一部分数字两块都包含了（重叠）也没事，求最大值不怕重复，不影响结果。
举例子：L=2,R=4，len=3，k=1，块长=2
左块：2、3；右块起点：4-2+1=3 → 3、4
两块合起来 2、3、4 全部覆盖，3重复了无所谓。
完整代码
#include <stdio.h>
#include <stdlib.h>
#define CF 20//随便取的值，只要保证够覆盖5*10^5就好了
#define MAXN 500007
int st[CF][MAXN];//从i开始，连续2^k次方个数里的最大值
int log_table[MAXN];//存长度为len的区间，最大的k，满足2^k<=len
int main(int argc, char *argv[])
{
int n,q;
scanf("%d%d",&n,&q);
int i;
//st[0][i]层，就是原数组本身
for(i=1;i<=n;i++)
{
scanf("%d",&st[0][i]);
}
log_table[1]=0;//预处理log_table数组
//当2^k==i时，log_table数组里放的是对应的k
for(i=2;i<=n;i++)//奇数时放的值是上一个偶数对应的k
{
log_table[i]=log_table[i/2]+1;
}
for(int k=1;k<CF;k++)//ST表倍增算表:一层一层往上算
{
for(i=1;i+(1<<k)-1<=n;i++)
{
//把长区间拆成前后两半，取两半的最大值
st[k][i]=st[k-1][i]>st[k-1][i+(1<<(k-1))]?st[k-1][i]:st[k-1][i+(1<<(k-1))];
}
}
while(q--)//处理每一次询问
{
int L,R;
scanf("%d%d",&L,&R);
int len=R-L+1;//算出区间长度
int k=log_table[len];//查表拿到对应的指数k
int max=st[k][L]>st[k][R-(1<<k)+1]?st[k][L]:st[k][R-(1<<k)+1];
printf("%d\n",max);
}
return 0;
}
建表部分踩坑
（1）st[k][i] = st[k-1][i] > st[k-1][i + (1 << (k-1))] ? st[k-1][i] : st[k-1][i + (1 << (k-1))]
这里我之前很好奇为啥是k-1：
当前这一整段长度是 2^k，对半切开之后，每一半长度就是 2^(k-1)，所以要用上一层k-1的数据
还有一个很关键的疑问：我在纸上推导数组的时候，发现它不是挨着比较，看着是交叉跳着取的。
比如 st[2][1]，不是拿 st[1][1] 和 st[1][2] 比，而是拿 st[1][1] 和 st[1][3] 对比。
后面我才想通：我们看的不是st这一行的下标顺序，看的是原始数组覆盖到哪些位置。
st[2][1] 管1、2、3、4这四个数，对半分就是前两个1~2，后两个3~4，所以才会隔一个取。
如果拿挨着的两个，区间会重叠，凑不齐连续4个数，直接就错了。（这里有点抽象，可以用例子里的数据推导一下）
（2）还有外层循环 k < CF
我发现k很大的时候，内循环根本进不去，一直在空跑。
其实这里可加break也可以不加，CF只设了20，最多空跑十几轮，电脑跑起来很快，蓝桥杯不会超时，我就选择不加，代码短一点好背。
转载自 CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/2402_87421821/article/details/170613005
