我们会把重点放在复杂的树形结构上,主要讲解 并查集、树状数组、线段树、zkw 线段树、二叉查找树、分块。
不久的将来,将会更新可持久化并查集、可持久化线段树、平衡树、左偏树。
并查集
并查集基本概念
它是一种轻量型的简单数据结构,可以动态维护若干个集合,并支持合并查询。
find(x)
,查询一个元素属于哪一个集合。merge(x, y)
,合并两个集合。
为了实现这个数据结构,我们采用 一个代表 表示这个集合。就是说,怎么表示这个集合呢,就挑一个人,他就代表了这整个集合。
定义 $p_x$ 表示 $x$ 所在集合的代表。
可以写出如下 find
函数。
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
merge
函数也很简单:
int merge(int x, int y) {
int f1 = find(x), f2 = find(y);
if (f1 != f2) p[f1] = f2;
}
路径压缩与按秩合并
路径压缩:执行 find
函数的同时,把访问过的每个节点都直接指向树根。
按秩合并:在对两个不同子集连接时,按照 rank 来连,也就是 rank 低的连在 rank 高的下面。rank 高的做父亲节点。
同时采用上面两种优化的并查集,每次 find
操作均摊复杂度进一步可以降到 $O(a(N))$,其中 $a(N)$ 为反阿克曼函数,对于 $\large ∀N\leq 2^{2^{10^{19729}}}$,都有 $a(N)<5$。故可以看成一个小小的常数。
同时,我 R.E.Tarjan(罗伯特·塔扬) 发表的论文中证明了这一点。
例题
Acwing 237.程序自动分析
原题见 Acwing 237。
对于每一个等号的条件,我们可以用并查集把他们合并起来。对于每一个 $x\not = y$,我们看这两个 $x,y$ 是否同一个集合中即可,如果在,就出现有矛盾。
因为如果在一个集合中,表示 $x$ 在之前的条件中是等于 $y$ 的。
然鹅这道题数据范围非常的大,仅用数组来存存不下,可以开一个 map
来存储。
参考代码(算是全场最短了吧)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int T, n, x[N], y[N], t[N];
unordered_map<int, int> p;
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int merge(int x, int y) {
int f1 = find(x), f2 = find(y);
if (f1 != f2) p[f1] = f2;
}
int main() {
cin >> T;
while (T--) {
cin >> n;
p.clear();
for (int i = 1; i <= n; i++) cin >> x[i] >> y[i] >> t[i], p[x[i]] = x[i], p[y[i]] = y[i];
for (int i = 1; i <= n; i++) if (t[i]) merge(x[i], y[i]);
int flg = 0;
for (int i = 1; i <= n; i++) if (t[i] == 0) if (find(x[i]) == find(y[i])) flg = 1;
puts(flg ? "NO" : "YES");
}
}
扩展域与带边权的并查集供学有余力的同学参考相关资料。
推荐习题:Acwing 1252
,Acwing 1250
,Acwing 837
,Acwing 239
。、
树状数组
树状数组 (BIT) 是一种xxxx的数据结构,作用是来维护序列的前缀和(注意,它只能求出前缀)。
我们建立一个树状数组 c,其中 $c[x]$ 保存序列 a 区间 $\rm [x-lowbit(x)+1,x]$ 中所有数的和。
您是不是ds选手啊
orz
az