c++ ST表（包含技术活动）
本帖最后由 bangbang-ande 于 2023-7-24 00:36 编辑(前言：本次为回馈活动，所以本次的代码将不开放，文章最后会说到理由）
本节我们说说ST表，这是一个经典的求最大值的数据结构，专门解决RMQ问题，但是它无法解决动态区间最大值（即区间加数后求最大值的问题）
ST表的理解难度不小，但是编写起来很容易。
我们先回顾求区间最大值的问题描述：
题目描述 （来自于洛谷的ST表的模板题P3865）
给定一个长度为N的数列，和M次询问，求出每一次询问的区间内数字的最大值。
输入格式
第一行包含两个整数N,M，分别表示数列的长度和询问的个数。
第二行包含N个整数（记为 a[\i]），依次表示数列的第i项。
接下来M行，每行包含两个整数 l[\i],r[\i]，表示查询的区间为,r[\i]]。
输出格式
输出包含M行，每行一个整数，依次表示每一次询问的结果。
样例输入
8 8
9 3 1 7 5 6 0 8
1 6
1 5
2 7
2 6
1 8
4 8
3 7
1 8
提示
对于 100% 的数据，满足 1 ≤ N ≤ 10^5，1 ≤ M ≤ 2×10^6，a[\i]∈，1 ≤ l[\i] ≤ r[\i] ≤ N。
时间限制：800ms；空间限制：125MB
这个题就是ST表的经典问题：RMQ问题。看到这个题，相信大家有一些想法，我们由浅入深来说说ST表的做法：
大家可以很快想到的第一种解法就是区间内一个一个数进行遍历，然后找到区间最大值。
这种方法确实很容易，容易到分数可能不怎么够（24pts），代码如下：
#include <iostream>
using namespace std;
int main(void){
int n, m;
cin>>n>>m;
int a;
for (int i=1; i<=n; i++){
cin>>a;
}
int x, y;
for (int i=1; i<=m; i++){
cin>>x>>y;
int lmax=0;
for (int j=x; j<=y; j++){
if (lmax<a){
lmax=a;
}
}
cout<<lmax<<endl;
}
} 时间复杂度为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]表示，那么i和j分别表示什么呢？准确来说，i表示的是原数组的第几个位置。而j的表示很关键，表示的是区间的长度。那么揭晓一下dp表示的就是区间的最大值。也就是说，我们存储的最大值并不是第二种方法的所有的最大值（也就是从所有的起点开始存，存储所有可能的区间），而是存一个次方的区间最大值。表格的讲解对我们后面的讲解很关键。
我们先讲解如何查询最大值：如果要查询某一部分的最大值，我们可以运用拆解的方法，举个例子，比如以下10个数：
数组12345678910
a[]3423184543697902256
加入我们打表已经完成，那么我们查询最大值的方法很简单，（假设查询最大值）我们只需要根据打好的表查询1-8的最大值；9-10的最大值进行比较得出最终最大值即可。这就是查询最大值的方法。
（下方的len表示的是l+r-1的值，也就是查询区间最大值的区间的长度）
此时很多同学都是？？？？的，我解释一下：查询方法是这样的：我们秉承不重复的原则，根据2^j≤len的目的寻找$j$的最大值，然后取出并且比较2^j的最大值，然后将没搜索到的部分作为新区间，再进行搜索（这也就是分段查询），我们用下图表示：
这一个图就很明显的告诉我们了搜索的方式，大家可以尝试下边的例子：查询最大值，查询的图片如下：
那我们总结一下就是：
查询的时间可以简化为O(log n)，根据题目的m次查询，时间复杂度为O(m log n)；
那有没有更加简便的方法呢？有的有的，刚刚的操作是运用了每一次的查询都是不重复的，那么可不可以重复呢？答案是可以，还很可以！因为重复的查询不影响最大值，最大值永远是它，重复查询仅仅是重复包含了某一段区间，对最大值没有影响。
既然可以重复，那么我们不如想想用最少的次数去查询。相信大家已经想到了，我们在前面的分段查询时，第一次分段的区间是最大的，而且会发现它永远大过于区间的一半，永远包含在最终查询的区间当中。那么实际上我们可以这么做：
也就是在分段的时候先铺一层第一段区间，再倒着铺一段相同的区间，那么此时我们就可以将整一个区间都覆盖，并且不超出该区间！
那这样子的方式也最简单，最快速，时间复杂度降低到了前所未有的O(1)！有m次查询，所以时间复杂度为O(m)！
然后我们来讲讲构建：
数组12345678910
a[]3423184543697902256
（上方为例子）
根据例子的数据，我们先建立一个二维列表出来：
dp[][]12345678910
0
1
2
3
那么根据我们对dp二维数组的定义，即：
dp准确来说，i表示的是原数组的第几个位置。而j的表示很关键，表示的是区间的长度。那么揭晓一下dp[\i]表示的就是区间的最大值。
（Tips：这里的表格与数组的形式是倒置了，表格的横轴为下方的i，纵轴为下方的j）我们可以首先可以得出dp[\i]的最大值就是a的值，因为这一行表示的是区间，也就是的最大值，那区间内只有一个数的最大值不就是这个数本身吗，所以填表如下：
dp[][]12345678910
0
3423184543697902256
1
2
3
那么接下来的应该怎么填写呢？依旧很简单，dp=max(dp, dp)，这一条式子也是很绝妙的，举个例子大家就明白了，dp求的是区间，也就是$$的最大值。那么我们想想，一共就两个数，那比较最大值不就是从dp和dp去比较吗？那如果是dp呢，它求的是区间的最大值，那么根据上面给出来的式子，我们可以知道：它通过寻找dp的最大值和dp的最大值可以得出，那这两个数怎么来的呢？由于我们的填表的顺序是从上到下的，所以这两个数在之前早就填完了，所以同理可以求出。最后填表如下（X表示不需要填，因为超过了数组的范围）：
dp[][]12345678910
0
3423184543697902256
1342345456969909056X
245456969909090XXX
3909090XXXXXXX
那么这个时候就构建完了ST表，确实理解起来很简单，按照填表的数量，可以得出时间复杂度约为O(n log n)
最后我们来写一下程序（按照P3865写的，这个程序还不能拿满分，在原题目有提示满分的方法）：
自己写，因为这一次有活动……
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鱼币） 前排支持 你已经做到这么高深的数据结构了啊... {:5_106:} {:5_106:} {:10_256:} @zhangjinxuan {:9_241:} {:7_113:}
页:
[1]