静态树上的最近公共祖先问题

基本概念

树 $T = (V,\;f,\;r)$ 是一张无向图，其中 $V$ 是点的集合，$f(u)$ 表示点 $u$ 的父亲，$r$ 是树的根，并且 $f(r) = \varnothing$，即根不存在父亲。下文中通常用正整数表示点，为了方便，令 $f(r) = 0$，点 $0$ 是一个不存在的点。树中除 $r$ 外，每个点都与它的父亲连边构成边集。记录 $\mathrm{ch}(u)$ 表示 $u$ 的儿子的集合，定义为 $\mathrm{ch}(u) = \{v:\;f(v) = u,\;v \in V\}$
。定义 $d(u)$ 表示点 $u$ 到根 $r$ 的简单路径上边的数量，即到根的距离，也称深度，因此有 $d(r) = 0$。令 $\max\{d(u):\;u \in V\}$ 表示树的高度，通常记为字母 $h$。

一个点 $u$ 到根 $r$ 的简单路径上的所有点都称为 $u$ 的祖先，构成的集合记做 $C(u)$（为了方便，自己可以是自己的祖先）。而两个点 $u$ 和 $v$ 的最近公共祖先（Least Common Ancestors，LCA）为 $C(u) \cap C(v)$ 中深度最大的点，记为 $\mathrm{lca}(u,\;v)$。所有祖先中有 $u$ 的点的导出子图同样也构成一棵树，记为 $T_u$，称作以 $u$ 为根的子树。

接下来，为了方便，通常记 $n = |V|$，表示树中的点数。此外，由于下面介绍的算法都要处理多组询问（通常记作 $q$ 组），所以在讨论到某个算法时空复杂度的时候，用 $O(f(n))$-$O(g(n))$ 表示该算法的空间复杂度为 $O(f(n))$，以及单次询问的时间复杂度为 $O(g(n))$。

解决方案

朴素算法

既然是要求公共祖先，那么我们一个直接的想法就是现将一个点 $u$ 的祖先全部标记出来，然后 $v$ 在从最深的祖先开始（也就是 $v$ 自己），一个一个检查是不是已经被标记过。如果找到了一个被标记的点，那么这个点就是最近公共祖先。

一般的实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

function LCA(u, v):
    // mark: 大小为 n 的整数数组
    // cur: 一个整型，记录该函数被调用了多少次
    cur += 1
    while u != 0:
        mark[u] = cur
        u = f(u)
    while mark[v] != cur:
        v = f(v)
    return v

这样的算法的复杂度为 $\Theta(n)$-$O(h)$。也就是说最坏情况下可能需要 $O(n)$ 的代价来找到最近公共祖先。由于随机一棵树的树高期望为 $O(\log n)$，所以该算法在一般情况下比较高效。

另外值得一提的是，在一般图最大匹配的带花树算法中，由于有 “缩花” 这种操作，并且本身对求最近公共祖先的复杂度要求不高，所以很多带花树算法的实现中使用朴素算法。

倍增算法

通过进一步观察，可以发现到达某个深度之后，继续往上走都会是公共祖先，而最近公共祖先就是它们中深度最深的。利用这一点，就可以使用二分这一技巧。二分一个向上走的距离 $x$，找到 $v$ 向上走 $x$ 步的点 $p$，并检查 $p$ 是否是 $u$ 的祖先。如果 $p$ 是 $u$ 的祖先，则 $d(\mathrm{lca}(u,\;v)) \geqslant d(p)$，所以需要减小 $x$，反之则需要增大 $x$。

现在就需要解决两个问题：

1. 找到 $v$ 向上走 $x$ 步的点 $p$。
2. 确认 $p$ 是否是 $u$ 的祖先。

对于第一个问题，我们有一个 $O(n\log h)$-$\Theta(1)$ 的长链剖分算法，但是这里暂不讨论这个算法。考虑到二分实际上可以转变为倍增的形式，即可以将目标 $x$ 转为二进制位，并且从高位向低位试位：如果某一位赋为 $1$ 导致找到的 $p$ 是 $u$ 的祖先，则将其赋为 $0$，否则赋为 $1$。这样就保证试位过程中的 $p$ 始终不是 $u$ 的祖先，最后 $f(p)$ 就正好是 $\mathrm{lca}(u,\;v)$。

