倍增（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]$的值

这是一道 ST 表经典题——静态区间最大值

#include 
#include 
using namespace std;
const int N = 1e6+10; 
int a[N],f[N][20],mn[N];
int n,m;
void init(){
	mn[0]=-1;	 
	for(int i=1;i<=n;i++){//对n取对数 
		mn[i]=((i&(i-1))==0)?mn[i-1]+1:mn[i-1];//i&(i-1)==0说明i是2的幂次 
		f[i][0]=a[i];
	}
//	否则枚举区间时间复杂度是O(n^2),但在枚举区间长度时,将线性枚举转变为
//	对 对数区间的枚举 
//mn数组就是预处理的取对数的值，log_2 len,慢,会被卡掉，log_10 len/ log_10 2
	for(int j=1;j<=mn[n];j++){//j<=mn[n]一般小于20，2^20=1e6 枚举区间长度 
		for(int i=1;i+(1<<j)-1<=n;i++){//枚举区间的起始下标 
			f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
		}
	}
}
int query(int l,int r){
	int len=r-l+1;//求出区间长度 
	int k=mn[len];//对区间长度取对数 2^k<=len,  2^{k+1} > len
//	log(len)/log(2) n一大就容易超时 
	return max(f[l][k],f[r-(1<<k)+1][k]);//???就是先将大区间分成两个区间	
}
int main() {//好离谱，疯狂卡输入输出，搞了输入卡输出
//	ios::sync_with_stdio(false);
//	cin.tie(0);cout.tie(0);
//	cin>>n>>m;
	scanf("%d%d",&n,&m);
//	n=read(),m=read();
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);//a[i]=read();
	init();
	int l,r;
	while(m--){
//		cin>>l>>r;
		scanf("%d%d",&l,&r);
//		l=read(),r=read();
printf("%d\n",query(l,r));
//		cout<
//		if(m)cout<
	} 
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

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];//注意 j 是指 2^j 步

对于每次询问求解两个点的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；
最近的公共祖先（板子）

#include
#include
#include
#include
#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));
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

LCA离线查询

多次查询无向图两点之间最小距离

暂且不会

解答博客1
解答博客2