# 稀疏表 Sparse Table
- 利用 `O(nlogn)` 預處理，`O(1)` 查詢區間 `[l, r]` 最大值
- 每一格 `ST[i][j]` 存區間 `[i, i+2^j−1]` 的最大值

    // Sparse Table : O(nlogn) 預處理，O(1) 查詢 [l, r] 最大值
    class SparseTable{
    public:
        int n, num[1000];    // input data
        int ST[1000][10];    // [i, i+2^j−1]
        void preprocess(){
            for(int i = 0; i < n; i++)
                ST[i][0] = num[i];
            for(int j = 1; (1<<j) <= n; j++)
                for(int i = 0; i+(1<<j)-1 < n; i++)    // 超出範圍的，不會用到
                    ST[i][j] = max(ST[i][j-1], ST[i + (1<<(j-1))][j-1]);
        }
        int query(int l, int r){
            int k = (int)log2(r-l+1);
            return max(ST[l][k], ST[r-(1<<k)+1][k]);
        }
    };

# 前綴和 Prefix Sum
- 利用 `O(n)` 預處理，`O(1)` 查詢區間 `[l, r]` 總和
- 每一格 `prefix[i]` 存區間 `[0, i]` 的總和

    int n, num[1000];    // input data
    int prefix[1000];    // [0, i]

    void preprocess(){
        prefix[0] = num[0];
        for(int i = 1; i < n; i++)
            prefix[i] = prefix[i-1] + num[i];
    }
    int query(int l, int r){
        if(l==0)    return prefix[r];
        else        return prefix[r]-prefix[l-1];
    }