转为倍增的好处在于现在只用关心每个点 $v$ 向上走 $2^k$ 步的点 $p$ 了，而这样的点对于每个 $v$ 而言只有 $O(\log h)$ 个，因此总共只用记录 $O(n \log h)$ 这么多的信息。现在令 $g(u,\;k)$ 表示点 $u$ 向上走 $2^k$ 步的点 $p$，然后之前的倍增的过程就是这样：

1
2
3
4
5
6

function LCA(u, v):
    for k = int(log(h)) to 0:
        p = g(v, k)
        if p is not an ancestor of u:
            v = p
    return f(v)

现在需要求出 $g(u,\;k)$ 中的值。首先关注到 $g(u,\;0) = f(u)$，这一部分可以直接得到。接下来，对于向上走 $2^k$ 步，相当于是走两次 $2^{k-1}$ 步，所以我们得到：

$$ g(u,\;k) = g(g(u,\;k - 1),\;k - 1) \;\;\;\; \forall k \gt 0 $$

所以 $g$ 可以在 $O(n \log h)$ 的时间内计算出来。

接下来对于第二个问题，我们可以使用 DFS 序来解决这个判定问题。也就是记录每个点在以 $r$ 为起点的 DFS 过程中入栈和出栈的时间。由于 DFS 的性质，$T_u$ 中的所有点的入栈时间是一个连续的区间，所以就可以利用这一点在 $\Theta(n)$-$\Theta(1)$ 的复杂度完成判定任务。

当然，我们可以不用 DFS 序。想象一下，如果 $u$ 和 $v$ 所处的深度相同，那么可以将 $u$ 和 $v$ 同时向上面走同样的步数 $x$。如果走到了同一个点上，则说明 $x$ 需要减小，否则说明需要增大。那么在此之前，就需要将 $u$ 和 $v$ 调到同一个深度。

这里将再次利用二进制和我们的 $g$ 函数。如果现在 $u$ 所处的深度比 $v$ 深，则 $u$ 需要向上走 $x = d(u) - d(v)$ 步。例如，如果 $x = 1011_{(2)}$，就是相当于分别走 $2^0$、$2^1$ 和 $2^3$ 步。而这都可以利用 $g$ 函数实现。最后的实现一般是下面这样：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

// 计算 g 函数
for u = 1 to n:
    g(u, 0) = f(u)
for k = 1 to int(log(h)):
    for u = 1 to n:
        g(u, k) = g(g(u, k - 1), k - 1)

function LCA(u, v):
    if d(u) < d(v):
        u, v = v, u  // 交换 u 和 v

    x = d(u) - d(v)
    for k = 0 to int(log(x)):
        if (x >> k) & 1:
            u = g(u, k)

    if u == v:  // 需要特判 v 是 u 的祖先的情况
        return u

    for k = int(log(n)) to 0:
        if g(u, k) != g(v, k):
            u = g(u, k)
            v = g(v, k)

    return f(u)

最后，倍增算法的复杂度为 $O(n\log h)$-$O(\log h)$。相对于朴素算法而言，虽然花费了更多的空间，但是获得了时间复杂度的巨大提升，是一个非常不错的改进。另外，值得注意的是，如果实现良好，倍增法在随机树的情况下期望复杂度为 $O(\log \log n)$。

倍增的思想可以扩展到更多的问题上，例如，我们可以仿照 $g$ 数组记录一些其它的信息，如最大 / 最小值，就可以用来求树上两点间最短路径的边权最大 / 最小值。在后缀数组构建算法中，也有一个运用了倍增思想的时间复杂度为 $\Theta(n\log n)$ 的简单算法。

链剖分

看到这里的时候：

1
2

if u == v:  // 需要特判 v 是 u 的祖先的情况
    return u

