倍增法（binary lifting），顾名思义就是翻倍。它能够使线性的处理转化为对数级的处理，大大地优化时间复杂度。
当线性递推无法满足时空复杂度要求，则通过成倍增长的方式，只递推状态空间中2的整数次幂位置的值，将复杂度优化为log级别
应用
RMQ问题
Range Maximum/Minimum Query 区间最大（最小）值
给定n个数，有m个询问，对于每个询问，你需要回答区间[l,r]中的最大/小值。
ST表
ST表是基于倍增思想解决可重复贡献问题的数据结构。
广泛应用于解决RMQ问题。
基于倍增思想，ST表可以做到 O(n log n) 预处理，O(1) 回答每个询问。但是不支持修改操作。
tip:与运算
属于位运算
a & b
即把a和b拆成二进制，对应每一个二进制位，只有1&1==1，否则为0
eg：
| D |
5 & 6 |
| B |
101 & 110 |
| ans |
100 |
判断i是否为2的幂
i&(i-1)==0 –> true
i&(i-1)==0 –> false
explanation:
如果一个数x是2的幂,一定是100000…0的形式
x-1变成01111…1,按位与则=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
47
| #include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],stmax[N][20],lg2[N];
int n,q;
void init()
{
lg2[0]=-1;
for(int i=1;i<=n;++i)
{
lg2[i]=((i&(i-1))==0)?lg2[i-1]+1:lg2[i-1];
stmax[i][0]=a[i];
}
for(int j=1;j<=lg2[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=lg2[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问题
（树上最近公共祖先）
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
|
#include <bits/stdc++.h>
using namespace std;
int n,m,fa[1001],dis[1001];
vector<int> e[1001];
inline void dfs(int x)
{
for(auto y:e[x])
{
dis[y]=dis[x]+1;
dfs(y);
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
e[x].push_back(y);
fa[y]=x;
}
memset(dis,0,sizeof(dis));
dfs(1);
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
if(dis[x]<dis[y]) swap(x,y);
int z=dis[x]-dis[y];
for(int j=1;j<=z;j++)
{
x=fa[x];
}
while(x!=y)
{
x=fa[x];
y=fa[y];
}
printf("%d\n",x);
}
}
|
倍增优化
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
|
#include <bits/stdc++.h>
using namespace std;
int n,m,s,fa[500010][22],dis[500010],vis[500010];
vector<int> e[500010];
inline void dfs(int x,int f)
{
for(auto y:e[x])
{
if(y==f) continue;
dis[y]=dis[x]+1;
fa[y][0]=x;
dfs(y,x);
}
}
int main()
{
scanf("%d",&n);
scanf("%d",&m);
scanf("%d",&s);
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
e[x].push_back(y);
e[y].push_back(x);
}
memset(dis,0,sizeof(dis));
dfs(s,0);
for(int i=1;i<=21;i++)
{
for(int j=1;j<=n;j++)
{
if(fa[j][i-1])
{
fa[j][i]=fa[fa[j][i-1]][i-1];
}
}
}
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
if(dis[x]<dis[y]) swap(x,y);
int z=dis[x]-dis[y];
for(int j=0;j<=21 && z;j++,z/=2)
{
if(z & 1)
{
x=fa[x][j];
}
}
if(x==y)
{
printf("%d\n",x);
continue;
}
for(int j=21;j>=0;j--)
{
if(fa[x][j]!=fa[y][j])
{
x=fa[x][j];
y=fa[y][j];
}
}
printf("%d\n",fa[x][0]);
}
}
|
紧急集合/聚会
三点找lca，两两组合找lca
若lca1=lca2=lca3，lca=lca1=lca2=lca3
若lca1=lca2!=lca3,lca=lca3
不存在lca1!=lca2!=lca3的情况
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
| #include <bits/stdc++.h>
using namespace std;
const int N = 5e5+10;
int n,m,s,fa[N][22],dis[N],vis[N];
vector<int> e[N];
inline void dfs(int x,int f)
{
for(auto y:e[x])
{
if(y==f) continue;
dis[y]=dis[x]+1;
fa[y][0]=x;
dfs(y,x);
}
}
int lca(int x,int y)
{
if(dis[x]<dis[y]) swap(x,y);
int z=dis[x]-dis[y];
for(int j=0;j<=21 && z;j++,z/=2)
{
if(z & 1)
{
x=fa[x][j];
}
}
if(x==y)
{
return x;
}
for(int j=21;j>=0;j--)
{
if(fa[x][j]!=fa[y][j])
{
x=fa[x][j];
y=fa[y][j];
}
}
return fa[x][0];
}
int main()
{
scanf("%d",&n);
scanf("%d",&m);
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
e[x].push_back(y);
e[y].push_back(x);
}
memset(dis,0,sizeof(dis));
dfs(1,0);
for(int i=1;i<=21;i++)
{
for(int j=1;j<=n;j++)
{
if(fa[j][i-1])
{
fa[j][i]=fa[fa[j][i-1]][i-1];
}
}
}
while(m--)
{
int ans[5];
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
ans[1]=lca(x,y);
ans[2]=lca(z,y);
ans[3]=lca(x,z);
if(ans[1]==ans[2] && ans[2]==ans[3])
{
printf("%d %d\n",ans[1],dis[x]+dis[y]+dis[z]-3*dis[ans[1]]);
continue;
}
else if(ans[1]==ans[2] && ans[1]!=ans[3])
{
printf("%d %d\n",ans[3],dis[x]+dis[y]+dis[z]-dis[ans[3]]-2*dis[ans[1]]);
continue;
}
else if(ans[2]==ans[3] && ans[1]!=ans[2])
{
printf("%d %d\n",ans[1],dis[x]+dis[y]+dis[z]-dis[ans[1]]-2*dis[ans[2]]);
continue;
}
else if(ans[1]==ans[3] && ans[1]!=ans[2])
{
printf("%d %d\n",ans[2],dis[x]+dis[y]+dis[z]-dis[ans[2]]-2*dis[ans[1]]);
continue;
}
}
return 0;
}
|