Hello!
本篇延續了上一篇的內容。
本篇主要是參考 ( 抄襲 ) 這個大神的筆記。
假如看到內容有錯誤的話，再麻煩跟我說一聲了~
稀疏表 ( sparse table)
在前綴和中，我們可以在 O(1) 的時間找出某個區間的和，那現在我們想要找的是某個區間的最大值或最小值該怎麼辦呢？
剛剛我們看過了分塊法，會將一個長陣列分成一個個長度為 sqrt(n) 的區塊。最後可以得到 O(n * sqrt(n)) 的時間複雜度。假如我們繼續將長度為 sqrt(n) 長度的區塊，繼續細分為許多長度為 sqrt(sqrt(n)) 的區塊，會不會讓複雜度更低呢？
這時候 sparse table 就是一個好用的資料結構了。
建立一張稀疏表， s[i][j]，這個二維陣列的每一個元素代表了一個區塊。i 代表從原本的陣列的第幾個元素開始， j 代表這個塊的大小為 2 的 j 次方。
舉個簡單的例子
假設現在我們希望能區間查找某個區間的最大值。原始的陣列 :
int a[10] = {3, 2, 4, 5, 6, 8, 1, 2, 9, 7};
並另外定義一個 sparse table : int s[10][4];
s[3][0] ==> 代表由第 3 個元素開始，且這個塊的大小為 2 的 0 次方
==> 所以這個區塊為 [5]，只有一個元素
s[2][3] ==> 代表由第 2 個元素開始，且這個塊的大小為 2 的 3 次方
==> 所以這個區塊為 [2, 4, 5, 6, 8, 1, 2, 9]
s[0][4] ==> 代表由第 0個元素開始，且這個塊的大小為 2 的 4 次方，但是因為初始陣列並沒有那麼大，所以這個區塊的大小會小於 16
==> 這個區塊為 [3, 2, 4, 5, 6, 8, 1, 2, 9, 7]，共 10 個元素s[i][j]，當 j 等於 0 的時候，因為區塊的大小為 1 ，所以值可以直接從初始的陣列拿取
==> s[i][0] = a[i];
s[i][j]，當 j 不等於 0 的時候，該區塊的值可由 s[i][j - 1], s[i+2^(j - 1)][j - 1] 求出，假設我們現在希望求區間內的元素最大值
==> s[i][j] = max(s[i][j - 1], s[i + 2^(j - 1)][j - 1])
-----
於是建稀疏表的時候，可得動態規劃的算式
if j == 0:
s[i][j] = a[j];
if j != 0:
s[i][j] = max(s[i][j - 1], s[i + 2^(j - 1)][j - 1]);
-----
在查表的時候，則可以用 1~2 塊區塊來得出值，只需要 O(1) 的時間。
舉個例子，想要查找從第二個數字到第八個數字 ([3, 8]) 的值，因為該區間大小為 6， 所以需要查詢兩塊大小為 4 的區塊 [3, 6], [5, 8]。
--> max(s[3][2], s[5][2]);
想的再更通用一點，假如區間為 [left, right]
則解為 max(s[left][log2(right - left + 1)], s[right - pow(2, log2(right - left + 1)) + 1][log2(right - left + 1])
P.S. 這裡的 log2 指的是 C++ 在 cmath 標頭檔裡提供的 function。
例題：239. Sliding Window Maximum
→ 區間查詢 ( 區間最大值 )
這一題是一個特例，因為每次查詢的區間大小都相同，所以有比 sparse table 更快的做法。
例題：ZeroJudge d539
→ 區間查詢 ( 區間最大值 )
這邊以 例題：ZeroJudge d539 為例：
初始化的複雜度： O(n log n)
查詢的複雜度 : O(1)
但是我的實作在大測資會 TLE ， 再麻煩神人指點了。 < _ _ >
#include <iostream>
#include <vector>
#include <cmath>
#include <cstdio>using namespace std;void initialize_sparse_table(vector<int> &input, vector<vector<int>> &sparse_table,
int start, int log_2_len) {
// log_2_len = log_2(len)
int len = pow(2, log_2_len);
int pow2 = pow(2, log_2_len - 1); if(start >= input.size()) {
return;
} if(log_2_len == 0) {
sparse_table[start][0] = input[start];
return;
} if(sparse_table[start][log_2_len] != 0) {
return;
} initialize_sparse_table(input, sparse_table,
start, log_2_len - 1); if(start + pow2 < input.size()) {
initialize_sparse_table(input, sparse_table,
start + pow2, log_2_len - 1);
} if(start + pow2 < input.size()) {
sparse_table[start][log_2_len] = max(sparse_table[start][log_2_len - 1],
sparse_table[start + pow2][log_2_len - 1]);
} else {
sparse_table[start][log_2_len] = sparse_table[start][log_2_len - 1];
}}int lookUp(vector<int> &input, vector<vector<int>> &sparse_table, int left, int right) {
int len = right - left + 1;
int log_2_len = 0; log_2_len = log2(len);
int pow2 = pow(2, log_2_len); return max(sparse_table[left][log_2_len], sparse_table[right - pow2 + 1][log_2_len]);
}int main(int argc, char *argv[]) { string st;
cin >> st; int n = atoi(st.c_str());
vector<int> input = vector<int>(n);
for(int i = 0;i < n;i++) {
int t;
scanf("%d", &t);
input[i] = t;
} cin >> st;
n = atoi(st.c_str()); int cols = 0;
int tmp = 1; while(tmp < input.size()) {
cols++;
tmp *= 2;
}
cols++; vector<vector<int>> sparse_table = vector<vector<int>>(input.size() + 1, vector<int>(cols, 0)); for(int i = 1;i < sparse_table[0].size();i++) {
for(int j = 0;j < input.size();j++) {
initialize_sparse_table(input, sparse_table, j, i);
}
} for(int i = 0;i < n;i++) {
int a, b;
scanf("%d %d", &a, &b); int left = min(a, b);
int right = max(a, b); int ans = 0;
ans = lookUp(input, sparse_table, left - 1, right - 1);
cout << ans << endl;
} return 0;
}
Bye!
接下來要開始學習困難的線段樹 ( segment tree) 以及 Binary Indexed Tree 了 !
Reference
- 區間問題概述 — 這篇太厲害了!
- Segment tree & Lazy Propagation
- 大神的線段樹筆記
- wikipedia : 線段樹
- 建國中學，演算法講義 : 線段樹詳解
- 資訊之芽算法班
- 資訊之芽
https://www.csie.ntu.edu.tw/~sprout/algo2018/ppt_pdf/segment_tree.pdf
https://www.csie.ntu.edu.tw/~sprout/algo2018/ppt_pdf/segment_tree_2.pdf
https://www.csie.ntu.edu.tw/~sprout/algo2018/ppt_pdf/Segment_Tree_inclass.pdf