不知道是否会想到，既然我们可以 $\Theta(1)$ 判定 $v$ 是否是 $u$ 的祖先，那为什么还要浪费时间来上跳呢？因为即使利用这一点可以减少计算量，却没有改进复杂度。但是并不意味着这种想法没有什么用，我们可以发现一个更深刻的道理：如果树是链状的，那么最近公共祖先问题就十分的 naïve 了，只需要比较 $d(u)$ 和 $d(v)$ 的大小即可。

现在我们要对付的树并不能如我们所愿的是链状，但是可不可以把 $u$ 和 $v$ 上跳，从而调到 $u$ 是 $v$ 的祖先呢？不妨尝试将树划分成许多长链，更形式化的说，就是用两两不相交的简单路径覆盖整棵树，从而使得每个点都在唯一的一条路径上：

当然，为了方便，简单路径上的点的深度是单调的（即不会出现先上行后下行的情况）。这些简单路径也称为链。这样一来在同一条链上的的情况就十分简单了。为了方便称呼，链中深度最小的点叫做链顶，如果一条树边不存在于任何一条链上，则称为轻边，否则称为重边。当 $u$ 和 $v$ 不在同一条链上时，可以让 $u$ 或者 $v$ 沿着链顶的轻边走上去，就会到达另外一条链。例如，如果 $u$ 在上图中的绿色点中，而 $v$ 在橙色点中，我们可以让 $u$ 沿着绿色和橙色之间的轻边走上去。到达橙色链，从而变成了一条链上的情况。具体的实现就大概就是这样：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

function LCA(u, v):
    // top: 一个整型数组，top[u] 表示 u 所处的链的链顶
    while top[u] != top[v]:
        // 挑选链顶深度较深的一个点向上跳
        if d(top[u]) > d(top[v]):
            u = f(top[u])
        else:
            v = f(top[v])

    // 此时 u 和 v 在同一条链上
    if d(u) < d(v):
        return u
    else:
        return v

现在的目标就是找出一种链剖分的方案，使得这种 “走轻边” 的情况尽量少。由于我们链剖分的方法所决定的，每个点沿着链向下走最多能走到一个儿子处，姑且称这个儿子为重儿子。当我们为每个点选取好重儿子后，链剖分的方案也就出来了。当然，随便选取重儿子是不可取的，就像在下面这棵树中：

如果随机选取，那么长链上的每条边就有 $1/2$ 的概率成为轻边，如果从底端走到根节点，期望要走 $h / 2$ 条轻边。

所以需要换一种思路，我们希望树上划分出的链尽量少，一种思路就是每次挑出最长的一条链。显然对于一个点 $u$，它的重儿子 $v \in \mathrm{ch}(u)$ 应当满足 $T_v$ 的树高最高。如果按照此标准选取重儿子，最多又会走多少条轻边呢？

不妨来分析一下如果已经走过了 $x$ 条轻边后，树中至少有多少个点。如上图所示，从最左下角的蓝色点 $u$ 开始走轻边，那么 $u$ 所经过的路径上至少有 $x + 1$ 个点。假设现在走到了 $p$，那么 $T_p$ 中的最长链至少为 $x + 1$，因为 $p$ 所在的长链是最长的，所以 $p$ 所处的长链的长度也至少为 $x + 1$。由此可以分析出：

$$ n \geqslant \sum_{k = 1}^{x + 1} k = {(x + 1)(x + 2) \over 2} \geqslant x^2 $$

换句话讲就是 $ x = O(\sqrt{n}) $。即任意一个点开始只要走 $O(\sqrt{n})$ 条轻边就可以到达根节点。最后这种方法的复杂度为 $\Theta(n)$-$O(\sqrt{n})$。实际上这种方法在之前提到过，通常称作长链剖分，它使用较少的空间和不是很坏的时间复杂度完成了最近公共祖先的计算任务。

但是这还没有结束，$O(\sqrt{n})$ 的时间复杂度相比之于倍增算法，还不是一个很理想的结果。回忆一下之前的分析过程中发现了什么：

如果 $T_u$ 中存在一条长度 $l$ 的链，那么 $u$ 所处的长链的长度至少为 $l$。

