ST 表¶
引入¶
什么是 ST 表?
ST 表是一种基于倍增思想、用来解决可重复贡献问题的数据结构。那么什么是可重复贡献问题呢?
假设现在有一个运算
接下来,好渴鹅将会以静态区间最值查询为例子(简称 RMQ,Range Maximum/Minimum Query)来讲述 ST 表的实现。
算法思想¶
基于 dp 和倍增。
我们可以将区间拆分成
然后对于询问,大家可能一下就可以想到将序列长度进行二进制拆解,然后调用之前的 dp 数组,在所有小块中取出最大值。这样做是
事实上,我们取最大值的数组是可以重叠的。我们就直接找到小于序列长度的最大的
时间复杂度:预处理 + dp
代码¶
代码 - ST 表
void pre() {
log[1] = 0, log[2] = 1;
for (int i = 3; i <= kMaxN; i++) {
log[i] = log[i >> 1] + 1;
}
for (int j = 1; j <= kLog; 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]);
}
}
}
int query(int l, int r) {
int s = log[r - l + 1];
return max(f[l][s], f[r - (1 << s) + 1][s]);
}
补充¶
其他求区间最值的方法还有线段树和树状数组,单词询问时间复杂度为