ST表(算法篇)

算法篇之ST表

引言：ST表实际是一个数据结构，但是它本质是基于dp算法的，而算法题中有时也会用到，这边我就归类于算法篇先把

ST表

概念：

ST表适用于解决区间最值的问题(RMQ问题)的数据结构
ST表本质是dp算法，只不过dp是对数组一排一排更新，而RMQ是对数组一列一列动态规划的
预处理时间复杂度为O(nlogn)，查询时间复杂度为O(1)

操作：

例题：给一个数组，有n个数，有m个left，right(left和right为区间边界)，求出这m个区间的最值

首先引入状态f[i][j]，f[i][j]表示从第i个元素开始的长度为2^j个元素的最值
将第i个元素开始的2^j个元素分成长度相等的两部分，每部分的长度为2^j-1
状态转移方程就为：f[i][j]=max(f[i][j-1]，f[i+2^j-1][j-1])，即两部分的最大值
边界条件：f[i][0]=a[i]
要询问区间[L,R]的最大值，因区间[L,R]的长度为R-L+1，求出log₂(R-L+1)的值，设为x
因此区间[L,R]就可以分为[L,L+2^x-1]和[R-2^x+1,R]两个部分，根据状态转移方程可以得出区间[L,R]的最大值：RMQ(L,R)=max(f[L][x],f[R-2^x+1][x])
2^x可以用移位运算1<<x提高效率

int query(int l,int r){int x=(int)log(r-l+1)/log(2);    //在c++中log默认为以10为底，所以需要换底//或者直接使用log2函数int x=(int)log2(r-l+1);return max(f[l][x],f[r-(1<<x)+1][x]);
}

代码：

#include <iostream>
#include <math.h>
using namespace std;
//例子
const int N=1e6+10;
int f[N][20];  //20是由log2(n)+1算出来的
int n,m;int query(int l,int r){
//    int x=(int)log(r-l+1)/log(2);int x=(int)log2(r-l+1);return max(f[l][x],f[r-(1<<x)+1][x]);
}int main() {cin>>n>>m;for(int i=1;i<=n;++i){int p;cin>>p;f[i][0]=p;}//外层循环是遍历列,列不需要遍历到n，而是2的j次方小于等于n// 因为f[i][j]代表的是从i开始的2的j次方个元素的最值，因此j最大只能取到log2(n)for(int j=1;(1<<j)<=n;++j){for(int i=1;i+(1<<j)-1<=n;++i){f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);}}while(m--){int x,y;cin>>x>>y;cout<<query(x,y)<<endl;}system("pause");return 0;
}

例题：

蓝桥杯2415：附近最小

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;int n, k;//ST算法
int query(int l, int r, vector<vector<int>> &f) {int x = (int)log2(r - l + 1);return min(f[l][x], f[r - (1 << x) + 1][x]);
}int main() {cin >> n ;int logn = log2(n) + 1;vector<vector<int>>f(n + 1, vector<int>(logn));for (int i = 1; i <= n; ++i) {cin >> f[i][0];}for (int j = 1; (1 << j) <= n; ++j) {for (int i = 1; i + (1 << j) - 1 <= n; ++i) {f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);}}cin >> k;for (int i = 1; i <= n; ++i) {int l = max(1, i - k);int r = min(n, i + k);cout << query(l, r, f) << " ";}cout << endl;return 0;
}