資料結構 ST表 詳解

😊 | Powered By HeartFireY | Sparse-table

📕 | 需要的前導知識：倍增

一、什麼是ST表

1.可重複貢獻問題

可重複貢獻問題是對于運算，運算的性質滿足，則對應的區間詢問就是一個可重複的貢獻問題，例如：最大值滿足，最大公因數滿足，是以RMQ問題和GCD問題就是一個可重複貢獻的問題，但是例如區間和就不滿足這個性質，因為在求解區間和的過程中采用的預處理區間會發生重疊，導緻重疊部分被重複計算，是以對于操作還需要滿足集合率才能夠使用ST表進行求解。

2.ST表簡介

ST表是一種基于倍增思想，用于解決可重複貢獻問題的資料結構。

ST表應用最廣泛的領域便是解決RMQ問題：給定個數，個詢問，對于每個詢問，需要回答區間中的最大值或最小值(可以采用兩個數組同時進行處理)。

基于倍增的思想，ST表可以實作下進行預處理，并在時間内回答每個詢問。如果僅僅進行區間最值查詢，ST表的效率完全吊打線段樹；但是，相比于線段樹，ST表并不支援修改操作，無論是單點修改還是區間修改都不支援。

二、ST表的原理和實作

我們在簡介中提到，ST表基于倍增的思想，但并不是樸素的倍增方式：對于樸素的倍增方式，我們可以發現查詢的過程中，我們仍然需要調步，那麼查詢的複雜度顯然不是，也不存在比線段樹更有的說法，反倒預處理不如線段樹快。

❓::那麼倍增的思想是如何應用的呢？

我們在簡介前提到了重複貢獻問題，顯然對于區間的最小值/最大值都滿足這個性質：。那麼顯然用來求解的預處理的區間有重疊部分，隻要這些區間的并是所求區間，最終計算出的答案一定就是正确答案。

❓::具體是如何實作的?

我們定義表示區間的最大值，那麼顯然。

那麼我們可以根據倍增的思路給出狀态轉移方程：

而對于詢問，我們将其分成兩部分和，即為兩個子區間。由于RMQ屬于可重複貢獻問題，是以不必使兩個區間不相交。

但顯然，我們需要使第一個字區間的右端點盡可能的接近​，那麼不妨直接令，那麼可以得到；同時，我們希望第二個區間的左端點盡可能地接近​，也就是，發現于上一個式子使完全相同的，是以隻需要取即可。但顯然這樣的​不是整數​，那麼我們直接取向下取整即可，此時的仍能保證兩個子區間完全覆寫整個區間。

由于使用STL反複計算值容易卡，對于我們隻需預處理出可能用到的全部​​值即可：

ST表的其他應用

除 RMQ 以外，還有其它的“可重複貢獻問題”。例如“區間按位和”、“區間按位或”、“區間 GCD”，ST 表都能高效地解決。

三、ST表RMQ模闆

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

#define N 2000010

int stmax[N][22], stmin[N][22], mn[N]，a[N];

int q, n;

void init(){
    mn[0] = -1;
    for (int i = 1; i <= n; i++){
        mn[i] = ((i & (i - 1)) == 0) ? mn[i - 1] + 1 : mn[i - 1];
        stmax[i][0] = stmin[i][0] = a[i];
    }
    for (int j = 1; j <= mn[n]; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++){
            stmax[i][j] = max(stmax[i][j - 1], stmax[i + (1 << (j - 1))][j - 1]);
            stmin[i][j] = min(stmin[i][j - 1], stmin[i + (1 << (j - 1))][j - 1]);
        }
}

inline int rmq_max(int L, int R){
    int k = mn[R - L + 1];
    return max(stmax[L][k], stmax[R - (1 << k) + 1][k]);
}

inline int rmq_min(int L, int R){
    int k = mn[R - L + 1];
    return min(stmin[L][k], stmin[R - (1 << k) + 1][k]);
}

signed main(){
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    init();
    while(q--){
        int l, r; cin >> l >> r;
        cout << rmq_max(l, r) << rmq_min(l, r) << endl;
    }
    return 0;
}