【提高课】ST表解决区间最值问题【2】

【提高课】ST表解决区间最值问题
这是之前写的，现在重新整理了模板，可以返回最小值的下标。

ST 表求区间最小值：

struct st_pair{
    
    int w, idx;
    bool operator < (const st_pair & x) const{
    
        return w < x.w;
    }
};

st_pair f[N][LG];

void init(){
    
    rep(j, 0, LG - 1){
    
        for(int i = 1; i + (1 << j) - 1 <= n; i ++ ){
    
            if(!j) f[i][j] = {
    a[i], i};
            else f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
        }
    }
}

st_pair query(int l, int r){
    
    int k = __lg(r - l + 1);
    return min(f[l][k], f[r - (1 << k) + 1][k]);
}