ST表

ST表,又称稀疏表,通过采取预处理的方案储存不同长度的区间答案,从而在查询时候非常高效

ST表一般用于解决区间最值,可重复贡献的问题

使用ST表需要注意以下问题:

• 静态区间查询
• 运算必须满足 结合律 和 幂等律
• 常见匀速有:
  • 区间最大最小值
  • 区间GCD
  • 区间按位与,按位或

基本思路

ST表的基本思路是 倍增法

假设我们有一个长度为$n$的数组a[0…n-1],我们预处理一个二维数组 st[i][j]
st[i][j]表示从 $i$ 开始,长度为 $2^j$ 的区间答案

预处理

• 初始化 st[i][0] = a[i]
• 状态转移:
  $st[i][j]=f(s[i][j-1],st[i+2^{j-1}][j-1])$
  即将长度为 $2^j$的区间拆成两个长度$2^{j-1}$的区间

查询

• 对于区间[L,R]:
  • 令 k = floor(log_2(R-L+1))
  • 有 ans = f(st[L][k],st[R-(1 << k)+1][k]
  • 对于log我们可以预处理log表
• 下图展示了ST表倍增的过程