当前位置：首页 > news >正文

倍增

news 2026/3/27 1:18:43

倍增

定义

倍增是一种与二分相似的算法，但是把二进制摆在了明面上。

大体思路是一步步确定答案的二进制表示的每一位。

简单倍增

例题：洛谷 P2249 【深基13.例1】查找

你说得对，但是这题其实是二分模板题。

首先转化为找到第一个小于 \(q\) 的位置 \(p\)。

因为长度不大于 \(10^6\)，所以答案一定可以用一个二十位二进制数来表示，因为 \(2^{20}>10^6\)

然后我们就尝试从高到低确定这个答案的每一位。

显然对于从低到高第 \(i\) 位，数值是 \(2^{i}\)，其中 \(i\ge 0\)。

那么我们判断，如果 \(2^i\le n\land a_{p_{i}}<q\)，那么说明答案的第 \(i\) 位一定是一。

因为如果这一位不是一，那么就算后面所有的二进制位都是 \(1\)，总和也没有 \(2^{i}\) 大，是更到不了 \(a_{ans}\) 的。

如果 \(a_{p_i}\ge q\)，说明跳太大了，这一位是 \(0\)。

简言之，二分是通过检查 mid 的可行性，而倍增是通过 check 每个二进制位的可行性。

以此类推，直到找到答案为止。

最后要记得特判是否越界。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ljl;
#define FUP(i,x,y) for(int i=(x);i<=(y);++i)
#define FDW(i,x,y) for(int i=(x);i>=(y);--i)
const int N=1e6+5;
int n,q,a[N],x;void Main()
{int p=0;cin>>x;FDW(i,20,0){if((p|(1<<i))<=n&&a[p|(1<<i)]<x)p=p|(1<<i);}if(p<n&&a[p+1]==x)cout<<p+1<<' ';else cout<<"-1 ";return;
}
int main(){ios::sync_with_stdio(0);cin>>n>>q;FUP(i,1,n)cin>>a[i];while(q--)Main();cout<<'\n'; return 0;
}

对于倍增的感性理解

首先我们知道，对于任意一个整数都可以分解成二进制的形式。

那么假设我们开了挂，知道了答案，那么这个答案 \(ans\) 也是由一位位的二进制数表达的。

那么我们就可以尝试跳步子。

第一次跳足够长，如果超出了，就撤回这一步，尝试更小的步子。

如果没超过，就迈出去。

这样迈出去对应 \(1\)，撤回对应 \(0\)，总可以凑成 \(ans\)。

树上倍增

因为倍增的结构相对稳定，那么就可以在多个数据结构上使用，就比如树。

举个例子，LCA！

Luogu P3379 【模板】最近公共祖先（LCA）

那么在树上，我们该怎么维护呢？

首先二分显然不太好搞。因为无法快速求出两点之间的中点。

我们考虑递推。

设 \(f_{i,j}\) 表示从 \(i\) 出发，跳了 \(2^j\) 步所到达的点。

那么显然有 \(f_{i,j}=f_{f_{i,j-1},j-1}\)，即在 \(i\) 上先跳 \(2^{j-1}\) 步，再跳 \(2^{j-1}\) 步的结果。

因为 \(2^j=2^{j-1}+2^{j-1}\)。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5,M=N;
int n,q,s,cnt_e,ehead[N],fa[N][25],dep[N];
struct E{int to,pre;
}e[M<<1];
void adde(int from,int to)
{e[++cnt_e].to=to;e[cnt_e].pre=ehead[from];ehead[from]=cnt_e;return;
}
void dfs(int u,int uf)
{fa[u][0]=uf;dep[u]=dep[uf]+1;for(int i=1;i<=20;++i)fa[u][i]=fa[fa[u][i-1]][i-1];for(int i=ehead[u];i;i=e[i].pre){int v=e[i].to;if(v==uf)continue;dfs(v,u);}return;
}
int getlca(int x,int y)
{if(x==y)return x;if(dep[x]<dep[y])swap(x,y);for(int i=20;i>=0;--i)if(dep[x]-(1<<i)>=dep[y])x=fa[x][i];if(x==y)return x;for(int i=20;i>=0;--i){if(fa[x][i]!=0&&fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];}return fa[x][0];
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>q>>s;for(int i=1,u,v;i<n;++i){cin>>u>>v;adde(u,v);adde(v,u);}dfs(s,0);while(q--){int u,v;cin>>u>>v;cout<<getlca(u,v)<<'\n';}return 0;
}

同理，树上倍增不仅可以维护祖先，还可以顺便维护一些链信息。

比如用 \(m_{i,j}\) 表示从 \(i\) 出发，跳 \(2^j\) 步的过程中，所有节点的权值最大值。

那么状态转移方程也大差不差：\(m_{i,j}=\max\left\{m_{i,j-1},m_{f_{i,{j-1}},j-1}\right\}\)