因为这一点，上述分析中每次到达的新的长链的长度至少加 $1$。由此，我们可以提出一个大胆的想法：每次向上走链长 $l$ 步，那么新到达的长链的长度就会翻倍，从而可以达到 $O(\log h)$ 的时间复杂度。

为了实现这一点，我们需要对于每一条长链记录它的长度 $l$，以及从链顶向上走 $l$ 步到达的点 $p$（如果链顶的深度不足 $l$ 则为根节点 $r$）。然后固定 $v$，不断上跳 $u$，直到 $p$ 是 $v$ 的祖先。这个时候发现仅这样做无法知道最近公共祖先，因为我们可能过头了，但是可以得知最近公共祖先一定在 $u$ 到 $p$ 的长链上，并且它满足二分性质。因此稍加改动，对于每条链，存储这条链本身的所有点，以及从链顶向上走至多 $l$ 步的所有点（总长最多为 $2l$），就可以完成最后一个二分过程了。

虽然每条链花费了 $2l$ 的空间来存储这些点，但是由于所有链长加起来只有 $n$，故最后的复杂度为 $\Theta(n)$-$O(\log h)$。我们成功实现了在倍增算法的基础上，减小空间开销的任务。

看到上面啰哩吧嗦一大堆，有的人可能一开始想法就不一样。可能会想尝试将重儿子 $v$ 选取为 $T_v$ 的大小最大的那一个。按照这个标准，之前长链剖分的最坏情况的那棵树，应该被划分成这样：

Aha！EXCITED！我们发现这样无论什么询问，最多走一次轻边了，显然科学了很多。在这种剖分中，如果使用之前长链剖分的 $O(\sqrt{n})$ 算法，现在的时间复杂度会变成什么了呢？

套用之前的分析过程，当一个点 $v$ 每走一条轻边到 $u$，我们就会知道 $u$ 的重儿子 $x$ 一定满足 $T_x$ 的大小不小于 $T_v$ 的大小，也就是说 $T_u$ 的大小相对于 $T_v$ 而言至少翻了一倍。最后得出结论，任意一个点走到根节点只会经过 $O(\log n)$ 条轻边。通过简单的调整选取重儿子的策略，我们直接获得了更加优秀的时间复杂度。实际上，这种剖分方法称为轻重链路径剖分（Heavy-Light Decomposition，HLD，又称树链剖分），这种思想在动态树（LCT、Toptree 之类）上发挥了极大的作用。

接下来又是一个老生常谈的问题，有了这种剖分方法，长链剖分就没有用处了吗？并不。之前提到了用长链剖分在 $O(n\log h)$-$\Theta(1)$ 的复杂度完成求一个点向上走 $k$ 步的点，这是一般算法无法做到的。经过之前对长链剖分的分析，相信你一定能想出具体方法。作为一个提示，那 $O(n \log h)$ 的空间实际上是被倍增算法中的 $g$ 函数吃掉了。

与倍增算法类似，链剖分方法实质上完成了对树上任意简单路径划分为少量链的目标，从而使得线性数据结构可以在树上大显身手。由于本文只讨论最近公共祖先问题，对于链剖分的其他扩展可以去寻找其他资料。

转化为 RMQ

就目前为止，我们一直在考虑直接在树上处理问题。有的时候，将一个问题转换为另外一个等价的问题，不失为一种奇妙的思路。

现在退回到一种十分朴素的实现方法：从点 $u$ 开始，搜索 $T_u$，如果 $v$ 在 $T_u$ 中，则最近公共祖先为 $u$。否则令 $u = f(u)$，继续执行以上过程。当然，如果某些点已经被遍历过了，则不需要再次访问。或者可以换一个角度：将树上的每条无向边拆为两条有向边。对于属于同一条无向边的两条有向边，我们优先走向下走的边。每进入一个点的时候，就记录一下，最后会构成一个序列。这实际上就是 DFS 序。

假设 $u$ 的 DFS 入栈时间早于 $v$ ，那么之前的朴素方法相当于从 $u$ 开始沿着这些边来搜索，直到到达 $v$。搜索过程中访问到的深度最小的点就是 $u$ 和 $v$ 的最近公共祖先。

