ST表模板

发布于 2017-11-03  1844 次阅读


O(1)求静态区间极值的算法


题目链接
在生活中,总会遇到这样一些题目:
在长度为N的数列中多次查找某区间的最大值。
于是,ST表应运而生

算法描述

ST表是一个可以在* O(nlogn) *的时间复杂度的预处理后,在 * O(1) * 的时间复杂度中查找任意区间的最大值
此算法基于倍增思想。

算法实现

此算法分预处理和查询

预处理

预处理一个st数组,对于$st[i][j]$,表示此序列第i位往后$2^j$位的最大值。
我们以最大值查询为例,预处理可以写成:
$st[i][j] = max(st[i][j-1],st[i+2^{k-1}][k-1])$
意思为区间$[i,i+2^j]$的最大值是区间$[i,i+2^{j-1}]$的最大值和区间$[i + 2{j-1},i + 2^j]$的最大值的最大值

显而易见,时间复杂度是O(nlogn)

查询

我们从预处理中可知,我们求一个区间的最大值,可以转化为求在此区间内,完全覆盖该区间的多个区间最大值的最大值
表示看不懂的看下面:
例如,我们有一个区间[1,10],我们可以通过取[1,5]和[6,10]两个区间的最大值,来找出[1,10]的最大值。但有时我们并不会运气这么好,例如我们只有[1,7]和[3,10]的最大值,但是取最大值后答案也是对的。
So,对于一个区间[l,r]我们可以算出一个数字c,让$c = log_2(r - l + 1)$,这样区间[l,r]的最大值就是$max(st[a][c],st[a - 2^b +1][c])$
然后,这就是 $O(1)$ 查询方法。

一些小问题

Q1:如何计算出$log_2(r - l + 1)$?
A1:这里在有的文章中建议你预处理出来,但这里我们选择cmath库函数

int c = log2(r - l + 1); //开头需加上 #include<cmath>

Q2:如何计算$2^j$?
A2:对于幂运算,我们选择位运算。
因为这是2的幂运算,所以能用位运算。

int a = 1 << j; //a表示2^j

Q3:st表需要开多大?
A3:不需要开很大。空间复杂度仅为$nlog_2n$
即开一个$log_2n$行n列的二维数组即可。

代码实现

#include <iostream>
#include <cstdio>
#include <cmath>
#define MAXN 10001
using namespace std;

int st[MAXN][30];
int n,q,a,b;

void init(){  //初始化st数组
    int c = log2(MAXN);
    for(int i = 1;i < c;i++)
        for(int j = 0;j + (1 << i - 1) < MAXN;j++)
            st[j][i] = max(st[j][i - 1], st[j + (1 << i - 1)][i-1]);
}

int find(int l,int r){  //查找
    int c = log2(r - l + 1);
    return max(st[l][c],st[r - (1 << c) + 1][c]);
}

int main(){
    scanf("%d%d",&n,&q);
    for(int i = 1; i<= n;i++)
        scanf("%d",&st[i][0]);
    init();
    for(int i = 1;i <= q;i++){
        scanf("%d%d",&a,&b);
        printf("%d%c",find(a,b),'\n');
    }
    return 0;
}

一个OIer。