# sparse table稀疏表

* 建立一個二維陣列，sp[N][$\lfloor log_2N\rfloor$]，N為數字長度，$\lfloor log_2N\rfloor$為2最接近N的整數對數
* sp[i][j]為位置i到i+$2^j$的最小值 {0<=j<=$\lfloor log_2N\rfloor$}
* **建立**：（最小值為例）
1. sp[i][j]=min(sp[i][j-1], sp[i+$2^{j-1}$][j-1]) -- ex:i到$2^3$為min( i到i+4的min, i+4到(i+4)+4的min )
2. 複雜度$O(n\log n)$
* **取值**：
1. 取[l, r], **LEN=l-r+1**, **j=$\lfloor log_2LEN\rfloor$**
2. 輸出即為 min(sp[l][j], sp[r-$2^j$+1][j])
3. 其原理為，即便取到重複的範圍，如[2,2+4]和[7-4, 7]，也不會影響極值的數值，因此可達到O(1)的速度
:::info
不能做修改，因為一個值會被很多範圍覆蓋
:::
> $2^j$ c++ code: ```1<<j```
> log則預先生成

程式碼：

#include <bits/stdc++.h>
using namespace std;

int num[500001], sp[500001][20], log_2[500001];

int query(int l, int r){
    int k=log_2[r-l+1];
    return min(sp[l][k], sp[r-(1<<k)+1][k]);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n
    cin >> n;

    // generates logarithm table of 2 (only needs n value)
    log_2[1]=0;
    for(int i=2;i<=n;++i) log_2[i]=log_2[i/2]+1;

    //build
    for(int i=0;i<n;++i){ //init
        cin >> num[i];
        sp[i][0]=num[i];
    }
    for(int j=1;j<=log_2[n];++j)
        for(int i=0;i+(1<<j)-1<n;++i)
            sp[i][j]=max(sp[i][j-1], sp[i+(1<<(j-1))][j-1]);
}