Level Ancestor 问题

形式陈述 ​

接口与参数约定 ​

给定含 $n\ge 1$ 个节点的静态有根树理路有根树与祖先关系Rooted tree · Ancestor relation in a rooted tree · Parent and depth in a tree在树中选定根后，由唯一根路径定义父子、祖先、深度与子树。，根的深度固定为 $0$。目标深度及步数均为整数。对节点 $v$ 和目标深度 $d$，定义

等价的第 $k$ 个祖先接口返回 $LA(v,depth(v)-k)$，其中 $0\le k\le depth(v)$；$k=0$ 返回 $v$，$k=depth(v)$ 返回根。页面以下用目标深度 $d$，避免把“深度”与“向上步数”混作同一参数。

树的唯一根路径保证答案存在且唯一。若 $d>depth(v)$ 或 $d<0$，接口应返回 $\mathrm{\perp }$ 或拒绝查询，不能依赖数组越界偶然充当哨兵。

Binary Lifting 基线 ​

二进制倍增理路二进制倍增Binary lifting · Doubling technique预计算函数的 $2^k$ 次迭代，用输入步数的二进制展开快速跳转。保存

预处理与空间为 $O(n\log (n+1))$，查询把 $k=depth(v)-d$ 按二进制分解，用最坏 $O(\log (n+1))$ 次跳转到答案。这一路线简单，还能同步维护路径摘要，但不是静态 Level Ancestor 的最优空间—查询组合。

先把查询压成一次跳跃与一次索引 ​

先求每个节点到最深后代的边数 $h(v)$，并让每个非叶节点选一个最高的孩子继续路径。这些不相交的最长向下路径覆盖全部节点。每条原路径有 $L$ 个节点，就在其顶部再复制至多 $L$ 个祖先，遇根停止，形成 ladder；全部扩展表的长度至多 $2n$，构造只需 $O(n)$ 时间。

节点 $v$ 所属的原路径会一直走到它的最深后代，所以其 ladder 在根以下至少容纳 $h(v)$ 步向上距离。对查询距离 $k=depth(v)-d>0$，取 $j=\lfloor {\log }_{2}k\rfloor$，先跳到 $u=ancestor(v,2^j)$。由于 $v$ 是 $u$ 的一个距离 $2^j$ 的后代，有 $h(u)\ge 2^j$；剩余距离 $k-2^j<2^j$，因此答案落在 $u$ 的扩展 ladder 内，可按深度直接索引。$k=0$ 则立即返回 $v$。

若每个节点都保存全部跳指针，这个办法的查询已经是 $O(1)$，但预处理和空间仍是 $O(n\log (n+1))$。线性大小的 ladder 并没有消除那些跳指针。

用宏节点和微树把跳指针压到线性 ​

以下在字长 $w=\mathrm{\Omega }(\log (n+1))$、支持常数时间字访问的Word-RAM理路Word-RAM 模型Word RAM · Word-RAM model以 w 位机器字、常数时间随机访存和明确字级操作集分析算法的随机访问机模型。中分析。小规模树可直接制表；其余取 $b=\lfloor ({\log }_{2}n)/4\rfloor$。把“子树至少有 $b$ 个节点、每个孩子的子树都少于 $b$ 个节点”的节点标为跳节点。它们的子树两两不交，因此最多有 $n/b=O(n/\log n)$ 个。

仅对跳节点保存全部有效二次幂祖先；距离超过其深度时使用无祖先哨兵。构建时不需要先给所有其他节点建倍增表：知道距离 $2^{j-1}$ 的祖先 $u$ 后，$h(u)\ge 2^{j-1}$，可直接在 $u$ 的 ladder 内再向上走 $2^{j-1}$ 步，得到下一个跳指针。每个跳节点花 $O(\log n)$，总计 $O(n)$。

所有跳节点及其祖先称为宏节点，组成一棵连通宏树。一次遍历给每个宏节点 $v$ 指定一个跳节点后代 $w$。对 $d\le depth(v)$，有 $LA(v,d)=LA(w,d)$，故使用 $w$ 的一次跳跃和 ladder 索引即可在常数时间回答。

删除宏节点后的每个连通分量是少于 $b$ 个节点的微树：若某分量根的子树至少有 $b$ 个节点，其中就会包含一个最深的跳节点，与分量不含宏节点矛盾。固定孩子次序，一棵微树可用 DFS 上下行的 $2(b-1)$ 位以内编码描述，所有形状至多 $O(4^b)=O(\sqrt{n})$ 种。对每种形状预计算“本地 DFS 节点编号、目标本地深度”的全部答案，共需

时间和字空间。每棵实际微树只保存形状编码、根深度，以及本地编号到实际节点的数组，总共 $O(n)$。

查询若仍在原微树内，就查该形状表并还原节点；目标在微树之外时，直接转到微树根的父节点，再使用宏节点算法。最高置位也可由长度 $n$ 的共享表在 $O(n)$ 预处理后常数查询。由此得到完整的

微树形状表、跳节点表和 ladder 各有单独的线性预算；它们共同支撑这个静态界。