ST 表

relax 自定义需要求的区间可重复贡献信息。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
namespace SpareTable
{
    constexpr int bMAX=20;
    int N,a[MAX],f[MAX][bMAX];
    inline int relax(int x,int y) {}
    inline void build()
    {
        for(int i=1;i<=N;++i) f[i][0]=a[i];
        for(int i=1;i<=__lg(N);++i) for(int j=1;j+(1<<i)-1<=N;++j) f[j][i]=relax(f[j][i-1],f[j+(1<<i>>1)][i-1]);
    }
    inline int query(int l,int r)
    {
        int t=__lg(r-l+1);
        return relax(f[l][t],f[r-(1<<t)+1][t]);
    }
}