C++ 倍增算法 |21xrx.com

C++ 倍增算法

2023-07-13 11:15:47 深夜i -- --

C++ 倍增算法数组二分查找动态规划

C++ 倍增算法是一种经典的算法，它常用于解决树上最近公共祖先（LCA）问题。该算法的核心思想是将一个大问题分解成多个小问题，再通过多次计算得出最终结果。在本文中，我们将详细介绍C++ 倍增算法的基本原理和实现方法。

一、基本原理

C++ 倍增算法的基本原理是利用二进制拆分来简化计算。对于一个节点u，我们可以通过二进制数a[0],a[1],…,a[k]来表示它的深度，其中a[0]=u，a[k]是根节点，a[i]表示u到它的第2^i个祖先的距离。例如，若k=3，则a=u，其中v为u的父节点，w为v的父节点，x为w的父节点。

为了方便计算距离，我们可以利用动态规划的思想，预处理出每个节点u到其某个祖先节点j的距离，即dis[u][j]。根据倍增的思想，我们可以通过dis数组来计算u和v的LCA。

具体来说，我们假设u和v的深度不相同，不妨设u的深度大于v的深度，则可以将u作为基准点，将v一直向上跳，直到与u在同一深度为止。此处可以利用二进制拆分的思想，将v一次跳2^i个祖先节点，直到跳到与u同一深度为止。然后再分别向上跳，直到两者找到一个相同的祖先节点x。这样，x就是u和v的LCA。

二、实现方法

C++ 倍增算法的实现过程中，需要进行以下几个步骤：

1.预处理出每个节点u到其某个祖先节点j的距离dis[u][j]。

2.根据输入的u和v，计算它们的深度d[u]和d[v]。

3.利用二进制拆分来计算u和v的LCA。具体来说，假设d[u] > d[v]，则先让v向上跳2^i步，直到与u的深度相等。然后，两者同时向上跳，找到它们的LCA即可。

下面是一个C++代码的例子，用来实现树上LCA问题的倍增算法：

int dis[MAXN][MAXLOG]; // dis[i][j] 表示结点 i 距离它的第 2^j 个祖先节点的距离

int d[MAXN]; // d[i] 表示结点 i 的深度

int lg2[MAXN]; // lg2[i] 表示 log2(i) 的值

int n, m;

vector G[MAXN];

void dfs(int u, int p) {

d[u] = d[p] + 1;

dis[u][0] = p;

for(int i = 1; i <= lg2[d[u]]; i++) {

dis[u][i] = dis[dis[u][i-1]][i-1] + 1;

}

for(auto v : G[u]) {

if(v == p) continue;

dfs(v, u);

}

int lca(int u, int v) {

if(d[u] < d[v]) swap(u, v);

int k = d[u] - d[v];

for(int i = lg2[k]; i >= 0; i--) {

if(k & (1 << i)) u = dis[u][i];

}

if(u == v) return u;

for(int i = lg2[d[u]]; i >= 0; i--) {

if(dis[u][i] != dis[v][i]) {

u = dis[u][i];

v = dis[v][i];

}

return dis[u][0];

}

int main() {

scanf("%d%d", &n, &m);

for(int i = 1; i < n; i++) {

int u, v;

scanf("%d%d", &u, &v);

G[u].push_back(v);

G[v].push_back(u);

}

for(int i = 1; i <= n; i++) lg2[i] = lg2[i/2] + 1;

dfs(1, 0);

while(m--) {

int u, v;

scanf("%d%d", &u, &v);

printf("%d\n", lca(u, v));

}

return 0;

}

通过上述代码，我们可以很方便地解决树上LCA问题。但需要注意的是，C++倍增算法存在时间复杂度为O(nlogn)的空间复杂度问题，因此不能用于解决大型数据量的问题。对于这种情况，我们需要采用更为高效的算法，例如Tarjan算法或ST表算法。

上一篇: idea打包java可执行jar包

下一篇: C++字符串占多少空间？

评论区

()

相似文章