ST表
ST表,又称稀疏表,通过采取预处理的方案储存不同长度的区间答案,从而在查询时候非常高效
ST表一般用于解决区间最值,可重复贡献的问题
使用ST表需要注意以下问题:
- 静态区间查询
- 运算必须满足 结合律 和 幂等律
- 常见问题有:
- 区间最大最小值
- 区间GCD
- 区间按位与,按位或
这里给一份参考代码
struct ST
{
int maxn;
vector<i64> logtab;
vector<vector<i64>> st;
ST(int maxk)
{
maxn = maxk;
}
void pre(const vector<i64> &a)
{
// 预处理log表
logtab.resize(maxn + 1);
int K = __lg(maxn) + 1;
st = vector<vector<i64>>(maxn, vector<i64>(K));
logtab[1] = 0;
for (i64 i = 2; i <= maxn; i++) {
logtab[i] = logtab[i / 2] + 1;
}
// 预处理st表
// 初始化
for (i64 i = 0; i < maxn; i++) {
st[i][0] = a[i];
}
// pre
for (i64 j = 1; (1 << j) <= maxn; j++) {
for (i64 i = 0; i + (1 << j) <= maxn; i++) {
st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
}
}
i64 get(int l, int r)
{
i64 k = logtab[r - l + 1];
return max(st[l][k], st[r - (1 << k) + 1][k]);
}
};cpp