KACTL 算法笔记

054-图论-二进制提升

5 min read

  1. 核心概述 在树上预处理每个节点的 2^k 级祖先表与深度，支持 O(log N) 的向上跳跃与 LCA 查询，预处理 O(N log N)。

  2. 原文引述

Description: Calculate power of two jumps in a tree, to support fast upward jumps and LCAs. Assumes the root node points to itself. Time: construction , queries

  1. 展开阐述

  • 定义与背景

    • 二进制提升（Binary Lifting）：为每个结点准备其第 2^k 个祖先，从而把“向上走 steps 步”拆为若干个 2^k 的二进制组合；并据此实现最近公共祖先（LCA）查询。
    • 适用范围：静态森林/树（可将多个根视作虚根的子树）；实现约定“根的父亲是其自身”。

  • 接口/字段/数据结构（据实现约定）

    • vector treeJump(vi& P)：输入父数组 P（P[root]=root），返回跳表 tbl，其维度为 d × N，d≈⌈log2 N⌉。
    • int jmp(vector& tbl, int nod, int steps)：从 nod 向上走 steps 步，若越过根则返回根（根的父为根）。
    • int lca(vector& tbl, vi& depth, int a, int b)：在给定深度数组 depth 的前提下，返回 a 与 b 的 LCA。

  • 预处理流程

    1. 维度计算
      • 取最小 d 使得 2^{d-1} < N ≤ 2^d，建立表 tbl[d][N]。
    2. 基层父表
      • tbl[0][v] = P[v]（直接父亲）；根满足 P[root]=root。
    3. 倍增递推
      • 对 k∈[1..d-1]，tbl[k][v] = tbl[k−1][ tbl[k−1][v] ]，即“2^{k−1} 两次跳跃叠加为 2^k”。

  • 查询与要点

    • 向上跳跃 jmp(tbl, nod, steps)
      • 从低位到高位（或高到低均可）枚举 steps 的二进制位 bit，如果 bit 置位则 nod = tbl[bit][nod]。
      • 若任一步到达根，则后续跳跃保持为根（因根的父指向自身）。
    • 最近公共祖先 lca(tbl, depth, a, b)
      1. 对齐深度：令 a 为较深节点，执行 a = jmp(tbl, a, depth[a]−depth[b])。
      2. 若 a==b，则返回 a。
      3. 自高到低枚举 k：若 tbl[k][a] != tbl[k][b]，则同步跳：a = tbl[k][a]，b = tbl[k][b]。
      4. 返回 tbl[0][a] 作为 LCA。
    • 深度一致性
      • depth[root]=0，depth[v]=depth[P[v]]+1；对森林可为每棵树独立设置根并执行相同规则。

  • 复杂度与边界条件

    • 预处理：O(N log N)；查询 jmp/lca：O(log N)。
    • 森林：可为每个连通分量挑选根，P[root]=root；LCA 仅在同一树内有意义。
    • 根约定：必须保证 P[root]=root，否则会在越界时产生未定义访问。
    • 退化链：d≈⌈log2 N⌉，不会因退化为链而影响渐进复杂度。
    • 节点越界/不存在：调用端应保证节点编号有效。

  • 变体/扩展

    • 跳跃附加信息：在 tbl 的同时维护“跳跃路径上的聚合信息”（如最小边权/最大边权），在 LCA/路径查询中返回区间聚合。
    • 支持 K 距离祖先/第 k 个祖先查询：jmp 即可；若需要“第 k 个后代”需额外树上顺序结构。
    • 与 RMQ 的关系：经典 LCA 亦可用 Euler Tour + RMQ 在 O(1) 查询；二进制提升实现更直观且易合并路径聚合信息。

  • 正确性要点与不变式

    • 祖先闭包：tbl[k][v] 恒是 v 的祖先；根的自环保证任何超出高度的跳跃都被“吸附”到根。
    • 二进制分解：任意 steps 的向上跳跃可唯一分解为若干个 2^k 跳跃之和，查询通过按位组合实现。
    • LCA 分离：自高到低尽量让 a、b 同步“抬升到 LCA 的子节点”，最终其父即 LCA。

  • 对比与取舍

    • 与 068-图论-最近公共祖先 的 RMQ 法：RMQ 可 O(1) 查询但需更复杂的预处理；二进制提升在需要路径聚合时更灵活。
    • 与 066-图论-重链剖分：HLD 便于路径分段到线段树/树状数组；若仅需 LCA/上跳，二进制提升更轻量。
    • 与在线维护（如 Link-Cut Tree 069-图论-LinkCutTree）：后者支持动态改树；二进制提升针对静态结构，常数更小。
  1. 关联节点

Graph View

Backlinks