Sparse Table(稀疏表)

Sparse Table是一種資料結構，在

$O(nlogn)$的時間複雜度做預處理，並可以進行

$O(1)$的查詢，Sparse Table常被用在RMQ的題目，可以視題目需求更改

$min()$、

$max()$、

$gcd()$、

$sum()$。其中預處理的方式會使用到倍增法(Binary Lifting)，由於建表需要花

$O(nlogn)$，所以如果要使用Sparse Table必須在不帶修改的題目才比較合適。

找區間MAX(zerojudge d539)

給一個數列

$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\ast 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}])$

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j + (1 << (i - 1))])

$O(1)$查詢

• 當建完表之後我們就可以進行
  $O(1)$的查詢，首先我們的詢問為
  $[l,r]$，那我們可以算出
  $lo{g}_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

AC (0. 4s, 39.4MB)

#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)$查詢，那我這題用線段樹的結果為AC (0.5s, 8.4MB)，但這題我比較喜歡sparse table，因為比較好寫。

線段樹code

#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了。

Codeforces Round #736 (Div. 1) pB. Integers Have Friends

再來這一題會有點變化，我自己看了解答之後還是寫了很久才做出來。

• 題目說要找到一個
  $m(m>=2)$使得
  $a_i\mathrm{mod}m=a_{i+1}\mathrm{mod}m=...=a_j\mathrm{mod}m$，我們可以觀察到當
  $A[i...j]$是friend group時，建立一個Difference Array
  $D[i]=|arr[i+1]-arr[i]|$，而這會有
  $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大小。

Accepted code

#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