ST 表

Vision271 · 2022-07-11 22:28:10 · 个人记录

1.概述

• ST 表以倍增的方式记录静态区间的 RMQ 问题解。

  • RMQ(Range Minimum/Maximum Query) 问题：区间最大/最小问题。

2.操作

• ST 表仅支持询问。

3.时间复杂度分析

• 建表 O(n\log_2 n)，查询 O(1)。

4.实现原理：

• 构建一个倍增数组（实质上很像 DP ）：

• 即，st_{k,i} 表示 i\sim i+2^k-1 这一段的最大/最小。

5.例题与示范代码

• 暂时没有。