现在情况就十分清楚了，由于这个 DFS 序是固定的，而且因为每条无向边都被拆成了两条有向边，加上进入根节点的一次记录，所以序列的长度为 $2n - 1$。现在我们将 DFS 序上每个位置的点 $u$ 换为 $u$ 的深度，称之为深度序列。这样相当于在一个长为 $2n - 1$ 的序列上，查询一个区间内的最小值。也就是静态区间最值问题（Range Minimum / Maximum Query，RMQ）。使用平衡树和线段树均可以做到 $\Theta(n)$-$O(\log n)$ 的复杂度，但这里不会讨论它们。接下来将会转为讨论专门用于解决静态 RMQ 问题的稀疏表算法（Sparse Table，又称 ST 表）。

稀疏表

首先注意到区间 $[l,\;r]$ 的最值可以由多个区间 $[l_1,\;r_1],\;[l_2,\;r_2],\;...,\;[l_k,\;r_k]$ 的最值得来，只要满足这些区间的并集是 $[l,\;r]$。基于这种思想，我们可以先预处理一些区间的最值，然后对于每一个询问，只要确保能找出一些已经处理过的区间并起来满足询问的要求，就可以回答询问。一个简单的想法就是拆成两个区间，一个是前缀一个是后缀：

嗯，分成两个区间，不难想到 $2^k + 2^k = 2^{k + 1}$。也就是说只用计算所有长度为 $2^k$ 的区间的最值，就可以在 $\Theta(1)$ 的时间内计算任意区间的最值。记 $f(i,\;j)$ 表示以 $i$ 为左端点，长度为 $2^j$ 的区间最值，然后令 $\mathrm{highbit}(n) = \lfloor \log n \rfloor$，即最大的 $k$ 满足 $2^k \leqslant n$。这个东西可以简单的在 $\Theta(n)$ 的时间内预处理出来。之后，每次查询就是这样的：

1
2
3
4
5
6
7

highbit[1] = 0
for i = 2 to n:
    highbit[i] = highbit[i >> 1] + 1

function QUERY(l, r):
    k = highbit[r - l + 1]
    return min(f(l, k), f(r - (1 << k) + 1, k))  // 或者 max

现在就只需要考虑如何计算 $f(i,\;j)$ 了。计算一个序列中所有长度为 $l$ 的区间的最值，可以使用一种叫做单调队列的方法。使用一个双端队列，来维护当前区间内从左至右的一个单调递减（或递增）序列，相当于是一个最值的候选队列。每次从后面加入一个元素时，就会导致队列里面不单调，所以需要不断地从尾部弹出元素，使得新的元素加入后，依然满足单调性。这样，队首的元素始终是最大（或最小）值。如果收缩左边界，导致队首元素被弹出，新的队首依然是最大（或最小）值。上述方法中每个元素只会入栈一次，出栈一次，所以单次复杂度为 $\Theta(n)$。由于我们需要计算的长度 $l$ 都是 $2$ 的幂，总共只有 $\Theta(\log n)$ 个，所以总的复杂度为 $\Theta(n \log n)$-$\Theta(1)$。

当然，我们有更简单的方法。因为每个长度为 $2^k$ 的区间可以拆成两个长度为 $2^{k-1}$ 的区间，因而可以递推计算，也就是 $f(i,\;j)$ 满足下面的关系（以最大值为例，$a_i$ 是目标序列）：

$$ \begin{aligned} f(i,\;0) & = a_i \\ f(i,\;j) & = \max\{f(i,\;j-1),\;f(i+2^{j-1},\;j-1)\} \;\;\;\; \forall j > 0 \end{aligned}$$

同样，它的复杂度也为 $\Theta(n \log n)$-$\Theta(1)$。如果将这个算法运用到最近公共祖先问题上面，我们就首次获得了单次询问时间为常数的算法。这是一个相当大的突破。

然而一切都还没有结束，我们不禁会想，能否继续优化，从而达到 $\Theta(n)$-$\Theta(1)$ 的理论下界呢（因为这是输入输出的复杂度）？答案是肯定的。就目前来看，我们只需要降低稀疏表的空间消耗，同时保证它的时间复杂度即可。

