O (log log n) 求 lca + lca 优化

WSY0814 · 2026-10-10 23:00:16 · 算法·理论

省流： 欧拉序 + ST 表 的优化，O (log log n) 的方法，优化所有 lca 的方法。

对比一下所有的求 lca 的方法 (在线，静态)：

欧拉序 + ST 表的常数太大了，让我们来优化一下它!

后面暂时只考虑二叉树，会进行扩展。

记 n_i 表示有 i 个子节点的节点个数 (0 \le i \le 2)，c (x) 表示 x 的子节点个数，\text {Sub} _ x 表示 x 的子树 (x \in Sub_x)。

n + n_2 个节点

直接把相邻第一次出现的节点之间的区间缩成深度最低的那个点。

分析结束后的节点个数，把每个点出现在欧拉序的情况分为两类，第一次和非第一次。

第一次出现一定会让深度增加 1，非第一次出现一定会让深度减少 1。

因为中间的区间都不是第一次出现，所以深度递减，只用保留最后一个点。

最终节点个数是 n 加上中间有点的间隔数，为 n + n_2，因为 n_0 = n_2 + 1，原式最多是 2n - 1 的 \frac 3 4，下面通过多种方式分析个数。

1.贡献归在后面的点上

因为每个点多次出现时，前后的点一定是第一次出现，所以下一个点一定是它的儿子，查询时可以把右端点省略。

发现非叶子节点出现时，下一个点就是它的某个儿子。所以除了没有父亲的第一个点，前面一定是它的父亲。

计算发现是 2 n - 1，思考可以发现我们记重了。

如果一个非叶子点第一次出现，会被记两次，减掉就是 2 n - 1 - n _ 1 - n _ 2 = n - 1 + n _ 0 = n + n _ 2。

2.贡献归在前面的点上

因为我们的方法是正确的，所以某个点和其后的间隔一定是它和其后点的 lca。

如果一个点不是下一个点的父亲，它们中间一定有一个点。

这种情况只会发生在叶节点上上，所以长度是 n + n _ 0。

但和前面求的不一样，发现是最后一个叶节点后没有间隔，所以要减 1，就是 n + n _ 0 - 1 = n + n _ 2。

3.把贡献归在间隔上

如果 x 和 y 相邻并且中间有间隔 z (取 x 在 y 前)。

前面证明了 z 一定是 x 和 y 的 lca，并且是 y 的父亲。

因为 z 是 x 和 y 的 lca，所以 z 是 x 的祖先。

如果 x 和 y 在 z 的同一子树内 z 就不是 x 和 y 的 lca 了，所以 x 和 y 不在同一子树。

因为相同子树内的节点在 a 数组中是连续区间，x 在 y 前。

所以 x 是它所在子树的最后一个点，x 的子树在 y 的子树前。

可以推出 z 有两个子树 (n_2)，x 是第一个子树的最后一个点，y 是第二个子树的第一个点，说明任意间隔都有两个子树。

还可以推出满足这个条件的 x 和 y 就有对应的 z，说明有两个子树的 z 就一定是某个间隔。

所以总节点数就是 n + n _ 2。

n 个点

前面证明了在求 lca 时如果需要求 [l, r] 的最小值时，可以求 [l, r) 的最小值，于是有了以下思路。

直接把缩出来的点跟上一个合并，易证一定是缩出来的点更优，缩成了 n 个点。

预处理 (主要)：

void dfs (int u, int par)
{
    a [++ tot] = u, v1 [u] = tot;
    for (const int & v : g [u])
        if (v != par)
        {
            dfs (v, u);
            a [tot] = u;
        }
}

查询：

int lca (int u, int v)
{
    int l = min (v1 [u], v1 [v]), r = max (v1 [u], v1 [v]);
    int lca = MAX (l, r);//a 数组在 [l, r) 内深度最小的点，[l, r) 为空则是 a [r]
    return lca;
}

n_0 个点

易证在 u 到 v 的路径非链时，\forall (x, y) x \in \text {Sub} _ u y \in \text {Sub} _ v \Rightarrow \mathrm {lca} (u, v) = \mathrm {lca} (x, y)，所以可以直接取 c (x) = c (y) = 0。

如果是链，可以通过判断按照上述方法求得的 lca 是否满足 \text {dep} _ {lca} \le \min (\text {dep} _ u, \text {dep} _ v)，如果不满足，就替换成深度更小的点，易证这是对的。

这样就只用保留 n_0 个点，再次压缩，易证如果在数组中，代表 u 的位置之后代表 v, a _ u = \mathrm {lca} (u, v)。

预处理：

void dfs (int u, int par)
{
    if (par && g [u].size () == 1)
        a [++ tot] = u, v1 [u] = tot;
    for (const int & v : g [u])
        if (v != par)
        {
            dfs (v, u);
            a [tot] = u;
        }
}

