【模板】ST表

xxxasybt2023 · 2025-10-08 15:33:21 · 算法·理论

template <typename T>
struct RMQ
{
    static const int N = 1e6+5,M = 21;
    T rmq[N][M]; int lg[N];
    inline T cmp(const T&a,const T&b) {return max(a,b);}
    void init(int n,T *a)
    {
        lg[0] = -1;
        for (int i = 1;i <= n;i ++) lg[i] = lg[i/2]+1,rmq[i][0] = a[i];
        for (int j = 1;j <= lg[n];j ++)
            for (int i = 1;i+(1<<j)-1 <= n;i ++)
                rmq[i][j] = cmp(rmq[i][j-1],rmq[i+(1<<j-1)][j-1]);
    }
    inline T query(int l,int r) {return cmp(rmq[l][lg[r-l+1]],rmq[r-(1<<lg[r-l+1])+1][lg[r-l+1]]);}
};