如何降低空间复杂度呢？一个奇葩的想法就是，如果只有 $n / \log n$ 个元素，那空间复杂度不就自然变成 $\Theta(n)$ 了吗？但如何实现这个看起来很不科学的想法呢？这时分块的技巧就可用上了。首先设定一个块大小 $S$，然后从前往后每 $S$ 个元素划为一块，注意最后一块可能没有 $S$ 个元素。这样整个序列就划为了 $\Theta(n / S)$ 块。考虑一下每一次询问可能出现的情况：

就上图列举的三种情况而言，实际上只有两种：

1. 询问跨越的块与块之间的分界线。
2. 询问没有跨越这个分界线。

此时不难发现，对于第一种情况，询问区间是由一些连续的块（可能没有）和首尾两个块的一个后缀和一个前缀构成。连续的块我们可以使用稀疏表解决，即用每个块内的最值表示这个块，构成一个序列，然后建立一个大小为 $\Theta(n/S)$ 的稀疏表；前缀和后缀部分，由于每个块的前缀最值和后缀最值总共只有 $\Theta(n)$ 个，也可以提前处理。这一部分的复杂度做到了 $\Theta(n)$-$\Theta(1)$。

对于第二种情况，似乎就没有那么方便了。现在我们对付的是一个大小为 $O(S)$ 的 RMQ 问题，如果直接尝试对每个块建立小的稀疏表，计算可知我们现在的空间复杂度是：

$$\Theta((n/S) \cdot S \log S+ (n / S) \cdot \log (n/S)) = \Theta(n \log S + (n \log n)/S)$$

通过对 $S$ 求导可知大约选取 $S = \log n$ 时达到最优复杂度，此时的空间复杂度为 $\Theta(n \log \log n)$。

What a pity！我们费尽心思，却仍然不能达到线性复杂度。注意到我们的空间几乎都用在处理一堆大小为 $O(S)$ 的子问题上了。由于每个位置上可以是任意数值，所以块与块之间几乎不可能相同，这导致利用现有的算法难以将空间复杂度降下来。

现在回到最开始要解决的问题，也就是求最近公共祖先。DFS 序总有一些非常好的性质，就例如之前的深度序列，不难发现这个序列上相邻两个数之差总是 $\pm 1$。这是因为 DFS 这个过程的每一步要么往下走，要么往上走。换句话说，深度序列的差分序列¹上只有 $\pm 1$。如果原序列长度为 $S$，那么它的差分序列就只有 $2^{S-1}$ 种，这远远小于原始序列可能的种数。

现在你也许可以猜到接下来要做什么了。由于差分序列种类不多，所以我们可以将差分序列做一遍前缀和处理，得到一个新的序列，第 $i$ 个位置上的值是差分序列上前 $i$ 个数的和，并且处理这个序列上的每个区间的最值。然后如果知道原始序列的第一项 $a$，那么原始序列就相当于是前缀和序列前添加一个 $0$，并且每个数都加上 $a$，所以可以轻松知道原始序列的最值。

这样一来，我们就可以使得大小为 $O(S)$ 的 RMQ 问题减小总空间代价了。选定 $S = \frac12\log n$，一方面，这样使得差分序列的种类只有 $2^{1/2\log n - 1} = \Theta(\sqrt{n})$ 种，因此我们可以简单粗暴的使用 $\Theta(S^2)$ 的空间为每一种差分序列计算区间最值，当然，你也可以使用稀疏表；另一方面，跨越多个块的询问同样可以使用之前的分块算法，并且空间复杂度依然是 $\Theta(n)$。综上，最近公共祖先问题可以在 $\Theta(n)$-$\Theta(1)$ 的复杂度解决了。

在具体实现上，由于 $\log n$ 不大，所以差分序列通常用二进制来表示（如二进制位 $1$ 表示差分序列上的 $+1$，对应的 $0$ 则表示 $-1$）。这样就只需要访问数组下标就可以知道特定差分序列的信息了。

笛卡尔树

