Sparse Table

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Generic Sparse Table for an idempotent, associative operation
5
// Here we will use it for RMQ (min), but it works for max, gcd, AND, OR as well.
6
7
template <class T, class F>
8
struct SparseTable {
9
    int n, K;                 // array size and maximum power of two
10
    vector<int> lg;           // floor(log2) table for 1..n
11
    vector<vector<T>> st;     // st[i][j] stores f over [i, i + 2^j - 1]
12
    F op;                     // combining function (e.g., min)
13
14
    SparseTable() {}
15
16
    SparseTable(const vector<T>& a, F comb) { build(a, comb); }
17
18
    void build(const vector<T>& a, F comb) {
19
        op = comb;
20
        n = (int)a.size();
21
        K = 0;
22
        while ((1 << K) <= n) K++;
23
        lg.assign(n + 1, 0);
24
        for (int i = 2; i <= n; ++i) lg[i] = lg[i / 2] + 1;
25
        st.assign(K, vector<T>(n));
26
        // level 0 is the array itself
27
        for (int i = 0; i < n; ++i) st[0][i] = a[i];
28
        // build higher levels
29
        for (int j = 1; j < K; ++j) {
30
            int len = 1 << j;
31
            int half = len >> 1;
32
            for (int i = 0; i + len - 1 < n; ++i) {
33
                st[j][i] = op(st[j - 1][i], st[j - 1][i + half]);
34
            }
35
        }
36
    }
37
38
    // Query on inclusive range [L, R]
39
    T query(int L, int R) const {
40
        if (L > R) swap(L, R);
41
        int k = lg[R - L + 1];
42
        // Combine two overlapping blocks of size 2^k
43
        return op(st[k][L], st[k][R - (1 << k) + 1]);
44
    }
45
};
46
47
int main() {
48
    ios::sync_with_stdio(false);
49
    cin.tie(nullptr);
50
51
    // Example array
52
    vector<int> A = {5, 2, 7, 3, 6, 1, 4, 9};
53
54
    // Build Sparse Table for minimum
55
    auto mn = [](int a, int b) { return min(a, b); };
56
    SparseTable<int, decltype(mn)> st(A, mn);
57
58
    // Sample queries
59
    vector<pair<int,int>> queries = {{0, 3}, {2, 5}, {0, 7}, {5, 5}};
60
    for (auto [L, R] : queries) {
61
        cout << "min(" << L << ", " << R << ") = " << st.query(L, R) << "\n";
62
    }
63
64
    return 0;
65
}
66

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Sparse Table for GCD. gcd is associative and idempotent.
5
6
struct GCDOp {
7
    int operator()(int a, int b) const { return std::gcd(a, b); }
8
};
9
10
struct GCDSparseTable {
11
    int n, K;
12
    vector<int> lg;
13
    vector<vector<int>> st;
14
15
    GCDSparseTable() {}
16
    GCDSparseTable(const vector<int>& a) { build(a); }
17
18
    void build(const vector<int>& a) {
19
        n = (int)a.size();
20
        K = 0; while ((1 << K) <= n) K++;
21
        lg.assign(n + 1, 0);
22
        for (int i = 2; i <= n; ++i) lg[i] = lg[i / 2] + 1;
23
        st.assign(K, vector<int>(n));
24
        for (int i = 0; i < n; ++i) st[0][i] = a[i];
25
        for (int j = 1; j < K; ++j) {
26
            int half = 1 << (j - 1);
27
            for (int i = 0; i + (1 << j) - 1 < n; ++i) {
28
                st[j][i] = std::gcd(st[j - 1][i], st[j - 1][i + half]);
29
            }
30
        }
31
    }
32
33
    int query(int L, int R) const {
34
        if (L > R) swap(L, R);
35
        int k = lg[R - L + 1];
36
        return std::gcd(st[k][L], st[k][R - (1 << k) + 1]);
37
    }
38
};
39
40
int main() {
41
    ios::sync_with_stdio(false);
42
    cin.tie(nullptr);
43
44
    vector<int> A = {24, 18, 30, 12, 6, 9, 3, 15};
45
    GCDSparseTable st(A);
46
47
    vector<pair<int,int>> queries = {{0, 1}, {1, 4}, {0, 7}, {3, 6}};
48
    for (auto [L, R] : queries) {
49
        cout << "gcd(" << L << ", " << R << ") = " << st.query(L, R) << "\n";
50
    }
51
    return 0;
52
}
53

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Sparse Table that stores pairs (depth, node) and returns the pair with smaller depth.
5
struct MinDepthOp {
6
    pair<int,int> operator()(const pair<int,int>& a, const pair<int,int>& b) const {
7
        if (a.first != b.first) return a.first < b.first ? a : b;
8
        // Tie-break by node id for determinism (optional)
9
        return a.second < b.second ? a : b;
10
    }
11
};
12
13
struct SparseTable {
14
    int n, K;
15
    vector<int> lg;
16
    vector<vector<pair<int,int>>> st; // (depth, node)
17
    MinDepthOp op;
18
19
    SparseTable() {}
20
21
    void build(const vector<pair<int,int>>& a) {
22
        n = (int)a.size();
23
        K = 0; while ((1 << K) <= n) K++;
24
        lg.assign(n + 1, 0);
25
        for (int i = 2; i <= n; ++i) lg[i] = lg[i / 2] + 1;
26
        st.assign(K, vector<pair<int,int>>(n));
27
        for (int i = 0; i < n; ++i) st[0][i] = a[i];
28
        for (int j = 1; j < K; ++j) {
29
            int half = 1 << (j - 1);
30
            for (int i = 0; i + (1 << j) - 1 < n; ++i) {
31
                st[j][i] = op(st[j - 1][i], st[j - 1][i + half]);
32
            }
33
        }
34
    }
35
36
    // Inclusive range [L, R]
37
    pair<int,int> query(int L, int R) const {
38
        if (L > R) swap(L, R);
39
        int k = lg[R - L + 1];
40
        return op(st[k][L], st[k][R - (1 << k) + 1]);
41
    }
42
};
43
44
struct LCA {
45
    int n;
46
    vector<vector<int>> g;
47
    vector<int> depth;
48
    vector<int> first;                 // first occurrence of each node in euler
49
    vector<pair<int,int>> euler;       // (depth, node)
50
    SparseTable st;                    // RMQ over euler by depth
51
52
    LCA(int n) : n(n), g(n), depth(n, 0), first(n, -1) {}
53
54
    void add_edge(int u, int v) {
55
        g[u].push_back(v);
56
        g[v].push_back(u);
57
    }
58
59
    void dfs(int u, int p, int d) {
60
        depth[u] = d;
61
        first[u] = (int)euler.size();
62
        euler.push_back({d, u});
63
        for (int v : g[u]) if (v != p) {
64
            dfs(v, u, d + 1);
65
            // Upon returning, record (depth,parent) again (Euler tour property)
66
            euler.push_back({d, u});
67
        }
68
    }
69
70
    void build(int root = 0) {
71
        euler.clear();
72
        dfs(root, -1, 0);
73
        st.build(euler);
74
    }
75
76
    int lca(int u, int v) const {
77
        int L = first[u];
78
        int R = first[v];
79
        return st.query(L, R).second; // node id from pair(depth,node)
80
    }
81
};
82
83
int main() {
84
    ios::sync_with_stdio(false);
85
    cin.tie(nullptr);
86
87
    // Build a sample tree
88
    int n = 9;
89
    LCA solver(n);
90
    // edges (undirected)
91
    solver.add_edge(0, 1);
92
    solver.add_edge(0, 2);
93
    solver.add_edge(1, 3);
94
    solver.add_edge(1, 4);
95
    solver.add_edge(2, 5);
96
    solver.add_edge(2, 6);
97
    solver.add_edge(4, 7);
98
    solver.add_edge(4, 8);
99
100
    solver.build(0); // root at 0
101
102
    vector<pair<int,int>> queries = {{3, 7}, {7, 8}, {5, 6}, {3, 5}, {3, 4}};
103
    for (auto [u, v] : queries) {
104
        cout << "LCA(" << u << ", " << v << ") = " << solver.lca(u, v) << "\n";
105
    }
106
    return 0;
107
}
108