倍增法 / RMQ 问题的 ST 表解法 / 基于树上倍增的 LCA 问题

什么是倍增？

倍增，从字面及数学的角度就是 ”成倍增长“ 的意思。这能使线性问题转化为数级处理，优化时间复杂度。

不是人话是不是？听不懂是不是？ 看这里。这是指我们在进行递推时，如果状态空间很大，通常的线性递推无法满足时间与空间复杂度的要求，那么我们可以通过成倍增长的方式，只递推状态空间中在 2 的整数次幂位置上的值作为代表。

因为基本定理：任意整数可以表示成若干个2的次幂项的和 这一性质，使用之前求出的代表值拼成所需的值。

”倍增“ 与 ”二进制划分“ 两个思想相互结合，降低了求解很多问题的时间与空间复杂度。快速幂其实就是 “倍增” 与 ”二进制划分“ 思想的一种体现 （不然你以为 O(n \log n) 的时间复杂度是吹出来的？）。

倍增的主要应用为：快速幂，RMQ 问题，ST 算法，LCA 等。

RMQ 问题 / ST 算法

关于 100 多行的线段树不香吗 \dots 你说的对，但我太蒟蒻了，不会。

著名的 ST 表大法能在 O(n \log n) 的时间复杂度预处理后以 O(1) 的时间复杂度查询对于一个序列，任意一对区间 \lbrack l, r \rbrack 中的最值是多少。

设 f_{i, j} 为序列中区间 \lbrack i, i + 2^j - 1 \rbrack 中的最值，也就是 i \sim 2^j 中的最值。

由于使用倍增思想，所以子区间长度成倍增长，所以当我们计算 f_{i, j} 时可以从之前的左半边和右半边转移过来，即 f_{i, j} = \max(f_{i, j - 1}, f_{i + 2^{j - 1}, j - 1})。

void ST1()
{
    for (int i = 1; i <= n; i++)
        f[i][0] = a[i];

    int num = log(n) / log(2) + 1;
    for (int j = 1; j <= num; j++)
    {
        for (int i = 1; i <= n - (1 << j) + 1; i++)
            f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
    }
    return ;
}

当询问区间最值时，我们计算出一个值 k，满足 2^k < r - l + 1 \le 2^{k + 1}，即为 2^k 是小于区间范围长度前提下最大的 k。

而这个值可能小于区间长度，所以我们要分两段进行求值，分别是 “从 l 开始的 2^k 个数” 和 “r 前的 2^k 个数。

\text{so } \max(a_l \sim a_r) = \max(f_{l, k}, f_{r - 2^k + 1, k})

int ST2(int l, int r)
{
    int k = log(r - l + 1) / log(2);
    return min(f[l][k], f[r - (1 << k) + 1][k]);
}

注：ST 表可以求 最大/最小值，你只需要把 \max 替换为 \min 即可。

板子：lg P1816，lg P3865

LCA

LCA，最近公共祖先问题。

给定一颗有根树，若节点 k 既是节点 x 的祖先，又是节点 y 的祖先，则称 k 是 \lbrack x, y \rbrack 的公共祖先。在 \lbrack x, y \rbrack 的所有公共祖先中，深度最大的称为最近公共祖先，记作 \operatorname*{LCA}(x, y)。

--- 因为讲解倍增，所以这里使用 **树上倍增法** 求解。 设 $f_{x, k}$ 表示从 $x$ 节点走 $2^k$ 步到达的祖先节点，若此节点不存在则设 $f_{x, k} = 0$；显然，$f_{x, 0}$ 就是 $x$ 的父节点。 由于 $f_{i, j}$ 可以从 $f{i, j - 1}$ 走 $2^{j - 1}$ 步转移过来，所以得出神奇小公式：$\text{if } k \in \lbrack 1, \log n \rbrack, f_{x, k} = f_{f_{x, k - 1}, k - 1}

要解决这个问题，我们还要求出每个节点的深度，可以使用 dfs 解决。

在处理 LCA 时，我们以 \lbrack x, y \rbrack 中深度较大的开始，先使深度较大的缩短到最接近另一个深度的节点（自己 / 最近的祖先），然后一直向上即可。

完整代码：

#include <bits/stdc++.h>
#define int long long
#define il inline
using namespace std;

il int read()
{
    int x = 0;
    char c = getchar();
    while (c < '0')
        c = getchar();
    while (c >= '0')
    {
        x = x * 10 + (c - '0');
        c = getchar();
    }    
    return x;
}

int n, m, s;
vector<int> edge[500005];
int lca[500005][25], dep[500005];
void dfs(int x, int fa)
{
    lca[x][0] = fa;
    dep[x] = dep[fa] + 1;
    int now = edge[x].size();
    for (int i = 0; i < now; i++)
    {
        if (edge[x][i] == fa)
            continue;
        dfs(edge[x][i], x);
    }
    return ;
}
void pre()
{
    for (int j = 1; j <= 20; j++)
    {
        for (int i = 1; i <= n; i++)
            lca[i][j] = lca[lca[i][j - 1]][j - 1];
    }
    return ;
}
il int LCA(int x, int y)
{
    if (dep[x] < dep[y])
        swap(x, y);
    for (int i = 20; i >= 0; i--)
    {
        if (dep[lca[x][i]] >= dep[y])
            x = lca[x][i];
    }
    if (x == y)
        return x;
    for (int i = 20; i >= 0; i--)
    {
        if (lca[x][i] != lca[y][i])
            x = lca[x][i], y = lca[y][i];
    }
    return lca[x][0];
}
signed main()
{
    n = read(); m = read(); s = read();
    for (int i = 1; i < n; i++)
    {
        int x, y;
        x = read(); y = read();
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    dfs(s, 0);
    pre();
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        x = read(); y = read();
        cout << LCA(x, y) << "\n";
    }
    return 0;
}

时间复杂度：O(m \log n)。

注：本代码用于 AC lg P3379 模板问题。

参考资料

https://www.dotcpp.com/course/947

https://www.cnblogs.com/boranhoushen/p/16557961.html

https://blog.nowcoder.net/n/63f14dae8a194960844facb24c23e58f?from=nowcoder_improve

图论算法：树上倍增法解决LCA问题 - hugeYlh - 博客园