虽然最近公共祖先的理论复杂度下界已经实现了，本文似乎也就没有必要继续下去了。但是之前我肯定的回答了 RMQ 能否达到理论下界，同时也为了揭示最近公共祖先和 RMQ 问题之间的一些联系，这里还是有必要说一下如何改进稀疏表的空间复杂度。

为了方便，接下来都只考虑最大值。我们知道，最大值一定是序列上的一个值，那么对于序列上的每个值，有哪些区间的最大值是它自己呢？首先来找出一个最大的区间满足这个区间的最大值就是自己，假设序列是 $a_i$，现在我们要确定的是 $a_x$ 的最大区间 $[l,\;r]$，那么可以从 $[x,\;x]$ 开始，检查 $a_{l-1}$ 是否不超过 $a_x$，如果是，则 $l$ 可以减 $1$；同理，如果满足 $a_{r+1} \leqslant a_x$，那么 $r$ 也可以加 $1$。当然我们需要满足 $l \geqslant 1$ 以及 $r \leqslant L$，其中 $L$ 是序列长度。这样做的正确性是显然的，因为这个区间不能跨过任何一个比 $a_x$ 大的位置。此外，我们容易得到所有满足最大值为 $a_x$ 的区间 $[l',\;r']$ 满足 $l \leqslant l' \leqslant x \leqslant r' \leqslant r$。

设 $l(x)$ 和 $r(x)$ 表示之前对于特定的 $x$ 所说的 $l$ 和 $r$，并且 $M(x) = [l(x),\;r(x)]$。求出所有的 $l(x)$ 和 $r(x)$ 固然可以使用贪心算法，但是它效率不高。其实这里可以使用之前提到过的单调队列。因为向左找出 $l(x)$ 的过程就相当于不停地从队列末尾弹出元素，直到找到第一个大于 $a_x$ 的元素。而求出 $r(x)$ 就是要知道 $a_x$ 是当谁加入队列后被弹出的，如果加入 $a_y$ 导致 $a_x$ 被弹出，那么说明 $a_y$ 是 $a_x$ 向右走的第一个大于 $a_x$ 的位置。此外还需要注意，最后队列里面肯定还会剩余一些元素没有被弹出来，这则说明这些元素的 $r(x)$ 都是 $L$。这样做的话就只用 $\Theta(n)$ 的时间复杂度了。具体的实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

// a: 长度为 L 的整型数组，表示序列
Q = []  // 单调队列
for i = 1 to L:
    while Q is not empty and a[Q.last()] <= a[i]:
        r(Q.last()) = i - 1
        Q.pop_back()

    if Q is empty:
        l(i) = 1  // 此时 a[i] 一路往左没有遇到更大的值
    else:
        l(i) = Q.last() + 1

    Q.push_back(i)

foreach i in Q:
    r(i) = L

现在我们来观察一个简单的例子：

此时你就会发现所有的这些区间两两之间只有包含和分离的关系。利用这种包含关系，我们实际上就可以构造一棵树：

这棵二叉树被称为笛卡尔树（Cartesian Tree）。对于知道 Treap 的人来说这个名词一定不陌生，这棵树相当于给每个位置 $x$ 的权值是 $a_x$ 后建立的 Treap。如果序列中没有重复的元素，那么这棵树是唯一的。回忆起所有满足最大值为 $a_x$ 的区间 $[l',\;r']$ 满足 $l(x) \leqslant l' \leqslant x \leqslant r' \leqslant r(x)$，那么说明这个最大值 $x$ 在树上一定是 $l'$ 和 $r'$ 的公共祖先。此外，还要满足 $l' \leqslant x \leqslant r'$，这恰好说明 $x$ 需要是 $\mathrm{lca}(l',\;r')$。因为如果不是最近公共祖先就不会将 $l'$ 和 $r'$ 隔开，就比如上图中的 $[3,\;5]$，这个区间的最大值是 $a_4$，而不是 $a_7$。

如果我们能够快速的构建出笛卡尔树，就可以使用上一节讨论的 $\Theta(n)$-$\Theta(1)$ 的最近公共祖先算法以同样的复杂度解决静态 RMQ 问题了。幸运的是，我们只用稍微修改一下之前的单调队列算法，就可以构造出笛卡尔树。

