倍增算法实例讲解

86145 阅读 0 评论 0 点赞

本篇将简要介绍倍增法。倍增法（英语：binary lifting），顾名思义就是翻倍。它能够使线性的处理转化为对数级的处理，大大地优化时间复杂度。这个方法在很多算法中均有应用，其中最常用的是 RMQ 问题和求 LCA（最近公共祖先）。

一、什么是倍增？

倍增，字面意思就是“成倍增长”。这是指我们在进行递推时，如果状态空间很大，通常的线性递推无法满足时间与空间复杂度的要求，那么我们可以通过成倍增长的方式，只递推状态空间中在 2 的整数次幂位置上的值作为代表。当需要其他位置上的值时，我们通过“任意整数可以表示成若干个2的次幂项的和”这一性质，使用之前求出的代表值拼成所需的值。所以使用倍增算法也要求我们递推的问题的状态空间关于2的次幂具有可划分行。

“倍增”与“二进制划分”两个思想相互结合，降低了求解很多问题的时间与空间复杂度。快速幂其实就是“倍增”与“二进制划分”思想的一种体现。其他应用还有，序列上的倍增问题，求解RMQ（区间最值）问题的ST算法，求解最近公共祖先（LCA）等。

二、基本用法

倍增主要用途是为了查找单调数据组中某一数值。

比如：在一个数组a {2,5,7,11,19} 中查找最大的小于12的数字。

（1）朴素做法：从第一个数开始，一个一个往后枚举，查找。

（2）二分做法：每次将数列分割一半判断，并且进一步查找子区间。

（3）倍增做法：设定一个增长长度 p 和已确定长度 l，现在要确定 a[l+p] 是否满足条件，若满足条件（比12小），则p成2倍增长；否则 p 缩小范围（试着缩小范围判断条件）。

主要代码：

l=0;
p=1;
while(p)//如果还能扩增范围(l)就继续
{
    if(a[l+p]<12)
    {
        l+=p;//增加已知范围
        p<<=1//成倍增长，相当于p*=2
    }
    else
    {
        p>>=1;//缩小范围
    }
}
cout<<a[l];

倍增算法一般比较稳定，时间 O(logn)。

三、ST算法

在RMQ问题（区间最值问题）中，著名的ST算法就是倍增的产物，给定一个长度为 N 的数列 A，ST算法能在O(N logN) 时间的预处理后，以 O(1) 的时间复杂度在线回答“数列 A 中下标在 l~r 之间的数的最大值是多少”这样的区间最值问题。

一个序列的子区间个数显然有 O(N^2) 个，根据倍增思想，我们首先在这个规模为 O(N^2) 的状态空间里选择一些 2 的整数次幂的位置作为代表值。

设 F[i,j] 表示数列 A中下标在子区间 [i,i+2^j-1] 里的数的最大值，也就是从 i 开始的 2^j 个数的最大值。递推边界显然是 F[i,0] = A[i]，即数列 A 在子区间 [i,i] 里的最大值。

在递推时，我们把子区间的长度成倍增长，有公式 F[i,j] = max(F[i,j-1],F[i+2^(j-1),j-1])，即长度为 2^j 的子区间的最大值是左右两半长度为 2^(j-1) 的子区间的最大值中较大的一个。

void ST——prework(){
    for(int i=1;i<=n;i++) f[i][0]=a[i];
    int t=log(n)/log(2)+1;
    for(int j=1;j<t;j++)
        for(int i=1;i<=n-(1<<j)+1;i++)
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}

当询问任意区间 [l,r] 的最值时，我们先计算出一个 k，满足 2^k < r - l +1 ≤ 2^(k+1)，也就是使 2 的 k 次幂小于区间长度的前提下最大的 k。那么“从 l 开始的 2^k 个数”和“以 r 结尾的 2^k 个数”这两段一定覆盖了整个区间 [l,r]，这两段的最大值分别是 F[l,r] 和 F[r-2^k+1,k]，两者中较大的那个就是整个区间 [l,r] 的最值。因为求的是最大值，所以这两段只要覆盖区间 [l,r] 即可，即使有重叠也没问题。

