倍增法（英语：binary lifting），顾名思义就是「成倍增长」．我们在进行递推时，如果状态空间很大，通常的线性递推无法满足时间与空间复杂度的要求，那么我们可以通过成倍增长的方式，只递推状态空间中在 𝑘 的整数次幂位置上的值作为代表．当需要其他位置上的值时，我们通过「任意整数可以表示成若干个 𝑘 的次幂项的和」这一性质，使用之前求出的代表值拼成所需的值．所以使用倍增算法也要求我们递推的问题的状态空间关于 𝑘的次幂具有可划分性．通常情况下 𝑘 取 2 ．

这个方法在很多算法中均有应用，其中最常用的是 RMQ 问题和求 LCA（最近公共祖先）．

LCA模板

最近公共祖先简称 LCA（Lowest Common Ancestor）．两个节点的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个． 为了方便，我们记某点集 𝑆 ={𝑣1,𝑣2,…,𝑣𝑛}的最近公共祖先为 LCA(𝑣1,𝑣2,…,𝑣𝑛) 或 LCA(𝑆)

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 2e5 + 5;
const int LOG = 20;

vector<int> adj[MAXN];
int fa[MAXN][LOG];
int depth[MAXN];

void dfs(int u,int parent)
{
	fa[u][0] = parent;
	for(int v: adj[u])
	{
		if(v == parent) continue;
		depth[v] = depth[u] + 1;
		dfs(v,u);
	}
}
void preprocess(int root,int n)
{
	depth[root] = 0;
	dfs(root,-1);
	
	for(int i = 1;i < LOG; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			if(fa[j][i-1] == -1) fa[j][i] = -1;
			else fa[j][i] = fa[fa[j][i-1]][i-1];
		}
	}
}
int lca(int u,int v)
{
	if(depth[u] < depth[v]) swap(u,v);
	int diff = depth[u] - depth[v];
	
	for(int i = LOG-1; i >= 0; i--)
	{
		if(k&(1<<i)) u =fa[u][i];
	}
	if(u==v) return u;
	for(int i = LOG-1; i >= 0; i--)
	{
		if(fa[u][i] != -1 && fa[u][i] != fa[v][i])
		{
			u = fa[u][i];
			v = fa[v][i];
		}
	}
	return fa[u][0];
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n,q;
	cin >> n >> q;
	for(int i = 1; i < n; i++)
	{
		int u,v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	
	preprocess(1,n);
}

倍增法+线性基

题目概述

A 国有 n 座城市，通过 n-1 条道路连接形成一棵树，保证任意两座城市之间路径唯一。每个城市 i 有一个非负整数 $G_i$，表示该城市的“幸运值”。

有 q 位旅行者，每位旅行者选择从城市 x 出发，沿树上从 x 到 y 的唯一简单路径行进，到达城市 y 离开。在经过路径上的每一座城市时，可以选择是否“拍照”，若拍照则会获得该城市的幸运值。

幸运值的累计方式不是加法，而是对所有被选择的城市幸运值进行按位异或（xor）运算。并且可以自由选择路径上的任意子集（不要求连续，也不要求全部选择）。

对于每个询问 $(x, y)$，需要在路径 $x \to y$上选取若干个城市，使它们的幸运值异或结果最大，并输出这个最大值。

题解

这道题是一个线性基和倍增算法的板子题。由于城市之间路径唯一，所以连成一棵树。然后对于两个点的唯一路径必然使用lca去解决。这道题要求记录幸运值的方法是最大异或和，于是想到了线性基。当我们预处理倍增算法的时候，利用倍增的方法插入从某点运动$2^i-1$线性基，这样就可以在询问时候极大优化。时间复杂度是 $O(n⋅logn⋅60^2+q⋅logn⋅60^2)$

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
const int MAXN = 2e4+5;
const int LOG = 20;

vector<int> adj[MAXN];

int n, q;
int depth[MAXN];
int fa[MAXN][LOG]; // 定义一点向上2^i步之后的点 

ll p[MAXN][LOG][62]; // 定义从该点的前一个段到2^i步之后的点的幸运值的线性基 
ll G[MAXN];

void dfs(int u,int parent)
{
	fa[u][0] = parent;
	depth[u] = depth[parent] + 1;
	for(int v:adj[u])
	{
		if(v == parent) continue;
		
		dfs(v,u);
	}
}

void insert_bas(ll b[], ll x)
{
 	 for(int i = 61; i >= 0; i--)
	  {
	  	if(((x >> i) & 1) == 0) continue;
	  	
	  	if(!b[i])
	  	{
	  		b[i] = x;
	  		break;
	    }
	    x ^= b[i];
	  }	
} // 线性基模板 

void merge_bas(ll a[], ll b[])
{
	for(int i = 61; i >= 0; i--)
	{
		if(b[i])
			insert_bas(a,b[i]);	
	}
} // 合并线性基 

void preprocess(int root,int n)
{
	
	dfs(root,0); // dfs来获得所有点的1步的时候的节点 
	
	for(int u = 1; u <= n; u++)
	{
		insert_bas(p[u][0], G[u]);
	}  // 记录本身的幸运值 
	
	for(int k = 1; k < LOG; k++)
	{
		for(int u = 1; u <= n; u++)
		{
			int mid = fa[u][k-1];
			fa[u][k] = fa[mid][k-1]; // 倍增递推 
			
			memcpy(p[u][k], p[u][k-1], sizeof(p[u][k-1]));
			merge_bas(p[u][k],p[mid][k-1]);  // 类似倍增递推的线性基插入 
		}
	}
}

ll query(int u,int v)
{
	ll res[62] = {0};
	
	if(depth[u] < depth[v]) swap(u,v);
	int diff = depth[u] - depth[v];
	
	for(int k = LOG - 1; k >= 0; k--)
	{
		if(diff & (1ll << k))
		{
			merge_bas(res,p[u][k]);
			u = fa[u][k];
			
		}
	}  // 将更远的点移动到相同位置，并且获取这一段线性基 
	
	if(u == v)
	{
		merge_bas(res,p[u][0]);
		ll ans = 0;
		for(int i = 61; i >= 0; i--)
		{
			ans = max(ans, ans ^ res[i]);
		}
		return ans;
	}  // 特判 如果已经相等的时候 直接输出结果 
	
	for(int k = LOG - 1; k >= 0; k--)
	{
		if(fa[u][k] != fa[v][k])
		{
			merge_bas(res,p[u][k]);
			merge_bas(res,p[v][k]);
			u = fa[u][k];
			v = fa[v][k];
		}
	}
	merge_bas(res, p[u][0]);
	merge_bas(res, p[v][0]);
	merge_bas(res, p[fa[u][0]][0]);
	
	ll ans = 0;
	for(int i = 61; i >= 0; i--)
	{
		ans = max(ans, ans ^ res[i]);
	}
	return ans;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	
	cin >> n >> q;
	
	for(int i = 1; i <= n; i++) cin >> G[i];
	for(int i = 1; i < n; i++)
	{
		int u,v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	memset(fa, 0, sizeof(fa));
	memset(p, 0, sizeof(p));	
	preprocess(1,n); // 初始化+预处理 
	
	while(q--)
	{
		int x, y;
		cin >> x >> y;
		cout << query(x,y) << '\n';
	}
}

倍增法套用

题目概述

给定 $n$ 个区间 $[l_i, r_i]$，以及 $m$ 个询问 $[x, y]$。

对于每个询问，需要从给定区间中选择若干个区间，使它们的并集能够完整覆盖区间 [x,y]，且所选区间数量最少。

若存在一组区间，其并集满足：$$[x, y] \subseteq \bigcup_{[l_j, r_j] \in S} [l_j, r_j]$$

则输出最小所需区间数量；否则输出 $-1$。

需要注意，区间覆盖是对连续实数范围的覆盖，因此所选区间的并集必须在 $[x, y]$ 上无间断。

题解

这道题先获取每个点的能跳越到的最远距离，利用贪心的方法获得。然后构建倍增预处理，判断每个区间的left可以跳到right。

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 5e5 + 5;
const int LOG = 21;

int f[MAXN];
int go[MAXN][LOG];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < n; i++)
	{
		int l, r;
		cin >> l >> r;
		f[l] = max(f[l],r);
	}
	for(int i = 1; i < MAXN; i++)
	{
		f[i] = max(f[i],f[i-1]);
	}
	for(int i = 0; i < MAXN; i++)
	{
		go[i][0] = f[i];
	}
	for(int k = 1; k < LOG; k++)
	{
		for(int i = 0; i < MAXN; i++)
		{
			go[i][k] = go[go[i][k-1]][k-1];
		}
	}
	while(m--)
	{
		int x, y;
		cin >> x >> y;
		
		int ans = 0;
		int cur = x;
		for(int k = LOG - 1; k >= 0 ; k--)
		{
			if(go[cur][k] < y)
			{
				ans += (1 << k);
				cur = go[cur][k];
			}
		}
		if(go[cur][0] >= y)
		{
			ans++;
			cout << ans << "\n";
		}
		else{
			cout << -1 << endl;
		}
	}
}