倍增是根据已经得到的信息，将考虑的范围扩大一倍，从而加速操作的一种思想。

快速幂

快速幂使用了倍增的思想。见文章数论模板。

树上倍增

最近公共祖先

树上倍增可求最近公共祖先（LCA）。个人约定：一个点向根节点方向移动称为“向上跳”。

对于一个有 $n$ 个节点的有根树，我们设 $f(i,j)$ 表示 $j$ 点向上跳 $2^i$ 所到的点。例如， $f(0,j)$ 就表示 $j$ 点的父亲。

我们通过对整个树进行 dfs 遍历，预先处理出 $f(0,j)$ ，其中 $j\in [1,n]$ 。然后我们可以通过预处理的值求出所有的 $f(i,j)$ ，其中 $0\le i\le \log_2n，j\in[1,n]$ 。状态转移方程：

f(i,j)=f(i-1,f(i-1,j))

这个方程表示， $j$ 点先向上跳 $2^{i-1}$ 个点，再向上跳 $2^{i-1}$ 个点，效果等价于向上跳 $2^{i}$ 个点。

这个预处理时间复杂度为 $O(n\log n)$ 。

求 LCA，首先将两个点深度平衡一下，再同步向上跳。每个点的深度也可以在前面 dfs 遍历时求得。最坏时间复杂度为 $O(n\log n)$ 。

代码如下（为 P3379 【模板】最近公共祖先（LCA）的代码）：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	const int N=500000+10,Log=20;
	struct edge{int nxt,to;}e[N*2];
	int n,Root,Q,cnt=0,d[N],head[N],f[Log+5][N];
	void add(int a,int b){e[++cnt]=(edge){head[a],b};head[a]=cnt;}
	void dfs(int root)
	{
		for(int i=head[root];i;i=e[i].nxt)
		{
			int son=e[i].to;
			if(f[0][root]==son) continue;
			d[son]=d[root]+1;f[0][son]=root;dfs(son);
		}
	}
	void init()
	{
		d[Root]=1;dfs(Root);f[0][Root]=Root;
		for(int i=1;i<=Log;i++)
			for(int j=1;j<=n;j++)
				f[i][j]=f[i-1][f[i-1][j]];
	}
	int LCA(int x,int y)
	{
		if(d[x]<d[y]) swap(x,y);//我们规定 x 的深度大。
		for(int i=Log;i>=0;i--) if(d[f[i][x]]>=d[y]) x=f[i][x];
		if(x==y) return x;
		for(int i=Log;i>=0;i--)//注意倒序枚举！
			if(f[i][x]!=f[i][y]) 
				x=f[i][x],y=f[i][y];
		return f[0][x];//这时它的父亲就是 LCA。
	}
	void yzmain()
	{
		int t1,t2;
		scanf("%d%d%d",&n,&Q,&Root);
		for(int i=1;i<=n-1;i++)
			scanf("%d%d",&t1,&t2),add(t1,t2),add(t2,t1);
		init();
		for(int i=1;i<=Q;i++)
			scanf("%d%d",&t1,&t2),
			printf("%d\n",LCA(t1,t2));
		return;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}

ST 表

它是解决 RMQ 问题（区间最值问题）的一种强有力的工具。它可以做到 $O(nlogn)$ 预处理， $O(1)$ 查询最值。ST 表是利用的是倍增的思想。

模板（P3865 【模板】ST 表）：

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	const int V=17,N=200000+5;
	int st[V+5][N],b[N],n,m;
	void yzmain()
	{
		int x,y,len;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
			scanf("%d",&st[0][i]);
		for(int i=1;i<=V;i++)
			for(int j=1;j<=n;j++)
				st[i][j]=max(st[i-1][j],st[i-1][j+(1<<(i-1))]);//区间最大max 区间最小min 
				/*     f[i-1][j]     f[i-1][j+2^(i-1)]
				   |----------------|----------------|
					     	total: f[i][j]               */
		for(int i=1;i<=V;i++)//快速得到 log_2 N
			b[1<<i]=1;
		for(int i=1;i<=n;i++)
			b[i]+=b[i-1];
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d",&x,&y);
			len=y-x+1;
			printf("%d\n",max(st[b[len]][x],st[b[len]][y+1-(1<<b[len])]));
		}
		return;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}

模板题 2：https://www.luogu.com.cn/problem/P1816。把输出格式以及 max 改一下即可。

本文作者：Yurchiu

本文链接：https://yz-hs.github.io/725d61041676/

版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。

OI 数论倍增树 ST 表 LCA

最后更新：2023-08-21, 23:18:21

By Yurchiu.

随机文章回味旧文

博客信息

文章数目

158