倍增(ST表与LCA)

倍增(ST表与LCA)简介倍增思想常见问题 以及算法模板 倍增 lca

大家好,欢迎来到IT知识分享网。

倍增(ST表与LCA)

什么是倍增?

倍增,就是成倍增长。指我们进行递推时,如果状态空间很大,通常线性递推无法满足时空复杂度要求,那么可以通过成倍增长的方式,只递推状态空间中 2 的整数次幂位置的值为代表将复杂度优化成log级别。

为什么倍增是正确的?

我们通过任意整数可以表示成若干个 2 的整数次幂的和这一性质来表示任意一个区间长度。例如:5 = 101 = 2 ^ 2 + 2 ^ 0;

倍增思想应用于哪些问题?

倍增最常见应用就是求解 RMQ问题和LCA问题

ST表

什么是ST表?

ST表是基于倍增思想解决可重复贡献问题的数据结构。

其中ST表最广泛的应用就是解决RMQ(区间最值问题): 给定一个包含n个数的数组,以及m次询问,每次询问给出一个区间[l, r],需要我门输出区间中的最小/大值。

基于倍增的思想,ST表可以实现 O(NlogN) 下进行预处理,并在O(1) 时间内回答每个询问。但是,ST表并不支持修改操作。

如何维护ST表?

我们定义数组f[i][j]表示下标从 i 开始长度为 2 ^ j 的区间中最小/大值。根据倍增的思想不难想出:

f[i][j] = max( f[i][j – 1] , f[i + (1 << (j – 1))][j – 1])

并且可以通过O(NlogN)的时间来预处理出所有f[i][j]的值。

在这里插入图片描述

对于每次询问[l, r],我们先计算出区间长度 len = r – l + 1。再对区间长度len取对数:
K = log ⁡ 2 l e n K = \log_2 len K=log2len
对于log函数的值我们可以通过O(N)的时间预处理出来。

再将区间分成 [l , l + 2 ^ k – 1][r – 2 ^ k + 1, r], 由于k 是整数可能存在精度误差,但是 2 ^ k + 1 > len ,这样就可以避免整数类型带来的误差。

在这里插入图片描述

练习:

ST表模板题:

#include <iostream> #include <algorithm> using namespace std; const int N = 1e5 + 10; int a[N], stmax[N][20], mn[N]; int n, q; void init() { mn[0] = -1; for (int i = 1; i <= n; i++) { mn[i] = ((i & (i - 1))== 0) ? mn[i - 1] + 1 : mn[i - 1]; stmax[i][0] = a[i]; } for (int j = 1; j <= mn[n]; j++) { for (int i = 1; i + (1 << j) - 1 <= n; i++) { stmax[i][j] = max(stmax[i][j - 1], stmax[i + (1 << (j - 1))][j - 1]); } } } int query(int l, int r) { int k = mn[r - l + 1]; return max(stmax[l][k], stmax[r - (1 << k) + 1][k]); } int main() { scanf("%d%d", &n, &q); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } init(); for (int i = 0; i < q; i++) { int l, r; scanf("%d%d", &l, &r); printf("%d\n", query(l, r)); } return 0; } 

LCA(最近公共祖先)

什么是LCA(最近公共祖先)?

祖先:指的是一个结点向根节点遍历的路径上经过的所有结点(包括该节点本省身)。

LCA指的是在一个有N个点的有根树中,给出m个询问,每个询问包含两个树上结点,需回答距离这两个结点最近的(深度最深的结点)。

在这里插入图片描述

如何解决LCA问题?

LCA问题的解法有很多:向上标记法,倍增法, tarjan等等,今天要介绍的是最简单且最常用的倍增法。

倍增法LCA基于倍增思想,可以通过O(NlogN)预处理,每次查询的时间复杂度为O(logN)

倍增法求解LCA问题具体如何实现?

我们定义fa[i][j],表示从i号结点开始向上走2 ^ j (0 <= j <= logN)步能够走到的结点, depth[i] 表示i号点的深度。

同样是倍增的思想,我们不难推出:

当 j == 0 时fa[i][j]表示的是i结点的父亲结点

当 j > 0 时 fa[i][j] = fa[ fa[i][j – 1] ][j – 1];

在这里插入图片描述

对于每次询问求解两个点的LCA可以分为一下步骤:

(1)、先将两个点向上跳到同一层(深度相同): 例如 depth[A] = 7, depth[B] = 4, 则应该先将A点向上跳

​ t = 7 – 4 = 3 = 011(B) 步[采用二进制并凑法] 跳到与B同一层;

(2)、再将这两个点同时向上跳直到跳到A, B两点的LCA的下一层为止。(为什么不直接跳到LCA?,因为j >= 0 时 2的整数次幂最小值为1);

(3)、此时的fa[A][0]即是A,B两点的LCA;

练习

LCA模板题

#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #define int long long using namespace std; const int N = 1e6 + 10; int n, root, m; int h[N], e[N], ne[N], idx; int f[N][40], depth[N], q[N]; void add(int a,int b){ e[idx] = b; ne[idx] = h[a]; h[a] = idx ++; return ; } void dfs(){ memset(depth, 0x7f, sizeof(depth)); depth[0] = 0; depth[root] = 1; int hh = 0, tt = 0; q[0] = root; while(hh <= tt){ int t = q[hh ++]; for(int i = h[t]; i != -1; i = ne[i]){ int j = e[i]; if(depth[j] > (depth[t] + 1)){ depth[j] = depth[t] + 1; q[++ tt] = j; f[j][0] = t; for(int k = 1; k <= 19; k ++){ f[j][k] = f[f[j][k - 1]][k - 1]; } } } } } int lca(int a, int b){ if(depth[a] < depth[b]){ swap(a, b); } for(int k = 19; k >= 0; k --){ if(depth[f[a][k]] >= depth[b]){ a = f[a][k]; } } if(a == b){ return a; } for(int k = 19; k >= 0; k --){ if(f[a][k] != f[b][k]){ a = f[a][k]; b = f[b][k]; } } return f[a][0]; } signed main(){ memset(h, -1, sizeof(h)); scanf("%lld%lld%lld",&n, &m, &root); for(int i = 0; i < n - 1; i ++){ int a, b; scanf("%lld%lld",&a, &b); add(a, b); add(b, a); } dfs(); for(int i = 0; i < m ; i ++){ int a, b; scanf("%lld%lld",&a, &b); printf("%lld\n",lca(a, b)); } } 

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/158257.html

(0)
上一篇 2025-01-25 15:20
下一篇 2025-01-25 15:25

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注微信