c++ ST表（包含技术活动）

bangbang-ande

(前言：本次为回馈活动，所以本次的代码将不开放，文章最后会说到理由）

本节我们说说ST表，这是一个经典的求最大值的数据结构，专门解决RMQ问题，但是它无法解决动态区间最大值（即区间加数后求最大值的问题）

ST表的理解难度不小，但是编写起来很容易。

我们先回顾求区间最大值的问题描述：

题目描述 （来自于洛谷的ST表的模板题P3865）
给定一个长度为N的数列，和M次询问，求出每一次询问的区间内数字的最大值。

输入格式
第一行包含两个整数N,M，分别表示数列的长度和询问的个数。
第二行包含N个整数（记为 a[\i]），依次表示数列的第i项。
接下来M行，每行包含两个整数 l[\i],r[\i]，表示查询的区间为[l[\i],r[\i]]。
输出格式
输出包含M行，每行一个整数，依次表示每一次询问的结果。

样例输入

1. 8 8
   
2. 9 3 1 7 5 6 0 8
   
3. 1 6
   
4. 1 5
   
5. 2 7
   
6. 2 6
   
7. 1 8
   
8. 4 8
   
9. 3 7
   
10. 1 8

复制代码

提示
对于 100% 的数据，满足 1 ≤ N ≤ 10^5，1 ≤ M ≤ 2×10^6，a[\i]∈[0,10^9]，1 ≤ l[\i] ≤ r[\i] ≤ N。
时间限制：800ms；空间限制：125MB

这个题就是ST表的经典问题：RMQ问题。看到这个题，相信大家有一些想法，我们由浅入深来说说ST表的做法：

大家可以很快想到的第一种解法就是区间内一个一个数进行遍历，然后找到区间最大值。
这种方法确实很容易，容易到分数可能不怎么够（24pts），代码如下：

1. #include <iostream>
   
2. using namespace std;
   
3. int main(void){
   
4.         int n, m;
   
5.         cin>>n>>m;
   
6.         int a[100010];
   
7.         for (int i=1; i<=n; i++){
   
8.                 cin>>a[i];
   
9.         }
   
10.         int x, y;
    
11.         for (int i=1; i<=m; i++){
    
12.                 cin>>x>>y;
    
13.                 int lmax=0;
    
14.                 for (int j=x; j<=y; j++){
    
15.                         if (lmax<a[j]){
    
16.                                 lmax=a[j];
    
17.                         }
    
18.                 }
    
19.                 cout<<lmax<<endl;
    
20.         }
    
21. }

复制代码

时间复杂度为O(nm)，如果n和m的值再大一点就超时了……

那么我们来想想有没有其它的方法……似乎有的Clever Boy就想出来了，我们可以用打表的方法求得最大值！虽然叫打表，但其实运用了动态规划的思想（不懂没关系）。简单的说，方法就是将每一种可能全部列出来，比如说有十个数据，那么我们的表中存储的是第一个~第二个的最大值，第一个~第三个的最大值，第一个~第四个的最大值，第一个~第五个的最大值……列出来的方法并不是单纯的一个一个模拟，而是根据已经算出来的可能进行组合获得全部的可能，时间复杂度为O(n^2+m)，空间复杂度就很大了O(nm)，时间和空间依旧没有得到巨大的改进。

ST表生而就是为了这个目的，因为它使用了倍增的思想，也就是2^n一步递增的方法。同时也因为2的特殊性（即$2^n=2^(n-1)+2^(n-1)），所以才有了这种方法。我们接下来正式来说ST表：

ST表是用二维数组构建的，我们用dp[\i][j]表示，那么i和j分别表示什么呢？准确来说，i表示的是原数组的第几个位置。而j的表示很关键，表示的是区间的长度。那么揭晓一下dp[j]表示的就是区间[i, i+2^j-1]的最大值。也就是说，我们存储的最大值并不是第二种方法的所有的最大值（也就是从所有的起点开始存，存储所有可能的区间），而是存一个次方的区间最大值。表格的讲解对我们后面的讲解很关键。

我们先讲解如何查询最大值：如果要查询某一部分的最大值，我们可以运用拆解的方法，举个例子，比如以下10个数：

数组	1	2	3	4	5	6	7	8	9	10
a[]	34	23	18	45	43	69	7	90	22	56

加入我们打表已经完成，那么我们查询最大值的方法很简单，（假设查询[1, 10]最大值）我们只需要根据打好的表查询1-8的最大值；9-10的最大值进行比较得出最终最大值即可。这就是查询最大值的方法。

（下方的len表示的是l+r-1的值，也就是查询区间最大值的区间的长度）
此时很多同学都是？？？？的，我解释一下：查询方法是这样的：我们秉承不重复的原则，根据2^j≤len的目的寻找$j$的最大值，然后取出并且比较2^j的最大值，然后将没搜索到的部分作为新区间，再进行搜索（这也就是分段查询），我们用下图表示：


这一个图就很明显的告诉我们了搜索的方式，大家可以尝试下边的例子：查询[2, 8]最大值，查询的图片如下：


那我们总结一下就是：


查询的时间可以简化为O(log n)，根据题目的m次查询，时间复杂度为O(m log n)；

那有没有更加简便的方法呢？有的有的，刚刚的操作是运用了每一次的查询都是不重复的，那么可不可以重复呢？答案是可以，还很可以！因为重复的查询不影响最大值，最大值永远是它，重复查询仅仅是重复包含了某一段区间，对最大值没有影响。
既然可以重复，那么我们不如想想用最少的次数去查询。相信大家已经想到了，我们在前面的分段查询时，第一次分段的区间是最大的，而且会发现它永远大过于区间的一半，永远包含在最终查询的区间当中。那么实际上我们可以这么做：



也就是在分段的时候先铺一层第一段区间，再倒着铺一段相同的区间，那么此时我们就可以将整一个区间都覆盖，并且不超出该区间！
那这样子的方式也最简单，最快速，时间复杂度降低到了前所未有的O(1)！有m次查询，所以时间复杂度为O(m)！

然后我们来讲讲构建：

数组	1	2	3	4	5	6	7	8	9	10
a[]	34	23	18	45	43	69	7	90	22	56

（上方为例子）
根据例子的数据，我们先建立一个二维列表出来：

dp[][]	1	2	3	4	5	6	7	8	9	10
0
1
2
3

那么根据我们对dp二维数组的定义，即：

dp[j]准确来说，i表示的是原数组的第几个位置。而j的表示很关键，表示的是区间的长度。那么揭晓一下dp[\i][j]表示的就是区间[i, i+2^j-1]的最大值。

（Tips：这里的表格与数组的形式是倒置了，表格的横轴为下方的i，纵轴为下方的j）我们可以首先可以得出dp[\i][0]的最大值就是a的值，因为这一行表示的是区间[i, i+1-1]，也就是[i, i]的最大值，那区间内只有一个数的最大值不就是这个数本身吗，所以填表如下：

dp[][]	1	2	3	4	5	6	7	8	9	10
0	34	23	18	45	43	69	7	90	22	56
1
2
3

那么接下来的应该怎么填写呢？依旧很简单，dp[j]=max(dp[j-1], dp[i+2^(j-1)][j-1])，这一条式子也是很绝妙的，举个例子大家就明白了，dp[1][1]求的是区间[1,1+2^1-1]，也就是$[1, 2]$的最大值。那么我们想想，一共就两个数，那比较最大值不就是从dp[1][0]和dp[2][0]去比较吗？那如果是dp[1][2]呢，它求的是区间[1, 4]的最大值，那么根据上面给出来的式子，我们可以知道：它通过寻找dp[1][1]的最大值和dp[3][1]的最大值可以得出，那这两个数怎么来的呢？由于我们的填表的顺序是从上到下的，所以这两个数在之前早就填完了，所以同理可以求出。最后填表如下（X表示不需要填，因为超过了数组的范围）：

dp[][]	1	2	3	4	5	6	7	8	9	10
0	34	23	18	45	43	69	7	90	22	56
1	34	23	45	45	69	69	90	90	56	X
2	45	45	69	69	90	90	90	X	X	X
3	90	90	90	X	X	X	X	X	X	X

那么这个时候就构建完了ST表，确实理解起来很简单，按照填表的数量，可以得出时间复杂度约为O(n log n)
最后我们来写一下程序（按照P3865写的，这个程序还不能拿满分，在原题目有提示满分的方法）：

1. 自己写，因为这一次有活动……

复制代码

ST表完美解决了最大值的问题，时间复杂度为O(1)，当然按照洛谷的问题来说，时间复杂度是O(nlog n+m)，但是依旧不够全能。

最后，来填前言埋下的坑：
本次是第一次技术活动，大家可以通过我的描述，或者搜集更多的资料，去弄懂ST表的原理，自行写出ST表的程序，在洛谷平台中尝试测试P3865）
洛谷的题目链接：https://www.luogu.com.cn/problem/P3865
测试出的最高分数可以拿到的奖励：
24pts及以下：0鱼币
24pts~56pts（不包含56pts，也不包含24pts）：2鱼币+1荣誉
56pts~80pts（不包含80pts）：5鱼币+5荣誉
80pts~100pts（不包含100pts）：8鱼币+8荣誉
100pts：12鱼币+10荣誉

如何发送自己的分数呢？这么发就行了：（仅仅截下测试点信息即可）

（因为我目前的评分只能评价一个鱼币，那么大家多发几条信息，我就能多评价一些，反正会补上就对了）
Have a great time，Everyone！
截止日期：2023.8.4

如果你水平不行的话，那么你可以尝试用运气的手段去要到鱼币（10%，2鱼币）

sfqxx

前排支持

额外减小

你已经做到这么高深的数据结构了啊...

琅琊王朝

woshizhangpengp

sfqxx

sfqxx

@zhangjinxuan

零之忆