倍增
参考资料
应用
详见 ST 表
详见 最近公共祖先（LCA）
例题
洛谷 P3865 【模板】ST 表 && RMQ 问题
给定一个长度为 的数列，和 次询问，求出每一次询问的区间内数字的最大值。
代码（1）
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=100005;
ll a[N][25];
void init(int n)
{
for(int j=1;j<=__lg(n);j++)
{
for(int i=1;i<=n-(1<<j)+1;i++)
{
a[i][j]=max(a[i][j-1],a[i+(1<<(j-1))][j-1]);
}
}
}
ll query(int l,int r)
{
int k=__lg(r-l+1);
return max(a[l][k],a[r-(1<<k)+1][k]);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i][0];
}
init(n);
while(m--)
{
int l,r;
cin>>l>>r;
cout<<query(l,r)<<'\n';
}
return 0;
}
洛谷 P3379 【模板】最近公共祖先（LCA）
给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。
代码（2）
- 倍增
- 树链剖分
#include <bits/stdc++.h>
using namespace std;
const int N=500005;
int a[N][25],dep[N];
vector<int> G[N];
bool vis[N];
void dfs(int u,int fa)
{
a[u][0]=fa;
for(int i=1;i<=20;i++)a[u][i]=a[a[u][i-1]][i-1];
dep[u]=dep[fa]+1;
for(auto v:G[u])
{
if(v!=fa)dfs(v,u);
}
}
int lca(int u,int v)
{
if(dep[u]<dep[v])swap(u,v);
for(int i=20;i>=0;i--)
{
if(dep[a[u][i]]>=dep[v])u=a[u][i];
}
if(u==v)return u;
for(int i=20;i>=0;i--)
{
if(a[u][i]!=a[v][i])
{
u=a[u][i];
v=a[v][i];
}
}
return a[u][0];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m,s;
cin>>n>>m>>s;
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs(s,0);
while(m--)
{
int u,v;
cin>>u>>v;
cout<<lca(u,v)<<'\n';
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int N=500005;
vector<int> G[N];
int fa[N],dep[N],siz[N],son[N];
int top[N],dfn[N],rnk[N],out[N];
int cnt=0;
void dfs1(int u)
{
siz[u]=1;
dep[u]=dep[fa[u]]+1;
for(auto v:G[u])
{
if(v==fa[u])continue;
fa[v]=u;
dfs1(v);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])son[u]=v;
}
}
void dfs2(int u,int e)
{
top[u]=e;
dfn[u]=++cnt;
rnk[cnt]=u;
if(son[u])dfs2(son[u],e);
for(auto v:G[u])
{
if(v==fa[u]||v==son[u])continue;
dfs2(v,v);
}
out[u]=cnt;
}
int lca(int u,int v)
{
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]])swap(u,v);
u=fa[top[u]];
}
return dep[u]<dep[v]?u:v;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m,s;
cin>>n>>m>>s;
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs1(s);
dfs2(s,s);
while(m--)
{
int u,v;
cin>>u>>v;
cout<<lca(u,v)<<'\n';
}
return 0;
}