ST表

前言

话说为啥讨论区没了

不能愉快的学习灌水了

ST表这种基础还没学我真是弱爆了
ST表的概念及实现

这也是一种倍增的应用

倍增在OI的应用还是很多的

ST表可以说是DP和倍增的完美结合

首先要知道区间最大值是一个具有"可重复贡献"性质的问题

这个性质是什么

就是说如果用来求解的预处理区间有重叠部分

这些区间的并是所求的区间

最终计算出的答案就是正确的

用式子咳血地表达一下就是说

对于区间 $[l,r]$

有子区间 $[l,r1]$ , $[r1+1,r]$

则 $max[l,r]=max(max[l,r1],max[r1+1,r])$

有了这个东西我们能干什么呢

如果手动模拟一下

容易发现我们能使用至多两个预处理过的区间来覆盖询问区间

也就是说询问时的时间复杂度可以被降至 $\mathcal{O}(1)$

在处理有大量询问的题目时十分有效

具体实现如下

令 $f(i,j)$ 表示区间 $(i,i+2^j-1)$ 的最大值。

显然 $f(i,0)=i$ 。

根据定义式，第二维就相当于倍增的时候“跳了 $2^j-1$ 步”

依据倍增的思路，写出状态转移方程

$f(i,j)=max(f(i,j-1),f(i+2^j-1,j-1))$

而对于每个询问 $[l,r]$

可以分成两个部分 $f(l,l+2^s-1)$ 和 $f(r-2^s-1,r)$

其中 $s=log(r-l+1)$

好了上代码

CPP

#include <cmath>
#include <iostream>
using namespace std;

int a[50001];
int f[50001][16];
int n;

void rmq_init()  //建立： dp(i,j) = min{dp(i,j-1),dp(i+2^(j-1),j-1)   O(nlogn)
{
    for (int i = 1; i <= n; i++)
        f[i][0] = a[i];
    int k = floor(log((double)n) / log(2.0));  // C/C++取整函数ceil()大,floor()小
    for (int j = 1; j <= k; j++)
        for (int i = n; i >= 1; i--) {
            if (i + (1 << (j - 1)) <=
                n)  // f(i,j) = min{f(i,j-1),f(i+2^(j-1),j-1)
                f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
        }
}

int rmq(int i, int j)  //查询：返回区间[i,j]的最小值     O(1)
{
    int k = floor(log((double)(j - i + 1)) / log(2.0));
    return min(f[i][k], f[j - (1 << k) + 1][k]);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    rmq_init();
    printf("%d\n", rmq(2, 5));
}

例题
后面再修吧

文章操作

前言

ST表的概念及实现

例题

相关推荐

评论

ST表