跳转至

ST 表

定義

ST 表示意圖

ST 表是用於解決 可重複貢獻問題 的數據結構。

什麼是可重複貢獻問題？

可重複貢獻問題 是指對於運算 \(\operatorname{opt}\)，滿足 \(x\operatorname{opt} x=x\)，則對應的區間詢問就是一個可重複貢獻問題。例如，最大值有 \(\max(x,x)=x\)，gcd 有 \(\operatorname{gcd}(x,x)=x\)，所以 RMQ 和區間 GCD 就是一個可重複貢獻問題。像區間和就不具有這個性質，如果求區間和的時候採用的預處理區間重疊了，則會導致重疊部分被計算兩次，這是我們所不願意看到的。另外，\(\operatorname{opt}\) 還必須滿足結合律才能使用 ST 表求解。

什麼是 RMQ？

RMQ 是英文 Range Maximum/Minimum Query 的縮寫，表示區間最大（最小）值。解決 RMQ 問題有很多種方法，可以參考 RMQ 專題。

引入

ST 表模板題

題目大意：給定 \(n\) 個數，有 \(m\) 個詢問，對於每個詢問，你需要回答區間 \([l,r]\) 中的最大值。

考慮暴力做法。每次都對區間 \([l,r]\) 掃描一遍，求出最大值。

顯然，這個算法會超時。

ST 表

ST 表基於 倍增 思想，可以做到 \(\Theta(n\log n)\) 預處理，\(\Theta(1)\) 回答每個詢問。但是不支持修改操作。

基於倍增思想，我們考慮如何求出區間最大值。可以發現，如果按照一般的倍增流程，每次跳 \(2^i\) 步的話，詢問時的複雜度仍舊是 \(\Theta(\log n)\)，並沒有比線段樹更優，反而預處理一步還比線段樹慢。

我們發現 \(\max(x,x)=x\)，也就是説，區間最大值是一個具有「可重複貢獻」性質的問題。即使用來求解的預處理區間有重疊部分，只要這些區間的並是所求的區間，最終計算出的答案就是正確的。

如果手動模擬一下，可以發現我們能使用至多兩個預處理過的區間來覆蓋詢問區間，也就是説詢問時的時間複雜度可以被降至 \(\Theta(1)\)，在處理有大量詢問的題目時十分有效。

具體實現如下：

令 \(f(i,j)\) 表示區間 \([i,i+2^j-1]\) 的最大值。

顯然 \(f(i,0)=a_i\)。

根據定義式，第二維就相當於倍增的時候「跳了 \(2^j-1\) 步」，依據倍增的思路，寫出狀態轉移方程：\(f(i,j)=\max(f(i,j-1),f(i+2^{j-1},j-1))\)。

以上就是預處理部分。而對於查詢，可以簡單實現如下：

對於每個詢問 \([l,r]\)，我們把它分成兩部分：\([l,l+2^s-1]\) 與 \([r-2^s+1,r]\)，其中 \(s=\left\lfloor\log_2(r-l+1)\right\rfloor\)。兩部分的結果的最大值就是回答。

ST 表的查詢過程

根據上面對於「可重複貢獻問題」的論證，由於最大值是「可重複貢獻問題」，重疊並不會對區間最大值產生影響。又因為這兩個區間完全覆蓋了 \([l,r]\)，可以保證答案的正確性。

模板代碼

ST 表模板題

C 風格模板

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;
const int logn = 21;
const int maxn = 2000001;
int f[maxn][logn + 1], Logn[maxn + 1];

int read() {  // 快读
  char c = getchar();
  int x = 0, f = 1;
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return x * f;
}

void pre() {  // 准备工作，初始化
  Logn[1] = 0;
  Logn[2] = 1;
  for (int i = 3; i < maxn; i++) {
    Logn[i] = Logn[i / 2] + 1;
  }
}

