ST(Sparse Table,稀疏表)

ST(Sparse Table,稀疏表)

May 27, 2024

Content #

ST（Sparse Table，稀疏表）算法采用了 倍增原理，在 O(nlogn)时间构造一个二维表之后，可以在 O(1)时间在线查询[l, r]区间的最值，有效解决在线 RMQ（Range Minimum/Maximum Query，区间最值查询）问题。

设 F[i, j]表示[i, i+2^j-1]区间的最值，区间长度为 2^j。

根据倍增思想，长度为 2^j 的区间可被分成两个长度为 2^(j-1) 的子区间，然后求两个子区间的最值即可。递推公式：

F[i, j]=max(F[i, j-1], F[i+2^(j-1), j-1])

ST创建 #

若数组长度为n，最大区间长度为 \(2^k \le n \le 2^(k+1)\)，因此 \[k = \log_2 n\]

for (int i = 1; i <= n; i++) {
  F[i][0] = a[i];
}
int k = log2(n);
for (int j = 1; j <= k; j++) {
  for (int i = 1; i <= n - (1 << j) + 1; i++) {
    F[i][j] = max(F[i][j-1], F[i + 1 << (j - 1)][j - 1])
  }
}

以下面数组为例，写出ST。

a[1..10]={5,3,7,2,12,1,6,4, 8,15}

ST查询 #

若查询[l,r]区间的最值，则首先计算 k 值，区间长度为 r-l+1，

k=log2(r-l+1)。

可以将查询区间分为两个子查询区间，取两个区间的最值即可。两个区间分别为:

a[l] ... a[l+2^k-1]  #l向后的2^k个数
a[r-2^k+1] ... a[r]  #r向前的2^k个数

这两个区间可能有重叠，但对求最值没有影响。 ST中的区间的长度都是2的指数次方，区间查询就要利用这一点，出现重叠就不可避免。理解这一点，才能明白右区间的起点不会是F[i+2^k].

int st_query(int l, int r) {
  int k = log2(r - l + 1);
  return max(F[l][l + (1 << k) - 1], F[r - (1 << k) + 1][r]);
}

算法分析 #

创建 ST 时，初始化需要 O(n)时间，两个 for 循环需要 O(nlogn)时间，总时间复杂度为 O(nlogn)。区间查询实际上是查表的过程，计算 k 值后从表中读取两个数取最大值即可，因此查询的时间复杂度为 O(1)。一次建表，多次使用，这种查表法就是动态规划。

From #

《算法训练营进阶篇》 陈小玉

POJ3264