#include <bits/stdc++.h>
using namespace std;

#define MAXN 5005
int st[MAXN][30]; //st[i][j] 代表区间[i, i+2^j)最小值

void ST(const vector<int>& a) {
    int n = a.size();
    for (int i=0; i<n; i++) st[i][0] = a[i];
    for (int j=1; (1<<j)<=n; j++) {//区间大小 
        for (int i=0; i+(1<<j)-1<n; i++) {//区间下限 
            st[i][j] = min(st[i][j-1], st[i+(1<<(j-1))][j-1]);
        }
    }
}

int ask(int l, int r) {
		int k = 0;
		while ((1<<(k+1))<=r-l+1) k++;
		return min(st[l][k], st[r-(1<<k)+1][k]);
}

int main() {
    vector<int> a = {1,2,3,4,2,1};
    ST(a);
    cout << ask(0,2) << endl;
    cout << ask(2,3) << endl;
    cout << ask(2,4) << endl;
    cout << ask(2,5) << endl;
}
/*
1
3
2
1
*/

封装

template<class T, class Compare=std::less<T>>
struct ST {
    Compare cmp;
    vector<vector<T>> st;  // st[i][j] 代表区间[i, i+2^j)最小值
    ST(const vector<T>& a, Compare cmp = Compare()) : st(a.size(), vector<T>(30)), cmp(cmp) {
        int sz = a.size();
        for (int i = 0; i < sz; i++)
            st[i][0] = a[i];
        for (int j = 1; (1 << j) <= sz; j++) {             // 区间大小
            for (int i = 0; i + (1 << j) - 1 < sz; i++) {  // 区间下限
                T x = st[i][j - 1], y = st[i + (1 << (j - 1))][j - 1];
                st[i][j] = min(x, y, cmp);
            }
        }
    }
    T ask(int l, int r) {
        int k = 0;
        while ((1 << (k + 1)) <= r - l + 1)
            k++;
        T x = st[l][k], y = st[r - (1 << k) + 1][k];
        return min(x, y, cmp);
    }
};