ST表维护其他区间值

E1_de5truct0r · 2021-08-19 11:29:08 · 个人记录

ST表模板讲解：link

建议先看完上文再看本文。

进入正题。

1. 维护区间 GCD 问题

思路

首先，\gcd(a,a) = a，所以 \gcd 具有可重复贡献的性质。这意味着，区间的重叠并不会影响最后求出 \gcd 的值。所以 ST 表就可以派上用场了。

与基础的 ST 表一样，我们令 f_{(i,j)} 表示区间 [i,i+2^j-1] 的 \gcd。显然，f_{(i,0)} = i。状态转移方程也是相同：

f_{(i,j)}=\gcd(f_{(i,j-1)},f_{(i+2^{j-1}-1,j-1)})

只不过把 \max 改成了 \gcd。

如果您不会用辗转相除法求 \gcd 请把下面的代码记住：

template<typename T>
inline T gcd(T a,T b){return b?gcd(b,a%b):a;}

时间复杂度证明

在算法运行的时候，可能要经过 O(\log_2n) 次迭代。每一次迭代都会使用 GCD 函数进行递归，令值域为 w，GCD 函数的时间复杂度最高是 \Omega (\log_2w) 的，所以总时间复杂度看似有 O(n\log_2n\log_2w)。

但是，在 GCD 的过程中，每一次递归（除最后一次递归之外）都会使数列中的某个数至少减半，而数列中的数最多减半的次数为 \log_2(w^n) = O(n \log_2 w)，所以，GCD 的递归部分最多只会运行 O(n \log_2 w) 次。再加上循环部分（以及最后一层递归）的 O(n \log_2 n)，最终时间复杂度则是 O(n(\log_2x + \log_2w))。

而查询部分的时间复杂度很好分析，考虑最劣情况，即每次询问都询问最劣的一对数，时间复杂度为 O(log_2w)。因此，ST 表维护“区间 GCD”的时间复杂度为预处理 O(n(\log_2x + \log_2w))，单次查询 O(log_2w)。

而线段树则是预处理 O(n\log_2x)，单次查询 O(\log_2n+\log_2x)。

这不是严谨的证明，更严谨的证明请参考 OI-Wiki。

参考例题：https://www.luogu.com.cn/problem/U174986

2.其他问题

只要是有“可重复贡献性的”就可以用ST 表维护，时间复杂度为 O(n\log_2s)+O(s)。其中，s 为处理数值的时间复杂度（如最大值 O(1)，\gcd 用 O(\log_2w+\log_2x) 等。）