倍增（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}len$$
对于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));}}