int ST_query(int l,int r){
    int k=log(r-l+1)/log(2);
    return max(f[l][k],f[r-(1<<k)+1][k]);
}

四、最近公共祖先（LCA）

给定一颗有根树，若节点 z 既是节点 x 的祖先，也是节点 y 的祖先，则称 z 是 x，y 的公共祖先。在 x，y 的所有共公共祖先中，深度最大的一个称为 x，y 的最近公共祖先，记为 LCA(x,y)。

LCA(x,y) 是 x 到根的路径与 y 到根的路径的交汇点，它也是 x 与 y 之间的路径上深度最小的节点。

这里着重介绍树上倍增法求LCA。

树上倍增法是一个很重要的算法。除了求 LCA 之外，它在很多问题中都有广泛应用。设 F[x,k] 表示 x 的 2^k 辈祖先，即从 x 向根节点走 2^k 步到达的节点。特别地，若该节点不存在，则令 F[x,k] = 0. F[x,0] 就是 x 的父节点。除此之外，任意k∈[1,log n]，F[x,k]=F[F[x,k-1],k-1]。

这类似于一个动态规划的过程，“阶段”就是节点的深度。因此，我们可以对树进行广度优先遍历，按照层次顺序，在节点入队之前，计算它在F数组中相应的值。

以上部分是预处理，时间复杂度为O(nlogn)，之后可以多次对不同的 x，y 计算 LCA，每次询问的时间复杂度为 O(logn)。

基于F数组计算 LCA(x,y) 分为以下几步：

设 d[x] 表示 x 的深度。不妨设 d[x]≥d[y]（否则交换 x，y）

用二进制拆分思想，把 x 向上调整到与 y 同一深度。具体来说，就是依次尝试从 x 向上走 k = 2^logn,...,2^1,2^1步，检查到达的节点是否比 y 深。在每次检查中，若是，则令 x=F[x,k]

若此时 x=y，说明已经找到了 LCA，LCA 就等于 y。

用二进制拆分思想，把 x，y 同时向上调整，并保持深度一致且二者不相会。具体来说，就是依次尝试把 x，y 同时向上走 k=2^logn,...,2^1,2^0步，在每次尝试中，若 F[x,k] ≠ F[y,k]（即仍未相会），则令 x = F[x,k]，y = F[y,k]。

此时 x，y 必定只差一步就相会了，它们的父节点 F[x,0] 就是 LCA。

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
 
const int maxn=101000;
int n;
int m;
int s;
int tot;
int head[maxn];
int lg[maxn];
int depth[maxn];
int fa[maxn][32];
 
struct edge{
	int to;
	int from;
	int nxt;
}e[2*maxn];
 
void add(int x,int y){
	tot++;
	e[tot].to=y;
	e[tot].from=x;
	e[tot].nxt=head[x];
	head[x]=tot;
}
 
void dfs(int now,int fath){
	fa[now][0]=fath;
	depth[now]=depth[fath]+1;
	for(int i=1;i<=lg[depth[now]];i++) fa[now][i]=fa[fa[now][i-1]][i-1];
	for(int i=head[now];i;i=e[i].nxt){
		int y=e[i].to;
		if(y==fath) continue;
		dfs(y,now);
	}
}
 
int lca(int x,int y){
	if(depth[x]<depth[y]) swap(x,y);
	while(depth[x]>depth[y]) x=fa[x][lg[depth[x]-depth[y]]-1];
	if(x==y) return x;
	for(int k=lg[depth[x]]-1;k>=0;k--){
		if(fa[x][k]!=fa[y][k]){
			x=fa[x][k];
			y=fa[y][k];
		}
	}
	return fa[x][0];
}
 
int x,y;
 
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<n;i++){
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	for(int i=1;i<=n;i++) lg[i]=lg[i-1]+(1<<lg[i-1]==i);
	dfs(s,0);
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		cout<<lca(x,y)<<endl;
	}
}