Sparse Table
區間和查詢
給定一個長度為 的序列 和 筆查詢：
Sparse Table 適合用於查詢區間訊息，但不帶任何修改操作的問題。Sparse Table 需要 的空間。
建表
利用倍增法的概念建表。
- 狀態： 記錄第 之間的答案。
- 轉移：
-
的作用和題目有關，例如上敘問題求區間最大值，那麼 。
| 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';
|
查詢時間複雜度是 ， 和 可以先預處理。
應用
可用來查詢區間極值，但不能修改（同個元素會包含在許多區間）。