模板 数据结构（1）

发表于 | 分类于 |
字数统计: 1,911 字

数据结构的第一份模板，包含了栈，队列，并查集等内容。

并查集

基本实现

并查集是一个实现起来较为简单的数据结构。它维护的是一系列不相交集合，每一个集合都由该集合中的一个代表元表示。

整个并查集实际上是一个森林，每一个元素 $x$ 都有一个属性 $fa[x]$ 作为 $x$ 所在的树的父节点。树根的父节点设为它本身。这样只要不断沿着 $fa[x]$ 走就能走到这一棵树的根，从而知道一个元素的归属。

事实上整棵树的形态并不重要，因为我们需要知道的是一个元素所在树的根节点。因此可以在递归找根时，令经过路径上的节点的 $fa$ 全部设为最后找到的根，这样可以方便之后的查询。这种优化称为路径压缩。路径压缩后的并查集查找操作的均摊时间复杂度是 $O(\log n)$。

并查集还要支持合并两个集合的操作。这个操作的基本实现方式是找出两个集合对应的树根，然后令其中一个根的 $fa$ 设为另外一个树根。这时的合并是可以指定方向的，即指定新集合的代表元是哪一个根。

如果不需要指定代表元就可以使用按秩合并。它是一种启发式合并。它将秩（一般定义为集合大小或者合并次数）较小的集合合并到秩较大的集合上，这样就只增加了小集合的查询代价。这样总共增加的总代价是 $O(n\log n)$ 级别的。这时查询操作的均摊时间复杂度也是 $O(\log n)$。

两种优化都使用的并查集的查询时间复杂度近似于常数级别。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int fa[100005], rank[100005], n;
void init(){
    for(int i = 1; i <= n; ++i)
        fa[i] = i, rank[i] = 1;
}
int Find(int x){
    if(x == fa[x]) return x;
    return (fa[x] = Find(fa[x]));
}
void joint(int x, int y){
    int xa = Find(x), ya = Find(y);
    if(xa == ya) return ;
    if(rank[xa] > rank[ya])
        fa[ya] = xa, rank[xa] += rank[ya];
    else 
        fa[xa] = ya, rank[ya] += rank[xa];
}
void joint(int from, int to){
    int xa = Find(from), ya = Find(to);
    if(xa == ya) return ;
    fa[xa] = ya;
}

基于并查集树的性质，可以将并查集的树边视作有向边或者无向边，这两种视角可以分别处理不同的问题。

无向边的并查集常用于维护无向图的连通性。这在 Kruskal 算法中得到了体现。扩展一下：并查集擅长维护等价关系（集合即等价类）。

有向边的并查集常用于维护一个数组中空闲和占用的情况。比如，可以令一个集合的根表示当前可用位置，如果占用了这个位置就把该位置所在集合和该位置之前的一个位置所在集合合并，这么做就可以快速查询一个位置之前最近的空闲位置。也可以用来维护链状或者树形的关系。

带权并查集

并查集的边可以拥有边权，而边权可以表示一些信息。

带权并查集和普通并查集主要在两个地方有所不同：一是在查找操作中，路径压缩时要进行边权的更新；二是在合并操作中，要确定合并方向，以及合并中新产生的边的边权。根据不同的问题会有不同的处理方法。重点在于弄清楚边权的意义。

1
2
3
4
5
6
7
8
9
10
11
12
13
int fa[100005], dis[100005], n;
int Find(int x){
    if(x == fa[x]) return x;
    int rt = Find(fa[x]);
    //更新边权操作
    return (fa[x] = rt);
}
void joint(int from, int to){
    int xa = Find(from), ya = Find(to);
    if(xa == ya) return ;
    fa[xa] = ya;
    //更新dis[xa]
}

多重关系并查集

联想到并查集能够维护一系列等价关系，我们可以将一个点拆成多个点，每一个点表示“满足某一个条件的集合”，如和 x 相同或者和 x 不同。这样如果题目中给出的都是双蕴含（或者异或）类型的条件，就可以利用这种并查集高效地维护这样的关系。

典型例题：NOI2001 食物链

树状数组

能用一个二进制数分出 $O(\log n)$ 个小区间：从 $[x - \text{lowbit}(x) + 1, x]$ 递归下去。利用这种思想，对于一个数组 $a[i]$，可以构造出一个数组 $c[i]$，其中 $c[x] = \sum _{i=x - \text{lowbit}(x) + 1}^{x} a[i]$。树状数组就是这样一个数组。

单点修改，单点求值

树状数组的基本模型是单点修改和求和。

要修改 $a[i]$，就要修改掉所有包含 $a[i]$ 的 $c[x]$。根据 $c[x]$ 的公式，只有所有 $x\ge i$且$\text{lowbit}(x) \ge \text{lowbit}(i)$的$x$满足条件。因此可以使用i += lowbit(i)不断获取下一个要更新的节点。
要查询$a[1]+\cdots + a[r]$，就按照上面分区间的思想，使用r -= lowbit(r)不断获取下一个要累计的区间。
上面两个操作的时间复杂度均为$O(\log n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
int lowbit(int x){
    return (-x) & x;
}
void add(int k, int v){
    while(k <= n)
        c[k] += v, k += lowbit(k);
}
int query(int r){
    int res = 0;
    while(r)
        res += c[r], r -= lowbit(r);
    return res;
}

初始化

初始化一个树状数组可以使用依次单点更新的方法，这样做是$O(n\log n)$的。实际上，可以使用和堆类似的建立方法，先对相邻的2个元素建立，再对相邻的4个元素建立，如此反复。这样做是$n+\frac{n}{2}+\frac{n}{4}+\cdots = O(n)$的。

1
2
3
4
5
6
void build(int a[], int n){
    memcpy(c, a, sizeof(a));
    for(int len = 2; len <= n; len <<= 1)
        for(int i = len; i <= n; i += len)
            c[i] += c[i - (len >> 1)];
}

区间修改，单点求值

维护原来数列的差分数列即可。

区间修改，区间求值

还是维护原来数列的差分数列。设$a[0]=0$，则$d[i] = a[i] - a[i - 1], a[i]=\sum_{j = 1}^{i}d[j]$。因此有

所以另外维护一个$i\times d[i]$的树状数组即可。

1
2
3
4
5
6
7
8
9
10
11
int c1[100005], c2[100005], n;
void add(int r, int k){
    for(int i = r; i <= n; i += lowbit(i))
        c1[i] += k, c2[i] += k * r;
}
ll query(int r){
    ll res = 0;
    for(int i = r; i > 0; i -= lowbit(i))
        res += 1ll * (r + 1) * c1[i] - c2[i];
    return res;
}

扩展

树状数组不仅能够维护前缀和，还能够维护其他具有和前缀有关的，具有和性质的量，如前缀最大值。

二维树状数组

线段树

线段树是一种比树状数组更为通用的数据结构：它将一个区间不断二分，父区间和子区间都作为树的节点，且最终形成一系列长度为0的叶子节点，并且对每一个区间节点附加一些信息以维护。线段树的这种结构使得它能在$O(\log n)$的时间内完成许多任务。

权值线段树

权值线段树是线段树的一种，它的节点记录在该节点代表的区间内，出现过的数的个数。它常用于解决区间第$k$小/大问题。