Sparse table

sparseTable.cpp

// https://cses.fi/problemset/task/1647

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

class SparseTable {
   private:
    vector<vector<ll>> ST;
    vector<ll> a;

   public:
    SparseTable(vector<ll>& v) {
        a = v;
        ST = vector<vector<ll>>(log2(a.size()) + 1, vector<ll>(a.size()));

        for (ll i = 0; i < a.size(); i++) {
            ST[0][i] = i;
        }

        for (ll k = 1; k < ST.size(); k++) {
            for (ll i = 0; i + (1 << k) <= a.size(); i++) {
                ll x = ST[k - 1][i];
                ll y = ST[k - 1][i + (1 << (k - 1))];

                ST[k][i] = (a[x] <= a[y]) ? x : y;
            }
        }
    }

    ll query(ll l, ll r) {
        if (l == r) {
            return a[l];
        }

        ll k = log2(r - l);
        ll x = ST[k][l], y = ST[k][r - (1 << k) + 1];

        return min(a[x], a[y]);
    }
};

int main() {
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    
    ll n, q;
    cin >> n >> q;
    
    vector<ll> a(n);

    for(ll& i : a) {
        cin >> i;
    }

    SparseTable t(a);

    while (q--) {
        ll l, r;
        cin >> l >> r;

        cout << t.query(l - 1, r - 1) << '\n';
    }
}