倍增简介

倍增，顾名思义就是成倍总价。若问题状态的空间特别大，则一步步地推的算法复杂度太高，可以通过倍增的思想，只考察2的整数次幂的位置，快速缩小求解范围，直到找到解。

倍增原理

任意整数可以被表示成若干个$2$的次幂项之和。例如整数$5$，其二进制表示为$(101)_2$，该二进制数从右往左第$0$、$2$位均为$1$，则$5=2^2+2^0$；整数$26$，其二进制表示为$(11010)_2$，该二进制数从右往左第$1$、$3$、$4$位均为$1$，则$26=2^4+2^3+2^1$。也就是说2的次幂项可以被拼成任意需要的值。

倍增应用

ST表（稀疏表）

树上倍增

树上倍增可以解决很多问题，最典型的是求解$LCA$问题。

原理

假设现在我用$f[i][j]$表示$i$的$2^j$辈祖先，即节点$i$向根节点走$2^j$步到达的节点，据此建立ST表。下面我要求解节点$u$与节点$v$的$LCA$，首先判断点$u$和点$v$的深度，将深度大的点向上移动，根据倍增原理，将$j$从大到小枚举，使点$u$与点$v$在同一深度。然后让两个点同时向上移动，如果它们经过一段倍增距离到达了一个相同的点，说明这两个点正好跳到$LCA$上或者是跳过了，为了保证结果的正确性，我们需要放弃这一次跳跃，最终只让这两个点跳到$LCA$的左右儿子上，输出其中一个节点的父亲即$f[u][0]$即可。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int deep[1000001],grand[500001][101],g[1000001],n,m,s,next,N;
struct Node
{
	int to,next;
}e[1000001];
void add(int x,int y)
{
	e[++next].to=y;
	e[next].next=g[x];
	g[x]=next;
}
void dfs(int x)
{
	for(int i=1;i<=N;i++)
	{
		grand[x][i]=grand[grand[x][i-1]][i-1];
	}
	for(int k=g[x];k;k=e[k].next)
	{
		if(e[k].to!=grand[x][0])
		{
			deep[e[k].to]=deep[x]+1;
			grand[e[k].to][0]=x;
			dfs(e[k].to);
		}
	}
	return;
}
int lca(int a,int b)
{
	if(deep[a]>deep[b])
	{
		swap(a,b);
	}
	for(int i=N;i>=0;i--)
	{
		if(deep[a]<deep[b]&&deep[grand[b][i]]>=deep[a])
		{
			b=grand[b][i];
		}
	}
	if(a==b)	return a;
	for(int i=N;i>=0;i--)
	{
		if(grand[a][i]!=grand[b][i])
		{
			a=grand[a][i];
			b=grand[b][i];
		}
	}
	return grand[a][0];
}
int main()
{
	cin>>n>>m>>s;
	for(int i=1;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	N=floor(log2(n+0.0)/log2(2.0));
	deep[s]=1;
	dfs(s);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		cout<<lca(x,y)<<endl;
	}
	return 0;
}