# Sparse Table(稀疏表)
Sparse Table是一種資料結構，在$O(nlogn)$的時間複雜度做預處理，並可以進行$O(1)$的查詢，Sparse Table常被用在RMQ的題目，可以視題目需求更改$min()$、$max()$、$gcd()$、$sum()$。其中預處理的方式會使用到倍增法(Binary Lifting)，由於建表需要花$O(nlogn)$，所以如果要使用Sparse Table必須在不帶修改的題目才比較合適。
## 找區間MAX(<a href="https://zerojudge.tw/ShowProblem?problemid=d539">zerojudge d539</a>)
:::success
給一個數列$T1,T2,T3....Tn$，求$Ta$到$Tb$之間(涵蓋$Ta$、$Tb$)的最大值。
#### 範例輸入
```
10
3 2 4 5 6 8 1 2 9 7
7
1 5
3 5
1 10
5 8
6 6
2 4
2 9
```
#### 範例輸出
```
6
6
9
8
8
5
9
```
:::
### $O(nlogn)$預處理
- 這個題目我們要先定義一個$dp[i][j]$，表示從j當作起點並向後延伸$2^j$個元素的最小值。
例如$dp[0][3]$代表區間$[3, 3]$，因為起點也算是一個元素，或例如$dp[2][4]$代表區間$[4, 7]$。
- 此時$dp[i][j]$也就是區間$[i, i + 2 ^ j - 1]$的最大值，其中長度為$2^j$可以再分為兩個長度為$2^{j - 1}$的塊，原因是$2^j= 2^{j - 1} + 2^{j - 1}$也就是$2^j=2 * 2^{j - 1}$。那這兩個細分的塊分別會是$[i, i + 2^{j - 1} - 1]$和$[i + 2^{j - 1}, i + 2^j - 1]$，並對這兩個區間取最大值就會是答案了。
- 因此我們可以推出轉移式$dp[i][j] = max(dp[i - 1][j], dp[i - 1][j + 2^{i-1}])$
```cpp
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j + (1 << (i - 1))])
```
### $O(1)$查詢
- 當建完表之後我們就可以進行$O(1)$的查詢，首先我們的詢問為$[l, r]$，那我們可以算出$log_2(r - l + 1)$，也就是求出區間長度的$log$，這樣我們才能用倍增法推算要延伸$2$的多少次方。
- 我設取完$log$的值為$k$，我們可以利用$dp[k][l]$求出區間$[l, l + 2^k]$的最大值，和$dp[k][r - (1 << k) + 1]$求出區間$[r - 2 ^ k + 1, r]$的最大值
- 最後我們只要利用$max(dp[k][l], dp[k][r] - 2 ^ k + 1])$就可以求出該區間最大值
### 初始狀態
我在一開始寫的時候忘記給$dp$初始狀態，這邊要記的給$dp$初始狀態，也就是讓$dp[0][j]=T[j]$，我們用一個迴圈迭代所有的$n$，這裡的意思是由$j$當起點時區間長度為$2^0=1$的時候的最大值，也就是$T[j]$。
### zj d539 code
:::spoiler <span style="color:green;">AC (0. 4s, 39.4MB)</span>
```cpp=
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N = 5e5 + 5;
int n, m, arr[N], dp[35][N];
void sparse_table(int n){
for(int i = 1;i <= 31;i++){
for(int j = 0;(j + (1LL << (i - 1))) < n;j++){
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j + (1LL << (i - 1))]);
}
}
}
int query(int l, int r){
int idx = __lg(r - l + 1);
return max(dp[idx][l], dp[idx][r - (1LL << idx) + 1]);
}
int main(){
IOS
cin >> n;
for(int i = 0;i < n;i++) cin >> arr[i];
cin >> m;
for(int i = 0;i < n;i++) dp[0][i] = arr[i];
sparse_table(n);
while(m--){
int l, r;
cin >> l >> r;
if(l > r) swap(l, r);
l--, r--;
cout << query(l, r) << '\n';
}
return 0;
}
```
:::
---
我這一題也用過線段樹來寫過，速度上差不多，線段樹是$O(n)$建樹，$O(logn)$查詢，那我這題用線段樹的結果為<span style="color:green;">AC (0.5s, 8.4MB)</span>，但這題我比較喜歡sparse table，因為比較好寫。
:::spoiler 線段樹code
```cpp=
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define L(x) (x << 1)
#define R(x) ((x << 1) | 1)
using namespace std;
typedef long long ll;
int n, m;
ll seg[500005 << 2];
struct Node{
int left, right;
int tag;
int value;
};
ll pull(int x){
return seg[x] = max(seg[L(x)], seg[R(x)]);
}
void build(int x, int l, int r){
if(l == r){
cin >> seg[x];
return;
}
int mid = (l + r) >> 1;
build(L(x), l, mid);
build(R(x), mid + 1, r);
pull(x);
}
void update(int x, int l, int r, int pos, int val){
if(l == r){
seg[x] += val;
return;
}
int mid = (l + r) >> 1;
if(pos >= mid) update(L(x), l, mid, pos, val);
else update(R(x), mid + 1, r, pos, val);
pull(x);
}
ll query(int x, int l, int r, int ql, int qr){
if(ql <= l && qr >= r)
return seg[x];
ll ret = 0;
int mid = (l + r) >> 1;
if(qr <= mid) return query(L(x), l, mid, ql, qr);
else if(ql > mid) return query(R(x), mid + 1, r, ql, qr);
return max(query(L(x), l, mid, ql, mid), query(R(x), mid + 1, r, mid + 1, qr));
}
int main(){
IOS
cin >> n;
build(1, 1, n);
cin >> m;
while(m--){
int l, r;
cin >> l >> r;
if(l > r) swap(l, r);
cout << query(1, 1, n, l, r) << '\n';
}
return 0;
}
```
:::
---
這題我也有用分塊算法寫寫看，但是只拿60%，剩下的TLE了。
### <a href="https://codeforces.com/problemset/problem/1548/B">Codeforces Round #736 (Div. 1) pB. Integers Have Friends</a>
再來這一題會有點變化，我自己看了解答之後還是寫了很久才做出來。
- 題目說要找到一個$m(m >= 2)$使得$a_i\mod m = a_{i+1}\mod m = ... = a_j\mod m$，我們可以觀察到當$A[i...j]$是friend group時，建立一個`Difference Array`$D[i] = \lvert arr[i+1]-arr[i] \rvert$，而這會有$n-1$項，其中$D[i...j-1]$的每一個數都會是$m$的倍數
- 如果該子陣列是一個friend group，該題目可以藉由這樣轉換成一個GCD問題
```
D[i] = k1 * m
D[i+1] = k2 * m
...
D[j-1] = kn * m
```
- 其中$k_1、k_2、...、k_n$都是整數。
- 藉由上述可以看出各項都可以看成$m$的倍數，所以只要找出各項的最大公因數就會是要求的$m$
- 所以我們判斷friend group的條件就會是$GCD(D[(i.....j-1)]) > 1$，這樣我們就可以找到$arr$中的最大friend group大小。
:::spoiler <span style="color:green">Accepted</span> code
```cpp=
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
#define int long long
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int t, arr[N], dp[31][N];
int gcd(int a, int b){
if(b == 0) return a;
return gcd(b, a % b);
}
void sparse_table(int n){
for(int i = 1;i <= 31;i++){
for(int j = 0;(j + (1LL << (i - 1))) < n - 1;j++){
if(j + (1LL << i) - 1 < n - 1)
dp[i][j] = gcd(dp[i - 1][j], dp[i - 1][j + (1LL << (i - 1))]);
}
}
}
int query(int l, int r){
int idx = __lg(r - l + 1);
return gcd(dp[idx][l], dp[idx][r - (1LL << idx) + 1]);
}
signed main(){
IOS
cin >> t;
while(t--){
int n;
cin >> n;
for(int i = 0;i < n;i++) cin >> arr[i];
if(n == 1){
cout << 1 << '\n';
continue;
}
int ans = 1, left = 0, right = 1;
for(int i = 1;i < n;i++){
dp[0][i - 1] = abs(arr[i] - arr[i - 1]);
}
sparse_table(n);
for(int right = 0;right < n - 1;right++){
while(left < right && query(left, right) == 1) left++;
if(query(left, right) > 1) ans = max(ans, right - left + 2);
}
cout << ans << '\n';
}
return 0;
}
```
:::
---
這題也能用線段樹，但我就懶得寫了，我自己覺得這題的想法很難想到，真的很神奇，同時我也覺得能想到倍增法的人也好厲害，整個過程都非常漂亮，真的很驚豔，那這一篇sparse table就寫到這了，話說我還沒用過sparse table寫過區間和的問題，改天來寫寫看!
## Reference
- https://hackmd.io/@wiwiho/cp-note/%2F%40wiwiho%2FCPN-sparse-table
- https://cp-algorithms.com/data_structures/sparse-table.html
- https://codeforces.com/blog/entry/93586
Sign in with Wallet
Connect another wallet