Skip to content

Sparse Table

區間和查詢

給定一個長度為 的序列 和 筆查詢：

  • x y：詢問 之間的最大值。

Sparse Table 適合用於查詢區間訊息，但不帶任何修改操作的問題。Sparse Table 需要 的空間。

建表

利用倍增法的概念建表。

  • 狀態： 記錄第 之間的答案。
  • 轉移：
  • 的作用和題目有關，例如上敘問題求區間最大值，那麼 。

1
2
3
4
5
6
7
8
9
for (int i = 0; i < N; ++i)
    cin >> sp[0][i];
for (int i = 1; i < LOG; ++i)
{
    for (int j = 0; j + p2[i] - 1 < n; ++j)
    {
        sp[i][j] = max(sp[i - 1][j], sp[i - 1][j + p2[i - 1]]);
    }
}

總共有 個狀態，每個狀態會花 時間轉移，整題時間複雜度為 。

查詢

假設要查詢的區間 ，現在要適合的兩個長度為 的區間剛好覆蓋住 ，兩個區間可能重疊，但不能超出 之外。 會是 ，這兩個區間的起點會是 和 。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
// 預處理
p2[0] = 1;
lg2[1] = 0;
lg2[2] = 1;
for(int i = 0; i < LOG; ++i) p2[i] = p2[i - 1] << 1;
for(int i = 3; i < MXN; ++i) lg2[i] = lg2[(i >> 1)] + 1;

// 查詢
int L, R;
cin >> L >> R;
int lg = lg2[R - L + 1];
cout << max(sp[lg][L], sp[lg][R - p2[lg] + 1]) << '\n';

查詢時間複雜度是 ， 和 可以先預處理。

應用

可用來查詢區間極值，但不能修改（同個元素會包含在許多區間）。

  1. Sparse Table - WiwiHo 的競程筆記 ↩