长链剖分

WC听课时听到可以$\Theta(1)$查询树上祖先的算法，叫长链剖分。然而讲课人非常厉害，说网上这种资料很多就没讲了。然而我姿势不够并搜不到。打听到该算法后在这里记录一下。

查询树上祖先的一般算法

静态树

静态的树上之前我只知道$O(\log n)$的倍增算法，即先构造出这棵树的倍增表$f[n][k]$，表示$n$号节点往树根走$2^k$步走到的祖先。这个东西可以在$O(n \log n)$的时间内预处理出来，具体的这里不再介绍，网上或者本博客一篇关于LCA的文章内都有介绍。
构建出倍增表后，如果我们想往上方走$d$步，那么可以将$d$按照二进制分解成几个$2$的幂的和，那么就可以利用倍增表进行$O(\log n)$次上跳，到达距离为$d$的祖先处。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

function find_ancestor(u, d):
    k = 0

    while d:
        if d & 1:
            u = f[u][k]
        d >>= 1
        k++

    return u

动态树

当然需要LCT啦。首先access到$u$，然后对于LCT上的平衡树，额外记录下每个节点的大小就可在平衡树上找出对应位置的祖先。

长链剖分

十分出名的树链剖分是按照儿子节点的大小来挑选重儿子的，这种剖分方法保证了每个节点到根的路径上的轻边数量为$O(\log n)$条。如果我们换用其它标准，如按照儿子节点的秩 (即节点到其子树内的叶子节点的最远距离) 为标准选取重儿子，称其为长链剖分，那么可以分析出轻边数量是$O(\sqrt n)$级别¹的。但这就无法体现出它的优势。

但是我们考虑另外一个事情：长链剖分之后，对于每个节点$u$，其子树中其它节点$v$到$u$的距离不超过$u$所处长链的长度。假设这个距离超过了链长，那么说明按照节点的秩来剖分的时候，就会朝着$v$的方向走。除非有多个最远点距离一样，否则这个最远点会与$u$在同一条长链上。所以它的距离不会超出链长。

那这有什么用？考虑另外一个事情：对于一个距离$d$，找到一个最大的$k$使得$2^k \leqslant d$，那么必定有$d - 2^k \lt 2^k$。同时，假如我们从一个点$u$往上走了$2^k$步到了$u^\prime$，那么根据之前的事实，$u^\prime$所处的长链的长度至少为$2^k$。令链长为$x$，由于剩下的步数小于$2^k$，所以我们如果有这条长链以及链顶往上走$x$步的所有顶点信息，那么就是存储$2x$个点，保存在一个数组内，然后就可以直接查找祖先了。总的时间复杂度为$\Theta(1)$。另外，由于由于所有长链的长度之和为$n$，所以最多记录$2n$个信息，即它的空间复杂度是$\Theta(n)$的。

因此实现的时候，需要计算倍增表和长链，这一步可以在$O(n \log n)$的时间复杂度内解决。然后查询的实现如下面的C++代码所示：

 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

/**
 * @param u (int) 当前节点
 * @param d (int) 距离
 * @return (int) 返回从当前节点往上走d步的祖先
 */
int find_ancestor(int u, int d) {
    assert(0 <= d && d <= depth[u]);  // 必须保证祖先存在

    if (d == 0)  // d = 0特判
        return u;

    int h = highbit[d];  // highbit用于记录数字1..n的最高位，提前预处理
    u = f[h][u];  // f是倍增表，上跳2^k步
    d -= 1 << h;

    assert(d < (1 << h));  // 满足事实1

    int t = top[u];  // top记录每个节点所处的链的链顶
    int pos = len[t] - 1 - (depth[u] - depth[t]) + d;  // len记录链长

    // chain是存储了2 * len[t]个节点的vector
    assert(0 <= pos && pos < chain[t].size());  // 满足事实2

    return chain[t][pos];  // 返回答案
}

倍增表和长度为$2x$的数组还可以存储其它信息。就以长度为$2x$的数组而言，可以记录前缀和或者利用ST表记录最大/最小值，配合快速的LCA算法从而能够$\Theta(1)$的时间复杂度回答两点间的路径上的特定信息的查询。

此外，如果不考虑倍增表，我们依然可以利用事实1从而达到在$O(\log n)$步跳到根节点，即每次跳到当前链能访问到的最后一个节点的父亲处。由于每次上跳到的新的链的长度必定翻倍，所以能做到这个复杂度。因此，长链剖分也可以以同样的时间复杂度实现树链剖分的功能。