说在前面的

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

  • 例题传送门
  • 在未作说明的情况下,有根树都以 为根。
  • 表示,节点 的最进公共祖先。
  • 表示,节点 的深度。
  • 表示,节点 的树上简单路径长度。

倍增

倍增法 (英语: ),顾名思义就是翻倍。它能够使线性的处理转化为对数级的处理,大大地优化时间复杂度。

引入

次询问,求一个节点的 级祖先。

分析

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

代码

初始化

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

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

分析

  • 我们可以分析到,如果 不相同,那么 的深度一定不小于 。那么这里定义 ,那么我们可以先把 提高为它的 级祖先,使这两个节点深度相同,便于之后的操作。
    • 如果 ,那么证明原本的 的子树中的某一个节点,他们的
    • 如果 ,那么 属于 的不同子树。那么我们可以考虑二分 的距离,这样我们就得到了 的做法。但其实我们可以再考虑一下倍增的性质,由于 进制表示是可以贪心的,那么如果两个节点 级祖先相同,那么 ,反之 。这样我们每次把问题范围减少为 ,那么由高位到低位贪心,就可以在 的时间范围内求出两个节点

代码

    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];
    }
  • 后话,关于查找 的做法有很多很多,这里不详细展开了。

拓展2

给你一个长度为 的序列, 次询问,查找 的最大值。

分析

相信很多同学知道线段树之类的 前者为初始化复杂度,后者为单次查询复杂度的做法 。

  • 这里我们可以通过该题无修改的优秀性质,考虑一个 的做法。我们可以分析 函数其实是有一个优美的性质的 可重复贡献 ,那么 所以,对于一个询问 ,我们可以形式化的写成 那么等同于 ,其中 的,这样我们就做到了对于一个区间拆分成两个区间,而且两个区间的并集是等于原区间的。而 就比较简单的。我们定义 是等同于 那么 一共有 的状态,初始化的时间复杂度为 ,而每次查询为 ,空间复杂度为
  • 图例
    图片说明
  • 这种做法可以拓展到,只要一个函数满足 可重复贡献 的性质,那么都可以使用这种方法的。例如区间 。而且区间 表维护,时间复杂度为 的。

代码

询问

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]);
            }
        }
  • 后话,其实关于这个问题还有 的做法 这个

总结

倍增一般优化的是静态的数据,而且 唯一对应。这样可以将 变为多个函数复合的形式,从而优化复杂度。

  • 在树上倍增,序列上倍增都是非常常见的。而且二分查找也可以用倍增替换,常数更小。