新人须知
新人须知

倍增法

倍增法（Binary Lifting）概述

倍增法（Binary Lifting）是一种高效的算法思想，主要用于跳跃式查询和倍增查询等问题。在解决问题时，倍增法可以将时间复杂度从线性 O(n) 减少到对数 O(log n)。

倍增法的核心思想是：

  1. 通过预处理阶段，存储跳跃的“倍数”关系（比如：2倍、4倍、8倍等）。
  2. 在查询阶段，利用这些预处理数据快速定位答案。

主要应用场景

  1. 树上最近公共祖先（LCA）查询
    • 利用倍增法快速求解两个节点的最近公共祖先。
  2. 跳跃查询问题
    • 比如：在链表或数组中，从某个位置开始，经过 k 步后会到达哪个位置。
  3. 区间快速查询
    • 例如：求某个值的倍数位置。

基本原理：利用二进制表示加速跳跃

给定一个查询问题，比如 “从某个点 u，经过 k 步到达哪个点？”
我们可以利用二进制的特性，将 k 分解成若干个 2ⁱ 的和。

例如：

  • k=13，二进制表示为 1101。
    • k = 8 + 4 + 1 = 2³ + 2² + 2⁰

思想：
我们只需要预处理出 “从某个点出发，跳跃 2ⁱ 步后的点”，然后在查询时，利用 k 的二进制表示组合这些 2ⁱ 步即可。

应用一：跳跃查询问题

问题描述

在一个数组或链表中，每个点指向一个下一位置。给定一个起点 u，我们想知道从 u 出发，经过 k 步会到达哪个位置？

解题步骤

  1. 预处理阶段：倍增表的构建

    • 设 f[i][j] 表示从节点 i 出发，经过 2ʲ 步后到达的节点。
    • 状态转移方程： f[i][j] = f[f[i][j-1]][j-1] 即：从节点 i 出发，走 2ʲ 步，可以拆分为走两次 2^(j-1) 步。

  2. 查询阶段：分解 k

    • 将 k 表示为二进制的若干个 2ⁱ 之和。
    • 对于 k 的每一位 1，累加对应的 2ⁱ 步数。

代码实现

假设有 n 个点，每个点有一个 next 指向它的下一位置。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100010;
const int LOG = 20;

int f[MAXN][LOG];

void preprocess(int n, vector<int>& next) {
    for (int i = 1; i <= n; i++) {
        f[i][0] = next[i];
    }

    for (int j = 1; j < LOG; j++) {
        for (int i = 1; i <= n; i++) {
            f[i][j] = f[f[i][j-1]][j-1];
        }
    }
}

int query(int u, int k) {
    for (int j = 0; k > 0; j++) {
        if (k & 1) {
            u = f[u][j];
        }
        k >>= 1;
    }
    return u;
}

int main() {
    int n = 5;
    vector<int> next = {0, 2, 3, 4, 5, 5};

    preprocess(n, next);

    int start = 1, steps = 7;
    cout << "从节点 " << start << " 经过 " << steps << " 步到达节点：" << query(start, steps) << endl;

    return 0;
}

代码解释

  1. 预处理倍增表：

    • f[i][0] 表示从 i 出发，走1步到达的位置。
    • f[i][j] 根据状态转移方程构建。

  2. 查询：

    • 将 k 的二进制表示逐位检查。
    • 如果 k 的某一位为 1，就执行对应的 2ⁱ 步跳跃。

  3. 复杂度分析：

    • 预处理时间复杂度： O(n log n)
    • 单次查询时间复杂度： O(log k)

应用二：树上 LCA 问题

倍增法也可以用来求解树上两个节点的最近公共祖先（LCA）。方法类似，预处理每个节点的 2ⁱ 级父节点，然后快速跳跃到目标层次找到公共祖先。

总结

  1. 倍增法的核心思想：
    利用二进制分解，将查询问题转换为若干次 2ⁱ 跳跃的组合。

  2. 主要步骤：

    • 预处理阶段：构建倍增表。
    • 查询阶段：利用倍增表加速跳跃。

  3. 时间复杂度：

    • 预处理： O(n log n)
    • 单次查询： O(log n)

倍增法是一种非常高效的算法技巧，在树结构、跳跃查询等场景中有广泛应用。

小结

ON THIS PAGE