首页 > 其他 > 详细

模板 - 数据结构 - ST表

时间:2019-03-16 00:55:53      阅读:28      评论:0      收藏:0      [点我收藏+]

标签:两个   its   结构   con   我们   fin   span   bsp   %d   

区间最大值,$O(nlogn)$ 预处理,$O(1)$ 查询,不能动态修改。在查询次数M显著大于元素数量N的时候看得出差距。

 

令 $f[i][j]$ 表示 $[i,i+2^j-1]$ 的最大值。

显然, $f[i][0]=a[i]$ 。 

根据定义式,写出状态转移方程: $f[i][j]=max(f[i][j-1],f[i+2^{j-1}][j-1])$ 。

我们可以这么理解:将区间 $[i,i+2^j-1]$ 分成相同的两部分

中点即为 $(i+(i+2^j-1))/2=i+2^{j-1}-1/2$ 

所以 $[i,i+2^j-1]$ 可以分成 $[i,i+2^{j-1}-1]$ 和 $[i+2^j,i+2^j-1]$ 

 

对于每个询问 $[x,y]$ ,我们把它分成两部分 $f[x][s],f[y-2^s+1][s]$ 

其中 $s=log_2(y-x+1)$ ,虽然这两个区间有重叠,但是重叠不会影响区间的最大值

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int MAXLOGN=17;
const int MAXN=100000;
int a[MAXN+5],f[MAXN+5][MAXLOGN],Logn[MAXN+5];

inline int read() {
    char c=getchar();
    int x=0,f=1;
    while(c<0||c>9) {
        if(c==-)
            f=-1;
        c=getchar();
    }
    while(c>=0&&c<=9) {
        x=x*10+c-0;
        c=getchar();
    }
    return x*f;
}

void init() {
    Logn[1]=0;
    Logn[2]=1;
    for(int i=3; i<=MAXN; i++) {
        Logn[i]=Logn[i/2]+1;
    }
}
int main() { init(); int n=read(),m=read(); for(int i=1; i<=n; i++) f[i][0]=read(); for(int j=1; j<=MAXLOGN; 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]); for(int i=1; i<=m; i++) { int x=read(),y=read(); int s=Logn[y-x+1]; printf("%d\n",max(f[x][s],f[y-(1<<s)+1][s])); } return 0; }

 

模板 - 数据结构 - ST表

标签:两个   its   结构   con   我们   fin   span   bsp   %d   

原文:https://www.cnblogs.com/Yinku/p/10472788.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号