模板-ST表

题目背景

这是一道ST表经典题——静态区间最大值

请注意最大数据时限只有0.8s，数据强度不低，请务必保证你的每次查询复杂度为 O(1)

题目描述

给定一个长度为 N 的数列，和 M 次询问，求出每一次询问的区间内数字的最大值。

输入输出格式

输入格式：

第一行包含两个整数 N, M，分别表示数列的长度和询问的个数。

第二行包含 N 个整数（记为 ai），依次表示数列的第 ii 项。

接下来 M行，每行包含两个整数 li, ri​，表示查询的区间为[li​,ri​]

输出格式：

输出包含 M行，每行一个整数，依次表示每一次询问的结果。

输入输出样例

输入样例#1： 

8 89 3 1 7 5 6 0 81 61 52 72 61 84 83 71 8

输出样例#1： 

99779879

说明

对于30%的数据，满足： 1≤N,M≤10

对于70%的数据，满足： 1≤N,M≤1e5

对于100%的数据，满足： 1≤N≤1e5,1≤M≤1e6,ai​∈[0,1e9],1≤li​≤ri​≤N

关于这道区间最值的题，很显然要用ST表吧。

那么，ST表是什么呢？

简单的说，ST表就是通过初始化的方式来求区间最值，从而达到建表复杂度为O(nlogn)，查询复杂度只为O（1）！！！（不激动吗？）

但显然它也有一定的弊端，就是建表之后就不能再更改（其实也不是不行，大不了重新建一个呗（想想时间复杂度。。。）），这也确立了它的局限性。。。

好的那么我们该如何实现呢？

1.建表

先确定一件事：长度为1的区间最大值就是该数本身（显然吧）

我们想一想，如果要记录每一个区间的最值，那么我们就需要把每一个区间都扫一遍，时间复杂度可想而知。。。

那么我们该怎么办呢？

这里我们用到了一种思想（也属于一种算法）：倍增！！！

在讲他之前，我们先定义一个二维数组p[j][i]表示从第i个数开始，长度为pow（2，j）的区间的最大值。

好的，你可能又要问倍增是什么？

倍增就是2的n次幂，其中n不断的变大，由于他的增长是2的指数级的，因此称之为倍增。

我们来想一个问题：对于任意一个区间，他的最大值是不是就等于（（它的分出的各个区间的最大值）的最大值）（好吧，有点绕）。。。

这个是显然的吧。。。

那么，我们是不是可以将它分为各个区间呢？（问题的关键）

再结合倍增，我们可以把一个区间[i,i+pow(2,j)-1]表示为[i,i+pow(2,j-1)-1]和[i+pow(2,j-1),i+pow(2,j)-1];(由此我们得到了状态转移方程；dp的出现了）

或许这张图会更明白一些。。。

因此，只要不断进行拆分，就可以利用倍增来初始化ST表。（没听懂没有关系，请再看一遍后继续往下听）

那么代码该如何实现呢？

其实也比较简单，只要从j=1开始倍增（j=0上文提到初始化的方法），并保证不要越界（如果越界就会RE或者加入一些十分奇怪的数。。。），再比较两个区间的最大值即可。

2.查询

刚刚讲的建表其实也是为了查询做准备工作，可能大家刚刚有一个疑问：不是要求区间最大值么？你怎么保证数据给的长度就正好是2的n次幂呢？

没事，我学的时候也有这一个疑问，因此我们还有下文qwq

你想，我们求的只是区间最大值，而不是区间之和，是不是有一点思路了呢？

没有也没关系，我们还是用一张图来解释一下：

看完这张图你可能有一个疑问：这个区间不是重叠了么？

但是这又有什么影响呢？

由于我们知道每一个点开始2的n次幂的区间最值，所以我们只要将所求区间用这个初始值完全覆盖即可，并且我们不能超出这个区间。

所以我们只要从两个边界点向区间里看，从大到小倍减直到找到第一个2的n次幂小于区间长度，显然它大于区间的一半，我们只要将[l,l+pow(2,k)-1]和[r-pow(2,k)+1]进行比较求出最值即可。

最后，附上本题代码：

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 int a[100005],p[50][100005]; 6 void start(int n) 7 { 8     int t=log2(n); 9     for(int k=1; k<=t+1; k++)10     {11         for(int i=1; i+(1<
        
         <=n; i++)12         {13             p[k][i]=max(p[k-1][i],p[k-1][i+(1<<(k-1))]);14         }15     }16 }17 void query(int l,int r)18 {19     int t=log2(r-l+1);20     printf("%d\n",max(p[t][l],p[t][r-(1<