int main() {
  int n = read(), m = read();
  for (int i = 1; i <= n; i++) f[i][0] = read();
  pre();
  for (int j = 1; j <= logn; 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表具体实现
  for (int i = 1; i <= m; i++) {
    int x = read(), y = read();
    int s = Logn[y - x + 1];
    printf("%d\n", max(f[x][s], f[y - (1 << s) + 1][s]));
  }
  return 0;
}

C++ 風格模板

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;

template <typename T>
class SparseTable {
  using VT = vector<T>;
  using VVT = vector<VT>;
  using func_type = function<T(const T &, const T &)>;

  VVT ST;

  static T default_func(const T &t1, const T &t2) { return max(t1, t2); }

  func_type op;

 public:
  SparseTable(const vector<T> &v, func_type _func = default_func) {
    op = _func;
    int len = v.size(), l1 = ceil(log2(len)) + 1;
    ST.assign(len, VT(l1, 0));
    for (int i = 0; i < len; ++i) {
      ST[i][0] = v[i];
    }
    for (int j = 1; j < l1; ++j) {
      int pj = (1 << (j - 1));
      for (int i = 0; i + pj < len; ++i) {
        ST[i][j] = op(ST[i][j - 1], ST[i + (1 << (j - 1))][j - 1]);
      }
    }
  }

  T query(int l, int r) {
    int lt = r - l + 1;
    int q = floor(log2(lt));
    return op(ST[l][q], ST[r - (1 << q) + 1][q]);
  }
};

注意點

  1. 輸入輸出數據一般很多，建議開啓輸入輸出優化。

  2. 每次用 std::log 重新計算 log 函數值並不值得，建議進行如下的預處理：

\[ \begin{cases} \texttt{Logn}[1] \gets 0, \\ \texttt{Logn}\left[i\right] \gets \texttt{Logn}\left[\frac{i}{2}\right] + 1. \end{cases} \]

ST 表維護其他信息

除 RMQ 以外，還有其它的「可重複貢獻問題」。例如「區間按位和」、「區間按位或」、「區間 GCD」，ST 表都能高效地解決。

需要注意的是，對於「區間 GCD」，ST 表的查詢複雜度並沒有比線段樹更優（令值域為 \(w\)，ST 表的查詢複雜度為 \(\Theta(\log w)\)，而線段樹為 \(\Theta(\log n+\log w)\)，且值域一般是大於 \(n\) 的），但是 ST 表的預處理複雜度也沒有比線段樹更劣，而編程複雜度方面 ST 表比線段樹簡單很多。

如果分析一下，「可重複貢獻問題」一般都帶有某種類似 RMQ 的成分。例如「區間按位與」就是每一位取最小值，而「區間 GCD」則是每一個質因數的指數取最小值。

總結

ST 表能較好的維護「可重複貢獻」的區間信息（同時也應滿足結合律），時間複雜度較低，代碼量相對其他算法很小。但是，ST 表能維護的信息非常有限，不能較好地擴展，並且不支持修改操作。

練習

RMQ 模板題

「SCOI2007」降雨量

[USACO07JAN] 平衡的陣容 Balanced Lineup

附錄：ST 表求區間 GCD 的時間複雜度分析

在算法運行的時候，可能要經過 \(\Theta(\log n)\) 次迭代。每一次迭代都可能會使用 GCD 函數進行遞歸，令值域為 \(w\)，GCD 函數的時間複雜度最高是 \(\Omega(\log w)\) 的，所以總時間複雜度看似有 \(O(n\log n\log w)\)。

但是，在 GCD 的過程中，每一次遞歸（除最後一次遞歸之外）都會使數列中的某個數至少減半，而數列中的數最多減半的次數為 \(\log_2 (w^n)=\Theta(n\log w)\)，所以，GCD 的遞歸部分最多隻會運行 \(O(n\log w)\) 次。再加上循環部分（以及最後一層遞歸）的 \(\Theta(n\log n)\)，最終時間複雜度則是 \(O(n(\log w+\log x))\)，由於可以構造數據使得時間複雜度為 \(\Omega(n(\log w+\log x))\)，所以最終的時間複雜度即為 \(\Theta(n(\log w+\log x))\)。

而查詢部分的時間複雜度很好分析，考慮最劣情況，即每次詢問都詢問最劣的一對數，時間複雜度為 \(\Theta(\log w)\)。因此，ST 表維護「區間 GCD」的時間複雜度為預處理 \(\Theta(n(\log n+\log w))\)，單次查詢 \(\Theta(\log w)\)。

線段樹的相應操作是預處理 \(\Theta(n\log x)\)，查詢 \(\Theta(n(\log n+\log x))\)。

這並不是一個嚴謹的數學論證，更為嚴謹的附在下方：

更嚴謹的證明

理解本段，可能需要具備 時間複雜度 的關於「勢能分析法」的知識。

先分析預處理部分的時間複雜度：

設「待考慮數列」為在預處理 ST 表的時候當前層循環的數列。例如，第零層的數列就是原數列，第一層的數列就是第零層的數列經過一次迭代之後的數列，即 st[1..n][1]，我們將其記為 \(A\)。

而勢能函數就定義為「待考慮數列」中所有數的累乘的以二為底的對數。即：\(\Phi(A)=\log_2\left(\prod\limits_{i=1}^n A_i\right)\)。

在一次迭代中，所花費的時間相當於迭代循環所花費的時間與 GCD 所花費的時間之和。其中，GCD 花費的時間有長有短。最短可能只有兩次甚至一次遞歸，而最長可能有 \(O(\log w)\) 次遞歸。但是，GCD 過程中，除最開頭一層與最末一層以外，每次遞歸都會使「待考慮數列」中的某個結果至少減半。即，\(\Phi(A)\) 會減少至少 \(1\)，該層遞歸所用的時間可以被勢能函數均攤。

同時，我們可以看到，\(\Phi(A)\) 的初值最大為 \(\log_2 (w^n)=\Theta(n\log w)\)，而 \(\Phi(A)\) 不增。所以，ST 表預處理部分的時間複雜度為 \(O(n(\log w+\log n))\)。

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用