跳转至

ST 表

引入

什么是 ST 表?

ST 表是一种基于倍增思想、用来解决可重复贡献问题的数据结构。那么什么是可重复贡献问题呢?

假设现在有一个运算 opt,若 xoptx 正好等于 x,那么对应的区间询问就是一个可重复贡献问题。(例如求 aloptal+1optoptar)。比如区间最大值、区间最大公因数。另外,opt 还需要满足结合律:aoptboptc=aopt(boptc),这也是快速幂、线段树等所需要的。

接下来,好渴鹅将会以静态区间最值查询为例子(简称 RMQ,Range Maximum/Minimum Query)来讲述 ST 表的实现。

算法思想

基于 dp 和倍增。

我们可以将区间拆分成 log2 个长度为 2x 的块,然后将两个块取最大值合并成一个块,那么这个问题就成了最优子结构问题。设 dpi,j 表示为 ii+2j1 这个区间内的最大值,那么很显然 dpi,0=ai。那么我们就以 j 为拓扑序,然后将长度为 2j 的块划分成两个 2(j1) 的块,那么第一个块的起始位置为 i,第二个块的起始位置为 i+2j,取最大值即可。

然后对于询问,大家可能一下就可以想到将序列长度进行二进制拆解,然后调用之前的 dp 数组,在所有小块中取出最大值。这样做是 O(log2n) 的,不够优秀。

事实上,我们取最大值的数组是可以重叠的。我们就直接找到小于序列长度的最大的 log 值,假设为 x,然后把 l 往后 x 位和 r 往前 x 位取最大值,就行了。log2i 可以通过 O(n) 的预处理快速求出。

时间复杂度:预处理 + dp O(nlog2n),询问 O(1)

代码

代码 - ST 表
void pre() {
  log[1] = 0, log[2] = 1;
  for (int i = 3; i <= kMaxN; i++) {
    log[i] = log[i >> 1] + 1;
  }
  for (int j = 1; j <= kLog; 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]);
    }
  }
}

int query(int l, int r) {
  int s = log[r - l + 1];
  return max(f[l][s], f[r - (1 << s) + 1][s]);
}

补充

其他求区间最值的方法还有线段树和树状数组,单词询问时间复杂度为 O(log2n)。与 ST 表不同的是,这两货支持动态修改。这两货也是非常重要的数据结构,在今后的学习过程中好渴鹅会重点讲解。

评论