Code: Static Range Minimum Queries

#include <bits/stdc++.h>

using namespace std;

const int lg = 21;
const int inf = 1e9;

class BinaryLifting {
  public:
    int n;
    vector<int> a;
    vector<vector<int>> jump;
    vector<vector<int>> dp;
    BinaryLifting(int n) {
        this->n = n;
        a.resize(n);
        jump.resize(n, vector<int>(lg, -1));
        dp.resize(n, vector<int>(lg, inf));
    }

    void prepare_lifts() {
        // jump[i][j] is the node that you would reach if you take 2^j
        // steps starting from node i.
        for (int i = 0; i < n - 1; i++) {
            jump[i][0] = i + 1;
            dp[i][0] = min(a[i], a[i + 1]);
        }

        // Caution : Loop Order.
        // You should iterate powers of 2 first.
        for (int j = 1; j < lg; j++) {
            for (int i = 0; i < n; i++) {
                // Make the first half of the jump.
                int mid = jump[i][j - 1];
                if (mid == -1) {
                    continue;
                }
                // Make the second half of the jump.
                jump[i][j] = jump[mid][j - 1];
                dp[i][j] = min(dp[i][j - 1], dp[mid][j - 1]);
            }
        }
    }

    vector<int> split(int num) {
        vector<int> res;
        for (int i = 0; i < lg; i++) {
            if ((1 << i) & num) {
                res.push_back(i);
            }
        }
        return res;
    }

    int walk(int src, int steps) {
        vector<int> powers_of_2 = split(steps);

        int now = src;
        int res = a[src];
        for (int p : powers_of_2) {
            res = min(res, dp[now][p]);
            now = jump[now][p];
            if (now == -1) {
                break;
            }
        }

        return res;
    }

    int get_min(int l, int r) { return walk(l, r - l); }
};

void solve() {
    int n, q;
    cin >> n >> q;

    BinaryLifting blift(n);
    for (int i = 0; i < n; i++) {
        cin >> blift.a[i];
    }
    blift.prepare_lifts();

    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        cout << blift.get_min(l, r) << "\n";
    }
}

int main(int argc, char **argv) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    solve();
}