ST表

GA34 · 2025-02-10 21:02:26 · 算法·理论

• 前言

  话说为啥讨论区没了

  不能愉快的学习灌水了

  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。

  根据定义式，第二维就相当于倍增的时候“跳了

  依据倍增的思路，写出状态转移方程 $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)

  好了上代码

#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));
}

• 例题

  后面再修吧