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

template <typename T, class F = std::function<T(const T&, const T&)>>
struct SparseTable {
    std::vector<std::vector<T>> st;
    F merge;
    std::vector<int32_t> log_table;
    
    SparseTable(const std::vector<T>& arr, F merge) : merge(merge) {
        auto n = arr.size();
        if (n == 0) return;
        
        log_table.resize(n + 1);
        log_table[0] = log_table[1] = 0;
        for (auto i = 2; i <= n; i++) {
            log_table[i] = log_table[i / 2] + 1;
        }
        
        auto k = log_table[n] + 1;
        st.resize(n, std::vector<T>(k));
        for (auto i = 0; i < n; i++) {
            st[i][0] = arr[i];
        }
        
        for (auto j = 1; j < k; j++) {
            for (auto i = 0; i + (1 << j) <= n; i++) {
                st[i][j] = merge(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
            }
        }
    }
    
    T query(auto l, auto r) {
        assert(0 <= l and l < r and r <= st.size());
        auto k = log_table[r - l];
        return merge(st[l][k], st[r - (1 << k)][k]);
    }
};