查询:

int lca (int u, int v)
{
    int l = min (v1 [leaf [u]], v1 [leaf [v]]), r = max (v1 [leaf [u]], v1 [leaf [v]]);
    int lca = MAX (l, r);//a 数组在 [l, r) 内深度最小的点，[l, r) 为空则是虚拟节点，深度无穷
    if (dep [lca] > dep [l]) lca = l;
    if (dep [lca] > dep [r]) lca = r;
    return lca;
}

也可以把得到的数组扩展成 \pm 1 RMQ，做到 O (n)，长度会比原来优。

思考可以发现这个方式相当于把树上的链压缩成了最下面的一个点，以后讨论也都假设树压缩过了。

我们可以通过这个性质压缩 ST 表里节点的权值，更适用于 \pm 1 RMQ，这在树中有链的情况下一定是比原来更优的。

正常取深度，我们可以改成取从根节点到它路径上的所有节点中，有多少个节点有两个儿子 (包括它本身)，可以更适用于 \pm 1 RMQ。

通用性扩展

这个优化只使用于二叉树，该怎么扩展呢？

容易发现，复杂度最高的情况是根节点下挂超级多个叶节点，我们就针对这个来优化。

因为在压缩树下不会出现叶节点没有兄弟的情况。

所以我们把同一父亲的叶节点合并到 2 个，仅保留第一个和最后一个来处理 （因为中间的权值 = 第一个的权值）。

最高大约是 \frac 2 3 \cdot n，因为如果合并有 2 m 个叶节点，父亲节点就有 m 个，所以就是 2 m \le 2 m \cdot \frac n {2 m + m} = n \cdot \frac {2 m} {3 m} \le \frac {2 n} 3 \approx \frac {2 n - 1} 6。

发现第一个点只在查询的点父亲相同时有用，所以可以特判，让后只留第二个节点，就是上面的 \frac 1 2，大约是 \frac {2 n - 1} {12}。

再把同一父亲的叶节点全都保留为他们的父亲节点（要特判考虑一个点的情况），这最高大约是 \frac 1 3 \cdot n。

当然，所有的都可以用这种方法去除链和叶节点。

可以通过这种方法 把所有复杂度里的的 n 改成 \frac 1 3 \cdot n，但预处理要加 O (n)，但通常跑不满。

O (log log n) 求 lca

嗯对我在优化常数时又想到了一个方法和它的优化，虽然是先想到的优化。

我们对每个节点看 lca 是它的节点可能是哪些，易证 \mathrm {lca} (u, v) = x 当且仅当 u \in \text {Sub} _ {l _ x}, v \in \text {Sub} _ {r _ x}，没有 l _ x 或 r _ x 叉出去，反了倒过来。

不妨设 \text {siz} _ {l _ x} \ge \text {siz} _ {r _ x}。

求出每个节点的前序遍历序 \text {id} _ x

每次把所有 v \in \text {Sub} _ {r _ x} 打上与 u \in \text {Sub} _ {l _ x} 的 lca 为 x 的标记，因为是连续的，可以只留右端点和父节点。

每个节点最多会有 O (log n) 个标记，所以预处理 O (n log n)，证明如下。

每个节点的标记个数等于从根节点到 x 的路径上有几次是往右子树去，但这种边是轻边，所以可以直接套用重链剖分的结论。

查询直接二分， O (log log n)，常数小。

优化

首先把一条链的情况扔出去，按照之前讲的方法来特判。

优化就是因为一条链的情况已经有处理方法了，可以只留叶节点，\text {siz} _ x 可以只看其下叶节点的个数。复杂度是原来的 \frac 1 2。

和 O (1) 算法的转化

前面说了，我们需要标记所有 u \in \text {Sub} _ {l _ x}, v \in \text {Sub} _ {r _ x} 的 lca 为 x。

我们也可以在 \text {Sub} _ {l _ x} 的部分与 \text {Sub} _ {r _ x} 的部分之间增加一个 x，这是 n _ 0 + n _ 2 的。

也可以直接把 \text {Sub} _ {l _ x} 中最后一个点的值改成 x，观察到和前面的 n _ 0 算法等价。

通用性扩展

把重链放最前，那么复杂度如下。

考虑每个点会有几个标记，很容易就能发现是从根节点到它的路径上轻边的数量，可以套用重链剖分的结论。

:::info[说明]{open} 为什么那么多易证：写不完，根本写不完！最近没时间，以后再补，总之都是我证明过了的。

话说为什么几乎每个与 lca 有关的文章下面都会固定刷新 dfs 序评论啊？

为什么我加了上面那句话以后的评论全在说 “dfs 序求 lca 多用”。