ST表

实现的功能：固定数组询问区间最值RMQ/区间GCD

原数组v下标从0开始；ST表下标从1开始，首元素为0

洛谷模板题：Luogu P3865

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define endl '\n'

// ST表
// 实现的功能：固定数组 区间最值询问RMQ/区间GCD
// 下标从0开始

template <typename T>
struct SparseTable
{
    int n;
    vector<T> a; // 原数组
    vector<vector<T>> st; // st[i][j]表示[i,i+2^j-1]的最值
    T op(const T &a, const T &b) { return max(a, b); } // 可选：max,min,__gcd
    SparseTable(vector<T> _v){
        a = _v;
        n = a.size();
        st.resize(n+5);
        int len = log2(n)+1;
        for (int i=0; i<n; i++) st[i].resize(21, 0); // n<=2e6开21
        solve();
    }
    void solve(){
        for (int i = 0; i < n; i++) st[i][0] = a[i];
        for (int j = 1; (1 << j) <= n; j++){
            int len = (1 << j);
            for (int i = 0; i + len - 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 j = log2(r - l + 1);//已向下取整
        return op(st[l][j], st[r - (1 << j) + 1][j]);
    }
};

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n, q;
    cin >> n >> q;
    vector<int> v(n);
    for (auto &i : v) cin >> i;
    SparseTable<int> st(v);
    while (q--){
        int l, r;
        cin >> l >> r;
        cout << st.query(l-1, r-1) << endl;
    }
    return 0;
}