假设我们现在已经有了一棵笛卡尔树，考虑在后面加入一个新的元素 $a_x$ 时，笛卡尔树该如何变化。首先，我们还是要找出 $a_x$ 往左走的第一个比它大的元素 $a_y$，此时我们就知道 $y$ 是 $x$ 的父亲了。另外，不要忘记那些被弹出队列的点，这些的点的 $r$ 函数的值已经全部被修改为 $x - 1$ 了，所以会改变它们的父亲：

经修改后的算法实现应该是这样的：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

// 现在每个元素 a[i] 有三个属性 value、left 和 right，
// 分别表示权值、二叉树上的左儿子和右儿子，如果没有儿子则为 null
function BUILD-CARTESIAN-TREE(a):
    Q = []
    foreach x in a:
        while Q is not empty and Q.last().value <= x.value:
            Q.last().right = x.left
            x.left = Q.last()
            Q.pop_back()

        Q.push_back(x)

    // 最后留在队列里的点相连
    while Q.size() > 1:
        v = Q.last()
        Q.pop_back()
        Q.last().right = v

    return Q.first()  // 返回笛卡尔树的树根

至此，最近公共祖先问题和区间最值问题同时都得到了优秀的解决方案。现在我们来整理一下这两者之间的联系：

1. 利用 DFS 序可以将最近公共祖先问题转为区间最值问题。
2. 利用笛卡尔树可以将区间最值问题转为最近公共祖先问题。

注记

上文中实际上只介绍了在线算法，而没有介绍离线算法，一是因为离线算法应用场景比较少，二是因为我所知道的离线算法（分治法和 Tarjan 算法）的复杂度并没有达到理论下界（Tarjan 算法是一个复杂度接近常数的 $\Theta(n + q)$-$O(\alpha(n))$ 算法）。所以只在这里简单提及一下。分治算法使用了一种通常称作 “整体二分” 的思想：定义过程 $\mathrm{solve}(l,\;r)$ 会解决最近公共祖先的深度在 $[l,\;r]$ 的所有询问，这个过程大致执行步骤如下：

1. 令 $m = (l + r) / 2$，表示我们二分的答案。
2. 将所有深度为 $m$ 的点 $u$ 的子树 $T_u$ 内深度不大于 $r$ 的点的标号设为 $u$。
3. 对于每一个询问 $u$、$v$，如果 $u$ 和 $v$ 都有标号且标号相同，则说明 $d(\mathrm{lca}(u,\;v)) \geqslant m$，将这个询问交给 $\mathrm{solve}(m,\;r)$。否则将 $u$ 和 $v$ 都变为自己标号的父亲（如果没有标号则不变），并交给 $\mathrm{solve}(l,\;m-1)$。
4. 清除所有标号并且递归处理 $\mathrm{solve}(m,\;r)$ 和 $\mathrm{solve}(l,\;m-1)$。

分治算法本质上是实现了一个集体倍增的方法，其复杂度为 $\Theta(n + q)$-$O(\log h)$。Tarjan 算法则是对 DFS 序的处理，在回溯的时候将父亲与儿子利用并查集连接起来，并且在并查集上存储附加信息使得可以查询答案，实现起来比较方便。

在前文中留下了一个简单的思考题，就是利用长链剖分实现 $O(n \log h)$-$\Theta(1)$ 的祖先查询，这个算法可以在 https://riteme.github.io/blog/2017-2-6/long-chain.html 处找到答案。

RMQ 问题的实现方面，其实还有许多可以仔细思考的地方。虽然我们在理论上达到了最优，但是它付出了较大的空间代价，并且在一般情况下这种算法实际表现情况并不如想象中那么优秀。相关的讨论可以在 Wikipedia 的笛卡尔树（https://en.wikipedia.org/wiki/Cartesian_tree）的引用中找到。

最后，前面所提及的算法我基本上亲自使用 C++ 实现并测试过，这些代码可以在这里找到：https://github.com/riteme/test/tree/master/oi/algs/Graph/LCA