1. 首页
  2. 算法模板

ST表

简介

给定一个长度为 n 的数组,支持 O(1) 查询区间最值。
使用前,调用 init() 函数初始化 ST,然后使用 query() 函数查询区间最值。
当前代码实现区间最小值问题,区间的最大值,最大公约数等均可以查询。

原理

预处理出原区间内长度为 1, 2, 4, \cdots, 2^k 的子区间的答案,此预处理的复杂度为 O(n \log n)
预处理的时,长度为 1 的子区间信息直接从原数组中得到。长度大于 12^k 的子区间信息由两个长度为 2^{k-1} 的区间合并得到。如下图中,表示 [1, 8] 的橘红色区间,由两个长度为 4 的灰色区间([1,4], [5,8])合并得到,黑色箭头表示合并操作。

查询的时候,先寻找区间覆盖查询区间的两个预处理长度为 2^k 的区间,要求 2^k 小于等于查询区间长度且最大,用从查询区间左侧起与右侧起的两个 2^k 区间的答案组合出查询答案,单次查询复杂度 O(1)
如下图,蓝色区间表示查询区间 [3, 8],长度为 6,那么我们可以找到两个长度为 4 的区间([3, 6], [5, 8])将其完全覆盖。

示例

代码

namespace SparseTable{
    const int MAXN=1e5+50;
    int lg2[MAXN];
    int dp[MAXN][20];
    void init(int v[], int n){
        lg2[0]=-1;
        for (int i=1; i<MAXN; i++) lg2[i]=lg2[i>>1]+1;
        for (int i=1; i<n; i++) dp[i][0]=v[i];
        for (int j=1; (1<<j)<n; ++j){
            for (int i=1; i+(1<<(j-1))<n; i++){
                dp[i][j]=min(dp[i][j-1], dp[i+(1<<(j-1))][j-1]);
            }
        }
    }   
    int query(int l, int r){
        if (l>r) return 1e9;
        int k=lg2[r-l+1];
        return min(dp[l][k], dp[r-(1<<k)+1][k]);
    }
}
评分 0, 满分 5 星
0
0
看完收藏一下,下次也能找得到
0
上一篇:
:下一篇

发表评论

gravatar

沙发空缺中,还不快抢~