ST表学习笔记
标签搜索
侧边栏壁纸
博主昵称
Lez

  • 累计撰写 14 篇文章
  • 累计收到 0 条评论

ST表学习笔记

Lez
Lez
2023-04-20 / 0 评论 / 25 阅读 / 正在检测是否收录...

ST表学习笔记

什么是ST表

ST 表(Sprase Table),也叫稀疏表。

主要用于解决 RMQ(Range Minimum/Maximum Query,区间最值查询)问题。

如何预处理ST表

实际上,ST表是一种动态规划

我们需要用 $O(n \log n)$ 的时间预处理一张表,然后仅需 $O(1)$ 查询区间最大/最小值。

我们设 $f_{i, j}$ 为以第 $i$ 个数为起点,长度为 $2^j$ 的区间中的最大值,这里 $f$ 的定义可以为 int f[N+5][log(N)+5];

以下是代码,其中区间终点为 $i+2^j-1 \leqslant n$,状态转移方程是 $f_{i,j} = max(f[i][j-1], f[i+2^{j-1}][j-1])$。

for (int i=1; i<=n; ++i) cin >> f[i][0];

for (int j=1; j<=20; ++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]);

如何查询ST表

考虑对查询区间 $[l, r]$ 做分割拼凑

区间长度的指数 $k = \log(r-l+1)$

for (int i=1; i<=m; ++i) {
    cin >> l >> r;
    int k = log2(r-l+1);
    cout << max(f[l][k], f[r-(i<<k)+1][k]);
}

总结

ST表的使用范围:符合结合律并且可重复贡献的信息查询。
如果涉及区间修改,就要使用线段树

参考文献

liangbowen - ST 表学习笔记
董晓算法 - 35 ST表 RMQ问题

0

评论 (0)

取消