ST表(算法篇)

算法篇之ST表

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

ST表

概念：

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

操作：

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

1. 首先引入状态f[i][j]，f[i][j]表示从第i个元素开始的长度为2^j个元素的最值
2. 将第i个元素开始的2^j个元素分成长度相等的两部分，每部分的长度为2^j-1
3. 状态转移方程就为：f[i][j]=max(f[i][j-1]，f[i+2^j-1][j-1])，即两部分的最大值
4. 边界条件：f[i][0]=a[i]
5. 要询问区间[L,R]的最大值，因区间[L,R]的长度为R-L+1，求出log₂(R-L+1)的值，设为x
6. 因此区间[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])
7. 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;
}

原文地址：https://blog.csdn.net/hellmorning/article/details/142311118

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！