并查集
概念：并查集是一种非常精巧而实用的数据结构，它主要用于处理一些不相交集合的合并问题。一些常见的用途有求连通子图、求最小生成树的 Kruskal 法和求最近公共祖先（ LCA ）等。
使用并查集时，首先会存在一组不相交的动态集合 S={S1,S2,⋯,Sk} ，一般都会使用一个整数表示集合中的一个元素。
每个集合可能包含一个或多个元素，并选出集合中的某个元素作为代表。每个集合中具体包含了哪些元素是不关心的，具体选择哪个元素作为代表一般也是不关心的。我们关心的是，对于给定的元素，可以很快的找到这个元素所在的集合（的代表），以及合并两个元素所在的集合，而且这些操作的时间复杂度都是常数级的。
基本操作
-
init()：建立一个新的并查集并初始化，其中包含 s 个单元的集合
-
find(x)：找到元素 x 所在的集合的代表,该操作也可以用来判断两个元素是否位于同一个集合,只要他们各自的代表比较一下就可以了。
-
join(x,y)：把元素 x 和元素 y 所在的集合合并，要求 x 和 y 所在的集合不能相交，如果相交不能合并
如果相交了相当于已经连在一起分好类了,再合并在一起就环了不是我们想要的结果
代码实现
init() 初始化
就是使用树来表示集合，树的每个节点就表示集合中的一个元素，树根对应的元素就是该集合的代表
图中有两棵树，分别对应两个集合，其中第一个集合为 {a,b,c,d} ，代表元素 a ；第二个集合为 {e,f,g} ，代表元素是 e
树的节点表示集合中的元素，指针表示指向父节点的指针，根节点的指针指向自己，表示其没有父节点（也可以看作自己就是自己的父元素）。沿着每个节点的父节点不断向上查找，最终就可以找到该树的根节点，即该集合的代表元素
现在，应该可以很容易的写出 init() 和 find() 的代码了，假设使用一个足够长的数组来存储树节点（很类似之前讲到的静态链表），那么 init() 要做的就是构造出的森林并初始化,其中每个元素都是一个单元素集合,即父节点是其自身：
相应的代码如下所示，时间复杂度是 O(n) :
注意：最关键的一步，并查集使用的前提，否则后序合并查找操作都失效了
1
2
3
4
5
6
| int fa[maxn];
void init(){
for(int i=1;i<=n;i++){
fa[i]=i;
}
}
|
find() 查找
接下来，就是 find() 操作了，如果每次都沿着父节点向上查找
1
2
3
4
5
6
7
|
int find(int x){
int r=x;
if(r==fa[r])return r;
else r=find(fa[r]);
return r;
}
|
上述代码时间复杂度是树的高度，完全不可能达到常数级。如果直接对 x 进行操作反而更快，这里就需要应用一种非常简单而有效的策略——路径压缩
1
2
3
4
5
6
7
8
9
10
11
12
13
|
int find(int x){
if(x!=fa[x])fa[x]=find(fa[x]);
return fa[x];
}
int find(int x) {
int p=x,t;
while(fa[p]!=p)p=fa[p];
while (x!=p){t=uset[x];fa[x]=p;x=t;}
return x;
}
|
join() 合并
最后是合并操作 join() ，并查集的合并也非常简单，就是将一个集合的树根指向另一个集合的树根。是在每个集合的树根（祖先）处合并，所以在找到 fx ，fy后，操作对象就变为 fx ，fy
1
2
3
4
5
6
7
| void join(int x,int y){
int fx=find(x),fy=find(y);
if (fx==fy) return;
else{
fa[fx]=fy;
}
}
|
注意第 6 行 fa[fx] ，是树根(祖宗)合并，所以要 fx（ fx 已经找到祖宗的下标）
判断并查集数量
原理：到最后一个集合中只有祖宗元素指向自己（即 fa[i]==i ），剩下的子孙元素都指向非己的父元素或者祖宗元素，那么要是想知道 1-n 形成了几个并查集，就看有有几个元素所指向的是自己本身
1
2
3
4
5
6
| void count(){
int cnt=0;
for(int i=1;i<=n;i++){
if(fa[i]==i)cnt++;
}
}
|
模板
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
| #include<bits/stdc++.h>
using namespace std;
const int maxn=1e5;
int n;
int fa[maxn];
void init(){
for(int i=1;i<=n;i++){
fa[i]=i;
}
}
int find(int x){
if(x!=fa[x])fa[x]=find(fa[x]);
return fa[x];
}
void join(int x,int y){
int fx=find(x),fy=find(y);
if (fx==fy) return;
else{
fa[fx]=fy;
}
}
int count(){
int cnt=0;
for(int i=1;i<=n;i++){
if(fa[i]==i)cnt++;
}
return cnt;
}
signed main()
{
cin>>n;
init();
return 0;
}
|
启发式策略并查集
按秩合并
并查集的一个简单启发式策略——按秩合并。该方法使用秩来表示树高度的上界，在合并时，总是将具有较小秩的树根指向具有较大秩的树根。简单的说，就是总是将比较矮的树作为子树，添加到较高的树中
改变：为了保存秩，需要额外使用一个与 fa 同长度的数组 ran（相当于用来记录层数），并将所有元素都初始化为 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
| #include<bits/stdc++.h>
using namespace std;
const int maxn=1e5;
int n;
int fa[maxn];
int ran[maxn];
void init(){
for(int i=1;i<=n;i++)
fa[i]=i,ran[i]=0;
}
int find(int x){
if(x!=fa[x])
fa[x]=find(fa[x]);
return fa[x];
}
void join(int x,int y){
int fx=find(x),fy=find(y);
if(fx==fy) return;
if(ran[x]>ran[y])fa[fy]=fx;
else{
fa[fx]=fy;
if (ran[fx]==ran[fy])ran[fy]++;
}
}
signed mian()
{
cin>>n;
init();
return 0;
}
|
ran 数组里面的内容一般都是记录权值，要根据具体的题意来确定，其实就是带权并查集
按集合节点数合并
除了按秩合并，并查集还有一种常见的策略，就是按集合中包含的元素个数（或者说树中的节点数）合并，将包含节点较少的树根，指向包含节点较多的树根。这个策略与按秩合并的策略类似，同样可以提升并查集的运行速度，而且省去了额外的 ran数组
改变：fa 数组都初始化为 -1
即若 fa 的值是正数则表示该元素的父节点（的索引）若是负数则表示该元素是所在集合的代表（即树根），而且值的相反数即为集合中的元素个数
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
| #include<bits/stdc++.h>
using namespace std;
const int maxn=1e5;
int n;
int fa[maxn];
void init(){
for(int i=1;i<=n;i++)
fa[i]=-1;
}
int find(int x){
if (fa[x]<0) return x;
fa[x]=find(fa[x]);
return fa[x];
}
void join(int x,int y){
int fx=find(x),fy=find(y);
if(fx==fy)return;
if(fa[fx]<fa[fy]){
fa[fx]+=fa[fy];
fa[fy]=fx;
}
else{
fa[fy]+=fa[fx];
fa[fx]=fy;
}
}
signed main()
{
cin>>n;
init();
return 0;
}
|
如果要获取某个元素 x 所在集合包含的元素个数，可以使用 -fa[find(x)] 得到
带权并查集
转载博客 带权并查集就是在并查集的基础上多了其他的限制条件，一般需要另开其他数组记录，相应的题目比较灵活。
复杂度分析
并查集的空间复杂度是 O(n) 的，如果是按秩合并占的空间要多一些。
find() 和 join() 操作时间复杂度都可以看成常数级
树状数组
参考博客
概念：树状数组（又称二叉索引树）是一个查询和修改复杂度都为 log(n) 的数据结构，它是利用二进制的一些特点来实现。它的功能有局限性主要是用来动态查询连续和（或者是前缀和）的问题。它利用 O(n) 的附加空间复杂度，将线性的数列结构转化成树状结构从而进行跨越扫描，高效完成查询连续和
知识回顾
代码实现
| i |
二进制 |
K |
|
| 1 |
(1) 2 |
0 |
c[1]=a[1] |
| 2 |
(10) 2 |
1 |
c[2]=a[1]+a[2]=c[1]+a[2] |
| 3 |
(11) 2 |
0 |
c[3]=a[3] |
| 4 |
(100) 2 |
2 |
c[4]=a[1]+a[2]+a[3]+a[4]=c[2]+c[3]+a[4] |
| 5 |
(101) 2 |
0 |
c[5]=a[5] |
| 6 |
(110) 2 |
1 |
c[6]=a[5]+a[6]=c[5]+a[6] |
|
|
|
|
规律：
-
C[i]=A[i-2k+1]+A[i-2k+2]+…+A[i]（ k 为 i 的二进制中从最低位起到高位连续零的长度）
-
SUMi = C[i] + C[i-2k1] + C[(i - 2k1) - 2k2] + …（ k2 为下一个数组 i-2^k1 ^序号的 k ，依次类推下去）
-
A[i] 包含于 C[i + 2k1]、C[(i + 2k1) + 2k2]、…（ k2 为下一个数组 i-2k1 序号的 k ，依次类推下去）
-
lowbit（低位技术）：2k=i&(-i)
注意：和并查集不同，树状数组必须 1 开始存，从 0 开始存的话求 lowbit(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
| #include<bits/stdc++.h>
using namespace std;
int n;
int a[1005],c[1005];
int lowbit(int i){
return i&(-i);
}
void updata(int i,int k){
while(i<=n){
c[i]+=k;
i+=lowbit(i);
}
}
int getsum(int i){
int res=0;
while(i>0){
res+=c[i];
i-=lowbit(i);
}
return res;
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i],updata(i,a[i]);
int x,y;
cin>>x>>y;
int sum=getsum(y)-getsum(x-1);
return 0;
}
|
初始存值的时候相当于也是一次更新，另外中途更改值的时候不仅要更改相应的C[i]，也要更新后面包含 C[i] 的其他 C[]
操作用途
树状数组的跨域扫描高效性导致在区间上的作用巨大，借助差分可以实现快速维护查询区间
单点更新、单点查询
其实传统数组就可以实现，用不着树状数组
单点更新、区间查询
关键就是区间查询（一般是求和），记住一个公式若是 [A,B] 区间的和，就用 [1,B] 区间的和减去 [1,A-1] 区间的和，即 getsum(B)-getsum(A-1)
因为一般是闭区间去和，两边界的值也要算入在内
区间更新、单点查询
若仍用上述树状数组对于每个点一个一个更改复杂度太高，这里我们引入差分改用差分建树
假设我们规定 A[0]=0 ，另开一个数组 D[] 定义 D[i]=A[i]-A[i-1] 代替 C[]
则有 A[i]=D[1]+D[2]+...+D[i]
例如对于下面这个数组
- A[] = 1 2 3 5 6 9
- D[] = 1 1 1 2 1 3
如果我们把 [2,5] 区间内值加上 2 ，则变成了
- A[] = 1 4 5 7 8 9
- D[] = 1 3 1 2 1 1
只有 D[2] 和 D[6] 变了其他的都没变，需要修改的数组位置明显减少
规律：当某个区间 [x,y] 值改变了，区间内的差值是不变的，只有 D[x] 和 D[y+1] 的值发生改变
注意：因为 D[] 的定义和 C[] 存在区别，求和公式求出来的不再是 A[1]~A[i] 的总和而是 A[i] 的值
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
| #include<bits/stdc++.h>
using namespace std;
int n;
int a[50005],d[50005];
int lowbit(int x){
return x&(-x);
}
void updata(int i,int k){
while(i<=n){
d[i]+=k;
i+=lowbit(i);
}
}
int getsum(int i){
int res=0;
while(i>0){
res+=d[i];
i-=lowbit(i);
}
return res;
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
updata(i,a[i]-a[i-1]);
}
int x,y,k;cin>>x>>y>>k;
updata(x,k);
updata(y+1,-k);
int m;cin>>m;
int sum=getsum(m);
return 0;
}
|
区间更新、区间查询
上面我们说的差分建树状数组得到的是某个点的值，那如果我既要区间更新又要区间查询怎么办。这里我们还是利用差分，观察下面推导：
1
2
3
4
| A[1]+A[2]+...+A[n]
=(D[1])+(D[1]+D[2])+...+(D[1]+D[2]+...+D[n])
=n*D[1]+(n-1)*D[2]+...+D[n]
=n*(D[1]+D[2]+...+D[n])-(0*D[1]+1*D[2]+...+(n-1)*D[n])
|
我们假设另开一个数组 E[] 定义 E[i]=(i-1)*D[i]
每当修改 D[i] 的时候，就同时修改一下 E[i] ，这样复杂度就不会改变
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
| #include<bits/stdc++.h>
using namespace std;
int n;
int a[50005];
int sum1[50005];
int sum2[50005];
int lowbit(int x){
return x&(-x);
}
void updata(int i,int k){
int x=i;
while(i<=n){
sum1[i]+=k;
sum2[i]+=k*(x-1);
i+=lowbit(i);
}
}
int getsum(int i){
int res=0,x=i;
while(i>0){
res+=x*sum1[i]-sum2[i];
i-=lowbit(i);
}
return res;
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
updata(i,a[i]-a[i-1]);
}
int x,y,k;cin>>x>>y>>k;
updata(x,k);
updata(y+1,-k);
int sum =getsum(y)-getsum(x-1);
return 0;
}
|
应用：求逆序对
相关操作：离散化
首先要引入一个概念——离散化数据。离散化是一种常用的技巧，有时数据范围太大并且我们只关心数据之间的大小关系时我们将数据离散化放缩到我们能处理的范围（相当于预处理），也就是让他们的数值都变小一点但大小关系仍保持不变
打个比方，某个题目告诉你有 104 个数，每个数大小不超过 1010 ，要你对这些数进行相对大小关系排序，那么肯定不能直接开 1010大小的数组，但是 104 的范围就完全没问题
博客讲解1 博客讲解2
基础操作：1.排序2.去重3.索引
方法一：数组离散化
原数组
| a.value |
1000 |
5000 |
2000 |
8000 |
| a.id |
1 |
2 |
3 |
4 |
按 value 升序排列
| a.value |
1000 |
2000 |
5000 |
8000 |
| a.id |
1 |
3 |
2 |
4 |
将 value 重新赋值
| a.value |
1 |
2 |
3 |
4 |
| a.id |
1 |
3 |
2 |
4 |
离散后按照原元素位置顺序输出：1，3，2，4
需要注意的是数组离散不能去重，所以适用范围比较小
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| bool cmp(node a,node b){
return a.val<b.val;
}
for(int i=1;i<=n;i++){
cin>>a[i].val;
a[i].id=i;
}
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++)
b[a[i].id]=i;
|
方法二：STL +二分离散化
这个好理解，直接对存入的原数组去重并重新编号，首推这个方法
核心代码
需要用到二分函数和去重函数unique
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
for(int i=1;i<=n;i++){
cin>>a[i];
b[i]=a[i];
}
sort(b+1,b+1+n);
int len=unique(b+1,b+1+n)-b-1;
for(int i=1;i<=n;i++){
a[i]=lower_bound(b+1,b+1+n,a[i])-b;
cout<<a[i]<<" ";
}
|
模板题：给你 n*m 的交叉路口上每个楼的高度，现在要你重新安排每个楼的高度，让每行每列的大小关系不变，对于每个交叉点，输出该行该列中最大元素的值
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> row[1005],col[1005];
ll a[1005][1005];
signed main()
{
ios::sync_with_stdio(false),cin.tie(0);
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>a[i][j];
row[i].push_back(a[i][j]);
col[j].push_back(a[i][j]);
}
}
for(int i=0;i<n;i++){
sort(row[i].begin(),row[i].end());
row[i].erase(unique(row[i].begin(),row[i].end()),row[i].end());
}
for(int j=0;j<m;j++){
sort(col[j].begin(),col[j].end());
col[j].erase(unique(col[j].begin(),col[j].end()),col[j].end());
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
int rows=lower_bound(row[i].begin(),row[i].end(),a[i][j])-row[i].begin();
int rowb=row[i].end()-lower_bound(row[i].begin(),row[i].end(),a[i][j]);
int cols=lower_bound(col[j].begin(),col[j].end(),a[i][j])-col[j].begin();
int colb=col[j].end()-lower_bound(col[j].begin(),col[j].end(),a[i][j]);
cout<<max(rows,cols)+max(rowb,colb);
if(j!=m-1)cout<<" ";
else cout<<endl;
}
}
return 0;
}
|
方法三：map 离散化
利用了 map 自动排序去重的特性，所以同样适用于去重，操作更类似数组离散化但是这个适用于去重
1
2
3
4
5
6
7
8
9
10
|
for(int i=1;i<=n;i++){
cin>>a[i];
map[a[i]]=i;
}
map<int,int>::iterator it=mp.begin();
for(it;it<mp.end();it++){
cout<<it->second<<" ";
}
|
利用离散化求逆序对
逆序对：在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序对的总数就是这个排列的逆序对
求某个数的逆序对的规律：因为离散化后序列是自然数的排列，所以可以利用本身值减去前面比他小的数的个数和本身（也就是 1 ）求出来
注意：一般题目出的是求某个排列的所有逆序对的和，按照上述的方法算法不好实现，一般会转换为按照如下规律查找，可以实现在线操作
规律：计算一个排列的逆序对的和时，每插入一个数到数组末尾，就找这个数前面有多少比它小（找当前数和前面的数能组成的逆序对）。相当于从左向右处理序列求排列逆序对——每个数当前位置减去前面比自己小的数个数和本身（也就是 1 ）
注意：排列保证了数列没有重复的数，有重复的数的序列不叫排列。将序列离散化后也就成为了一个排列，
了解了离散化后就可以对很大的数据进行求逆序数了。离散处理后将每一个数存入树状数组，然后求出每一个数求逆序对，再对每一个逆序对求和就得到排列的逆序对了。利用桶的思想和树状数组结合
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
| #include<bits/stdc++.h>
using namespace std;
const int maxn=5e4+5;
int n;
int a[maxn];
int c[maxn];
struct node{
int val,id;
}in[maxn];
int lowbit(int i){
return i&(-i);
}
void update(int i,int k){
while(i<=n){
c[i]+=k;
i+=lowbit(i);
}
}
int getsum(int i){
int res=0;
while(i>0){
res+=c[i];
i-=lowbit(i);
}
return res;
}
bool cmp(node a,node b){
return a.val<b.val;
}
signed main(){
while(cin>>n&&n){
for(int i=1;i<=n;i++){
cin>>in[i].val;
in[i].id=i;
}
sort(in+1,in+n+1,cmp);
for(int i=1;i<=n;i++)
a[in[i].id]=i;
memset(c,0,sizeof(c));
long long ans=0;
for(int i=1;i<=n;i++){
update(a[i],1);
ans+=i-getsum(a[i]);
}
cout<<ans<<endl;
}
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
| int lowbit(int x){
return x&-x;
}
void add(int x,int y,int v){
while(x<=n){
int ty=y;
while(ty<=n)
tree[x][ty]+=v,ty+=lowbit(ty);
x+=lowbit(x);
}
}
int ask(int x,int y){
int res=0;
while(x){
int ty=y;
while(ty)
res+=tree[x][ty],ty-=lowbit(ty);
x-=lowbit(x);
}
return res;
}
|
模板题
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
|
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=(1<<12)+10;
int n,m;
ll c[maxn][maxn];
int lowbit(int x){
return x&-x;
}
void update(int x,int y,int k){
for(x;x<=n;x+=lowbit(x))
for(int ty=y;ty<=m;ty+=lowbit(ty))
c[x][ty]+=k;
}
ll getsum(int x,int y){
ll res=0;
for(x;x;x-=lowbit(x))
for(int ty=y;ty;ty-=lowbit(ty))
res+=c[x][ty];
return res;
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0);
cin>>n>>m;
int q;
while(cin>>q){
if(q==1){
int x,y,k;
cin>>x>>y>>k;
update(x,y,k);
}
else{
int a,b,c,d;
cin>>a>>b>>c>>d;
cout<<getsum(c,d)-getsum(c,b-1)-getsum(a-1,d)+getsum(a-1,b-1)<<endl;
}
}
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
| void add(int x,int y,int v){
while(x<=n){
int ty=y;
while(ty<=n)
c[x][ty]+=v,ty+=lowbit(ty);
x+=lowbit(x);
}
}
void real_add(int x1,int y1,int x2,int y2,int v){
add(x1,y1,v);
add(x1,y2+1,-v);
add(x2+1,y1,-v);
add(x2+1,y2+1,v);
}
int ask(int x, int y){
int res=0;
while(x){
int ty=y;
while(ty)
res+=c[x][ty],ty-=lowbit(ty);
x-=lowbit(x);
}
return res;
}
|
