ST表 笔记

介绍

$nlog(n)$时间复杂度解决RMQ问题。

原理

让我们的每一对区间都可以用至多两个区间来进行覆盖，这样我们就可以通过两个区间的最大值比较来得到新的区间的最大值。

实现

我们用 $f[i][j]$表示区间$(i,i+2^{j}-1)$的区间的最大值，我们的这个区间也可以用$(i,i+2^{j-1}-1)$和$(i+2^{j-1},(i+ 2^{j-1}) + 2^{j-1} - 1)$这两个区间来进行覆盖，用f数组来表示就是$f[i][j-1]$和$f[i + (1LL << (j-1))][j-1]$。因此我们就可以得到:

$f[i][j] = max(f[i][j-1],f[i + (1LL << (j-1))][j-1])$

 

我们就可以得到初始化时的代码

for(int j = 1 ; j <= (int)log2(n) + 1 ; ++ j ){
    for(int i = 1;i <= n ; ++ i){
        f[i][j] = max(f[i][j-1],f[i + (1LL << (j-1))][j-1]) ;
    }
}

 

对于查询时，根据 l 和 r ，我们可以通过这个区间的长度为$k = log2(r-l+1)$，就可以得到我们的第一个区间$(l,l+2^{k}-1)$，但很明显我们的区间有可能没有完全覆盖因为我们的指数是向下取整了，所以我们还需要从右边r开始往左来划定一个区间$(r-2^{k}+1,r)$，这两个区间一定会有重叠，但一定能覆盖我们的这个个区间，这两个区间用(f)数组来表示就是$f[l][k]$和$f[r-(1<<k)+1][k]$，由此我们就可以得到我们查询代码。

l = read() ;
r = read() ;
int k = log2(r - l + 1) ;
ans = max(f[l][k],f[r-(1<<k)+1][k]) ;