\(n\)表示數(shù)組長度，\(lg[i]\)表示\(log_2i\)，\(st[i][j]\)表示區(qū)間\([i, i+2^j-1]\)的詢問值。

構(gòu)造函數(shù)中預處理出\(lg\)和\(st\)，時間復雜度：\(O(nlogn)\)。

\(query(l,r)\)表示求區(qū)間\([l,r]\)的詢問值，時間復雜度：\(O(logn)\)。

支持高效區(qū)間查詢，不支持區(qū)間修改。

template <typename T>
class SparseTable 
{
public:
    using func_type = function<T(const T &, const T &)>;
    int n;
    vector<vector<T>> st;
    vector<int> lg;
    static T default_func(const T &a, const T &b) {return max(a, b);}
    func_type op;
    SparseTable(const vector<T> &v, func_type _func = default_func) 
    {
        n = v.size() - 1, op = _func;
        lg.assign(n + 1, 0);
        st.assign(n + 1, vector<T>(20));
        for (int i = 0; 1 << i <= n; i++) lg[1 << i] = i;
        for (int i = 1; i <= n; i++) 
        {
            if (!lg[i]) lg[i] = lg[i - 1];
            st[i][0] = v[i];
        }
        for (int j = 1; 1 << j <= n; j++)
            for (int i = 1; i + (1 << j) - 1 <= n; i++)
                st[i][j] = op(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
    }

    T query(int l, int r) 
    {
        int k = lg[r - l + 1];
        return op(st[l][k], st[r - (1 << k) + 1][k]);
    }
};

應(yīng)用

多次求區(qū)間詢問值（需滿足可重復貢獻和結(jié)合律，如最值，按位與值，按位或值，\(gcd\)值，代碼中默認為最大值）。

例題

Set To Max

總結(jié)

以上是生活随笔為你收集整理的ST表的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。