说在前面的
本人实力不高,求大佬轻喷,我尽量讲清楚一点。
- 例题传送门
- 在未作说明的情况下,有根树都以 为根。
- 表示,节点 的最进公共祖先。
- 表示,节点 的深度。
- 表示,节点 的树上简单路径长度。
倍增
倍增法 (英语: ),顾名思义就是翻倍。它能够使线性的处理转化为对数级的处理,大大地优化时间复杂度。
引入
次询问,求一个节点的 级祖先。
分析
- 我们考虑最暴力的做法,每个节点保存它的父亲,那么连续跳 次父亲就可以得到 级祖先。但这样的单次复杂度为 的。
- 我们可以想到,由于没有修改整棵树。那么每一个节点的父亲是唯一的,那么这启发了我们使用一个算法,快速的查询祖先。这个我们可以考虑倍增。我们考虑对于 都有唯一的用二进制表示的方案,所以我们可以只保存它的 级祖先。这样我们就可以在 内,得到一个节点的树上 级祖先。但是我们也需要一个空间为
- 图例
- 后话,关于 级祖先的查询,可以使用长链剖分可以达到 回答,有兴趣的朋友可以自行查看。
代码
初始化
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]); } }
- 后话,其实关于这个问题还有 的做法 这个 。
总结
倍增一般优化的是静态的数据,而且 唯一对应。这样可以将 变为多个函数复合的形式,从而优化复杂度。
- 在树上倍增,序列上倍增都是非常常见的。而且二分查找也可以用倍增替换,常数更小。