ST 表

概念：ST 表预处理长度为 2 的幂的区间最值。对幂等运算（最小值、最大值、gcd），任意区间可由两个允许重叠的块在 O(1) 合并。

关键步骤

st[i][j] 表示从 i 开始、长度 2^j 的最小值。查询 [l,r] 时令 k=floor(log2(r-l+1))，合并两个长度 2^k 的覆盖块。

for(int j=1;(1<<j)<=n;j++)
  for(int i=1;i+(1<<j)-1<=n;i++)
    st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
int queryMin(int l,int r){
    int k=__lg(r-l+1);
    return min(st[l][k],st[r-(1<<k)+1][k]);
}

复杂度

预处理 O(n log n)，每次最值查询 O(1)，空间 O(n log n)。ST 表不适合在线修改；普通区间和不能用重叠块直接相加。