5.倍增

发表于 分类于 ， 本文字数： 698

倍增

倍增, 从字面的上意思看就是成倍的增长 ,这是指我们在进行递推时,如果状态空间很大,通常的线性递推无法满足时间和空间复杂度的要求 ,那么我们就可以通过成倍的增长,只递推状态空间中在 2 的整数次幂位置上的值作为代表 。当需要其他位置上的值时,我们只需要通过” 任意整数可以表示成若干个2的次幂项的和 “ 这一性质(13=2^3^+2^2^+2^0^), 使用之前求出的代表值拼成所需的值。

ST算法

ST表（Sparse Table，稀疏表）是一种简单的数据结构，主要用来解决RMQ（Range Maximum/Minimum Query，区间最大/最小值查询）问题。它主要应用倍增的思想，可以实现 O(nlog⁡n) 预处理、 O(1) 查询。

1688108641061

为了减少时间复杂度，可以用动态规划的方法进行预处理： 

1
2
3
4
5
6
int f[MAXN][21]; // 第二维的大小根据数据范围决定，不小于log(MAXN)
for (int i = 1; i <= n; ++i)
    f[i][0] = read(); // 读入数据
for (int i = 1; i <= 20; ++i)
    for (int j = 1; j + (1 << i) - 1 <= n; ++j)
        f[j][i] = max(f[j][i - 1], f[j + (1 << (i - 1))][i - 1]);

img

求LCA最近公共祖先

LCA（Least Common Ancestors），即最近公共祖先，是指在有根树中，找出某两个结点u和v最近的公共祖先。

先dfs预处理好深度，把父节点和 2^i^级的祖先存到数组里，init一个lg数组优化，然后开始从大到小利用倍增往上爬，爬到父节点的子节点，输出父节点。

------ 本文结束感谢您的阅读 ------
请我一杯咖啡吧！
itingyu 微信打赏 微信打赏