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

淡淡交会过,各不留下印 | 在路上

  • 累计撰写 10 篇文章
  • 累计收到 34 条评论

ST表学习笔记

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

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问题

1

评论 (6)

取消
  1. 头像
    xxoceeethv
    Windows 10 · Google Chrome

    选材新颖独特,通过细节描写赋予主题鲜活生命力。

    回复
  2. 头像
    pnlznkbgug
    Windows 10 · Google Chrome

    老话题新解读,展现了深刻的反思精神。

    回复
  3. 头像
    zfbejvkflp
    Windows 10 · Google Chrome

    语言简洁明快,用词精准,毫无赘余。

    回复
  4. 头像
    ntaxtfoadz
    Windows 10 · Google Chrome

    文献引用规范,学术态度严谨,值得借鉴。

    回复
  5. 头像
    uaxfmlsgbj
    Windows 10 · Google Chrome

    作者的布局谋篇匠心独运,让读者在阅读中享受到了思维的乐趣。

    回复
  6. 头像
    jjhqzmonub
    Windows 10 · Google Chrome

    文章结构紧凑,层次分明,逻辑严密,让人一读即懂。

    回复