2020-11-26 21:31 已编辑天津大学 C++

关注

倍增

说在前面的

本人实力不高，求大佬轻喷，我尽量讲清楚一点。

例题传送门
在未作说明的情况下，有根树都以 $1$ 为根。
$lca(u,v)$ 表示，节点 $u,v$ 的最进公共祖先。
$dep_u$ 表示，节点 $u$ 的深度。
$dis(u,v)$ 表示，节点 $u,v$ 的树上简单路径长度。

倍增

倍增法（英语： $\text{binary lifting}$ ），顾名思义就是翻倍。它能够使线性的处理转化为对数级的处理，大大地优化时间复杂度。

引入

$q$ 次询问，求一个节点的 $K$ 级祖先。

分析

我们考虑最暴力的做法，每个节点保存它的父亲，那么连续跳 $K$ 次父亲就可以得到 $K$ 级祖先。但这样的单次复杂度为 $O(n)$ 的。
我们可以想到，由于没有修改整棵树。那么每一个节点的父亲是唯一的，那么这启发了我们使用一个算法，快速的查询祖先。这个我们可以考虑倍增。我们考虑对于 $\forall x\in\mathbb{N^{*}}$ 都有唯一的用二进制表示的方案，所以我们可以只保存它的 $2^k$ 级祖先。这样我们就可以在 $O(\log n)$ 内，得到一个节点的树上 $K$ 级祖先。但是我们也需要一个空间为 $O(n\log n)$
图例
后话，关于 $K$ 级祖先的查询，可以使用长链剖分可以达到 $O(1)$ 回答，有兴趣的朋友可以自行查看。

代码

初始化

fa[x][0] = father;
for(int i = 1;i <= Log[dep[x]];i++) 
fa[x][i] = fa[fa[x][i - 1]][i - 1];

查询

int k,x;
for(int i = Log[k];k >= 0;k--) {
    if((k >> i) & 1) x = fa[x][i];
}

拓展1

求有根树上两个节点 $u,v$ 的最近公共祖先。

分析

我们可以分析到，如果不相同，那么的深度一定不小于。那么这里定义，那么我们可以先把提高为它的级祖先，使这两个节点深度相同，便于之后的操作。
- 如果 $u=v$ ，那么证明原本的 $u$ 是 $v$ 的子树中的某一个节点，他们的 $lca$ 为 $v$ 。
- 如果 $u\ne v$ ，那么 $u,v$ 属于 $lca(u,v)$ 的不同子树。那么我们可以考虑二分 $dis(lca(u,v),u)$ 的距离，这样我们就得到了 $O(\log^2n)$ 的做法。但其实我们可以再考虑一下倍增的性质，由于 $2$ 进制表示是可以贪心的，那么如果两个节点 $2^{p}$ 级祖先相同，那么 $dis(lca(u,v),u) \le 2^{p}$ ，反之 $dis(lca(u,v),u) > 2^p$ 。这样我们每次把问题范围减少为 $\frac{1}{2}$ ，那么由高位到低位贪心，就可以在 $O(\log n)$ 的时间范围内求出两个节点 $u,v$ 的 $lca(u,v)$ 。

代码

    int lca(int a,int b) {
        if(dep[a] < dep[b]) swap(a,b);
        int k = dep[a] - dep[b];
        for(int i = Log[k];~i;i--) if((k >> i) & 1) a = fa[a][i];
        if(a == b) return a;
        for(int i = Log[dep[a]];~i;i--) if(fa[a][i] ^ fa[b][i]) a = fa[a][i],b = fa[b][i];
        return fa[a][0];
    }

后话，关于查找 $LCA$ 的做法有很多很多，这里不详细展开了。

拓展2

给你一个长度为 $n$ 的序列， $Q$ 次询问，查找 $[l,r]$ 的最大值。

分析

相信很多同学知道线段树之类的 $O(n\log n)-O(\log n)$ 前者为初始化复杂度，后者为单次查询复杂度的做法。

这里我们可以通过该题无修改的优秀性质，考虑一个 $O(n\log n)-O(1)$ 的做法。我们可以分析 $\max$ 函数其实是有一个优美的性质的 可重复贡献 ，那么 $\max\{a_1,a_2,a_3\} \Leftrightarrow \max\{a_1,a_2,a_3,a_3\}$ 所以，对于一个询问 $Q(l,r)$ ，我们可以形式化的写成 $\max\{a_l,a_{l+1}...a_{r}\}$ 那么等同于 $\max\{Q(l,l+2^p-1),Q(r-2^p+1,r)\}$ ，其中 $p=\lfloor\log_{2}(r-l+1)\rfloor$ 的，这样我们就做到了对于一个区间拆分成两个区间，而且两个区间的并集是等于原区间的。而 $\max\{a_{i},a_{i+1}...a_{i+2^p-1}\}$ 就比较简单的。我们定义 $f(i,p)=\max\{a_{i},a_{i+1}...a_{i+2^p-1}\}$ 是等同于 $\max\{f(i,p-1),f(i+2^{p-1},p-1)\}$ 那么 $f(i,p)$ 一共有 $n\log n$ 的状态，初始化的时间复杂度为 $O(n\log n)$ ，而每次查询为 $O(1)$ ，空间复杂度为 $O(n\log n)$ 。
图例
这种做法可以拓展到，只要一个函数满足 可重复贡献 的性质，那么都可以使用这种方法的。例如区间 $\gcd$ 。而且区间 $\gcd$ 用 $\text{St}$ 表维护，时间复杂度为 $O(n(\log n+ \log w))-O(\log w)$ 的。

代码

询问

int query(int l,int r) {
        int k = Log[r - l + 1];
        return max(st[l][k],st[r-(1<<k)+1][k]);
    }

初始化

        for(int i = 2;i <= n;i++) Log[i] = Log[i >> 1] + 1;
        for(int j = 1;j <= Log[n] + 1;j++) {
            for(int i = 1;i + (1 << j) - 1 <= n;i++) {
                st[i][j] = max(st[i][j-1],st[i+(1<<j-1)][j-1]);
            }
        }