目录
前言
一,暴力法
二,打表法
三,ST表
四,ST表的代码实现
总结
前言
ST表的主要作用是在一个区间里面寻找最大值,具有快速查找的功能,此表有些难,读者可以借助我的文章和网上的课程结合一起来看,多思考,此文章是逐层深入到ST表,为什么会有ST表,不会直接讲ST表
一,暴力法
问题切入:区间问题求最值
n个数字,在一个区间[ L,R ]中寻找MAX值,此过程进行m次查阅
例子:9 3 1 5 6 0 8
0 ~ 5 max为9 4~5 max为6 我们不难看出,这个是通过我们人的眼睛扫描最后比较得出得答案,那我们不难写出这个过程的代码
#include<iostream> #include<algorithm> #include<vector> using namespace std;int main() {vector<int>arr = { 9,3,1,5,6,0,8 };int ans, L, R;cin >> L >> R;for (int i = L;i <= R;i++) {ans = max(ans, arr[i]);}cout << ans << endl;return 0; }
我们想一下我们的人眼睛,我们人眼睛扫描一遍是不是需要用for循环遍历一遍,然后大脑不断地进行比对,最终得出最值,此类方法我们称之为暴力法
暴力法:时间复杂度O(nm)
我们不妨把这个复杂度放入到生活中里面实践一下
假设有100个数,同时进行10^7次查找,最后我们地测评集为10^9
1秒里面地测评集合是10^7~10^8,那么这个肯定不行
二,打表法
我们根据上面不难发现时间复杂度是O(nm),那么我们要优化这个时间复杂度的话,不难看出是n和m相差太大了,我们想把这个m换掉,换成小一点的,那么就有了打表法,也就是动态规划的思想
我们是每次选取两个数字,那么不就是利用二项式不就好了
我们这里就是
每次从n个数字选取两个数字,最后就是上面这个结果
我们可以列出表的打法的方程式子
i是左端点,j是右端点
#include<iostream> #include<algorithm> #include<vector> using namespace std;int main() {vector<int>arr = { 9,3,1,5,6,0,8 };const int n = 7;vector<vector<int>>ans(n, vector<int>(n, 0));for (int i = 0;i < n;i++) {for (int j = i;j < n;j++) {ans[i][j] = max(ans[i][j - 1], arr[j]);}}int L, R;cin >> L >> R;cout << ans[L][R] << endl; }
我们看的出来,这个就是一个打印一个表,这个表都有对应得数据,但是我这个代码有个缺陷,就是你刚刚开始得数组不可以为负数,当我们刚刚开始把数字填进去的时候,是与0进行比较填入的,还好这个是容器,会把没有用的空间排出去,要不然就会导致空间浪费,比如我们打一个4*4的表
然后容器就会解决这个问题,类似于边长数组,我们再来计算一下时间复杂度和空间复杂度
时间复杂度:O(n^2+m)
空间复杂度:O(n^2)
我们可以看到这个表的作用是把操作数字和表的行列的数字分开了,不是相乘而是相加,但是当n很大的时候不仅时间炸,这个空间也会炸,所以即使我们利用了表分开,但是结果还是不怎么好,但是我们该怎么利用这个表的思想来进行进一步的优化呢?
三,ST表
这个东西就有点点难,读者请认真理解
ST表也叫稀疏表,是把上面那个表进行稀疏,有些数据不应该要的就不要,有些数据该要才要按不思想
分析上面那个表的思想:按步思想
然后这个就是每次推断,把每一个可能都写出来
倍增思想
ST表的思想不是这样的,是利用稀疏,也就是倍增思想
不断地取一半取一半就好了,我们拿一个例子把,这样看的更加清晰
我们把这个ST表叫做dp[ i ][ j ]从i开始,长度为2^j的最大值区间
询问操作
[ 0 ][ 5 ]区间找最大值
[ 0 ][ 13 ]区间找最大值
我画了两个不同的图,咋们可以发现什么不,这个其实就是区间的拼凑,拼出一个最大的区间,这个相比较上一个方法其实这个就是类似于一个二分法的方法优化,我下面写的8,4,2其实是想告诉读者这个2^j这个j怎么写,那么不就是[0][3],[8][2],[12][1],可以这么理解,这个i就是左端点的值,这个j就是它的步长
你以为这个是巧合么?其实并不是,这个其实就是二进制
这个就是那个二进制转十进制公式,是不是很神奇,这个就是运用了这个思想,我们把这个长度(也就是十进制数)转化为二进制数字的和(也就是像后面那样的系数*2的几次方)这个系数不是为1就是0
时间复杂度和空间复杂度
我们来计算一下时间复杂度和空间复杂度
时间复杂度:O(m)
空间复杂度:O(n)
你别小看这个log,你自己算算就知道这个可以减很多很多,至于这个怎么计算出这个log,我的文章二叉树里面有讲,感兴趣可以取看看优化
但其实这个是可以优化掉的,我为什么要每次都是不重叠呢?我重叠找出的答案都是一样的,那我们重叠的话,那不就是可以减少很多的事情而且答案还是一样的
这样不是更好么,节省时间复杂度对比0~7和6~13的值就好了,记住这个两个地方的步长都是8,始终记住2^j,这个一定是2的j次方的数字
如何找到那个最长的2的次方的数字呢?我们可以借助log
这个x是这个区间的长度,我们这样就可以获得对应的长度了
我们利用这个思想的话,有两个情况,一,重合 二,相交
思想
我们用一下思想
长度:len=R-L+1
步长:j=(x为区间的长度)
最值:ans=max(dp[L][ j ],dp[R-2^j+1][j])
这个里没有听懂没事,我们可以看下面代码再来看这个,这里说没看懂是这个思想上面这个三行
四,ST表的代码实现
#include <iostream> #include <vector> #include <cmath> #include <algorithm>using namespace std;vector<vector<int>> dp; // dp[i][j] 表示左端点为 i 长度为 2^j 这样的区间,也就是 [i, i+2^j-1]int query(int l, int r) {int j = (int)log2(r - l + 1);return max(dp[l][j], dp[r - (1 << j) + 1][j]); }int main() {vector<int> arr = { 9, 3, 1, 7, 5, 6, 0, 8 };const int n = 8;dp = vector<vector<int>>(n, vector<int>((int)log2(n) + 5, 0));for (int i = 0; i < n; i++) dp[i][0] = arr[i];for (int j = 1; j <= log2(n); j++)for (int i = 0; i + (1 << j) - 1 < n; i++)dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);int l, r;while (cin >> l >> r) {cout << query(l, r) << endl;}return 0; }
这个可能有点难以理解,我们来具体分析一下
容器的定义
dp = vector<vector<int>>(n, vector<int>((int)log2(n) + 5, 0));
这个是构成一个二维的数组利用容器,我这个后面其实不用+5的,这个知识以防万一数组溢出了,所以我就加了个5,然后就是创建一个n*(n+5)的数组,然后初始化为0
为什么是log2(n)呢?
其实我们前面算出了这个空间复杂度,其实他就是按照步长来的,上面也有十进制转二进制的公式
,然后就是我们这个j本就是表示长度,也就是列,所以我们这么写情况一
for (int i = 0; i < n; i++) dp[i][0] = arr[i];
这个是把每一个数字输入到表里面,为了后面的区间的划分建立好基础
情况二
for (int j = 1; j <= log2(n); j++)for (int i = 0; i + (1 << j) - 1 < n; i++)dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
这里就是j就是所说的步长了,为什么这个j再外面,而这个i再里面呢?
我们要知道我们再情况一排版的时候,是同列不同行进行排列的,也就是说我们后面编写这个ST表的时候,我们是需要不断地划分区间,就像上面倍增思想那样,那么我们就要这样
我们是这样取排序的,所以我们就要把这个j放到外面
i表示右端点这个位移大家应该都知道吧,不知道的话我也来讲一讲吧
位移左移操作符
<<
被用来计算2的幂次方。左移操作符将一个数的二进制表示向左移动指定的位数,相当于将该数乘以 2n,其中 n 是移动的位数。例如,
1 << 1
等于2
(十进制的二进制表示是1
,左移一位变成10
,即2
),1 << 2
等于4
(十进制的二进制表示是1
,左移两位变成100
,即4
)为什么这个后面要写成i + (1 << (j - 1))这样子?
其实这个就是我前面所说的i+步长的话,就是找到对对应的数字,然后我们来考虑这个,注意这个是初始化表不是正式区间的最值了,我们这个后面j-1表示对于正在输入列地前面一列,这个i表示步长对对应的值查询
int j = (int)log2(r - l + 1);return max(dp[l][j], dp[r - (1 << j) + 1][j]);
这个j呀在这里就是表示长度啦右端点减去左端点+1,为什么要加1?因为有0这个点,长度是会多一个单位的
返回,怎么确定这个行和列呢?
行
也就是这里的L和R-(1<<j)+1
这里就是表示这个左端点和右端点,然后在这个里面寻找最值
列
这里就是已经确定这个答案在哪一行了,也就是步长
步长决定这个在哪一列找到
行就是我们之前不是细分了很多下区间吗?我们以1,2,3,4,5,6,7,8为例子讲一下
我们把这个1,2,3,4,5,6,7,8制作为ST表是这样的
我们利用上面的思想我们来找一下1~5的最大值,那就是这样的
我们在小区间里面组成大区间
总结
我们通过暴力法 打表法 ST表的优化与不优化来讲的
然后就是ST表的实现,主要是怎么打表和查询
打表:
打表主要是先把值都附在表中,然后根据这个表的初始化情况,利用步长来解决,也就是步长为2,4,8,16逐个进行打表
查询:
这里查询主要是逐个列是我们的最大长度,利用log和长度来解决
行是利用左端点和右端点,左端点不变,右端点-步长+1,这个+1下面可以解释,我们在计算len,就是区间总长度,为什么不是r-len+1,因为我们有j已经把这个这个定位到后面去了,不是1,2,3,4,5,6,7,8这个了,而是4,5,6,7,8这个,所以我们就要减去2^j才可以正确的解出答案,也就是减去对应得找到那个数字