Skip to main content

倍增

参考资料​

应用​

详见 ST 表

详见 最近公共祖先（LCA）

例题​

洛谷 P3865 【模板】ST 表 && RMQ 问题​

洛谷 P3865 【模板】ST 表 && RMQ 问题

给定一个长度为 NN 的数列，和 MM 次询问，求出每一次询问的区间内数字的最大值。

Code (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）​

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

给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。

Code (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;
}