st表学习

Wild_Of_The_World · 2024-12-29 17:16:08 · 个人记录

P2880 [USACO07JAN] Balanced Lineup G

P1890 gcd区间

P3865 【模板】ST 表 && RMQ 问题

以上三题总结

对于st表需要注意的是各个位置的边界，+1-1

st表预处理标程：

lg[1]=0;
for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
for(int j=1;j<=lg[n];j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);

f[i][j]->[i,i+(1<<j)-1]

故预处理第二个for终点为i+(1<<j)-1<=n

注意第二段起点为i+(1<<(j-1))

查询：

int k=lg[r-l+1];
  max(f[l][k],f[r-(1<<k)+1][k])

r-l+1为区间长度

第二段起点x

x+(1<<k)-1=r -> x=r-(1<<k)+1