常见数据结构

双端队列

• 双端队列是一种特殊的队列，它与普通队列的区别在于，普通队列只能队尾入队、队头出队，而双端队列的两头都能进行入队、出队、元素访问的操作。
• STL 中封装了一个双端队列 deque 可以直接使用，使用前需要引用头文件 <queue>。
• deque 的声明方式为 deque<object_type> variable_name;，尖括号 <> 里面的是队列中元素的数据类型，后面的是队列的名字。例如，queue<int> q; 声明的就是元素都是 int 类型的，名为 q 的双端队列。

deque 常用操作

操作	含义
push_front(x)	向队头插入一个元素 $x$
push_back(x)	向队尾插入一个元素 $x$
pop_front()	弹出队头元素
q.pop_back()	弹出队尾元素
q.clear()	清空双端队列
q.front()	返回队头元素
q.back()	返回队尾元素
q.size()	返回队列中元素个数，返回值类型为 size_t（size_t 的大小跟操作系统和编译器有关，$32$ 位操作系统下可能是 unsigned int，$64$ 位操作系统下可能是 unsigned long long）
q.empty()	队列为空返回 true，否则返回 false

以上操作除了 q.clear() 的时间复杂度是 $O(n)$ 的，其余操作的时间复杂度都是 $O(1)$ 的。

此外，deque 还可以进行运算符操作：

• 利用 = 为 deque 进行赋值。
• 利用 [] 访问元素，类似于数组和 vector。

优点：

• 与 STL 中的其他容器相比，deque 在双端都支持高效的增删操作。

缺点：

• deque 在内存中的存储不一定是连续的，因此利用普通指针对 deque 中的元素进行遍历是非常危险的操作，很有可能会遍历到非法区域。
• deque 并不适合遍历！由于 deque 在内存中的存储不一定连续，所以每次访问元素时，deque 底层都要检查是否触达了内存片段的边界，造成了额外的开销！
• 如果担心需要因遍历 deque 而导致代码的时间复杂度过大，可以考虑利用数组来模拟双端队列。

推荐题目：

• LOJ 6515

单调队列

单调队列也是队列，它与普通队列的不同点在于 “单调”，也就是说队列中的元素是有序的。根据队列中的元素的单调性，单调队列又可以分为 “单调递增队列” 和 “单调递减队列”。

例题

题目大意：给定一个长度为 $n$ 的整数数组，找出所有长度为 $k$ 的子数组中的最大值和最小值。

• 暴力的做法是对于每一个子数组，直接枚举所有子数组中的值找出最大最小值，时间复杂度为 $O(n)$。
• 一个更优的做法是利用单调队列找最大最小值。
  • 做法：从前往后进行遍历，每一次将下一位的下标放入队列中，然后将队首位于当前子数组外的下标出队。
  • 在这个队列中，储存的是元素的下标，我们要维护的单调性不是队列元素的单调性，而是队列元素作为下标所对应的值的单调性。
  • 为什么储存元素的下标而不是元素本身：需要将队首位于长度为 $k$ 的子数组外的元素出队，储存下标方便判断对应元素是否位于当前子数组内。
  • 从前往后遍历，单调递增队列的第一个元素就是当前的最小值，单调递减队列的第一个元素就是当前元素的最大值。

参考代码

#include <iostream>
#include <vector>
#include <queue>
using namespace std;int main() {ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);int n, k;cin >> n >> k;vector<int> a(n + 1), minm(n - k + 1), maxm(n - k + 1);for (int i = 1; i <= n; i++) cin >> a[i];deque<int> dq1, dq2;for (int i = 1; i <= n; i++) {while (!dq1.empty() && a[dq1.back()] > a[i]) dq1.pop_back();dq1.push_back(i);while (!dq1.empty() && i - dq1.front() >= k) dq1.pop_front();if (i >= k) minm[i - k] = a[dq1.front()];while (!dq2.empty() && a[dq2.back()] < a[i]) dq2.pop_back();dq2.push_back(i);while (!dq2.empty() && i - dq2.front() >= k) dq2.pop_front();if (i >= k) maxm[i - k] = a[dq2.front()];}return 0;
}

推荐题目

• 洛谷 P1886
• 洛谷 P1419
• 洛谷 P1725
• 洛谷 P1714

优先队列

• 优先队列也是一种队列，不过不同的是，优先队列的出队顺序是按照优先级来的。一般来说，优先级较高的先出队。
• 每个节点的键值都大于等于其父亲键值的堆叫做小根堆，否则叫做大根堆。优先队列一般都是有由堆来实现的，STL 中的 priority_queue 就是一个大根堆。
• 键值是用于比较节点优先级的值。对于基本数据类型、pair<int, int> 或者是 string 类，一般默认数值较大的优先级较高。对于 struct 和 class 等自定义数据类型，需要重载运算符来自定义优先级。

struct node {int u, dis;bool operator< (const node &x) const {return x.dis < dis;}
};
priority_queue<node> pq;

上面这个就是常用于最短路算法 dijsktra 中结构体运算符的重载写法。使用 priority_queue 前需要引用头文件 <queue>。声明方式为 priority_queue<object_type> variable_name;，里面的 object_type 是优先队列中的数据类型，variable_name 是优先队列名字。

priority_queue 常用操作

操作	含义
pq.push(x)	向优先队列中插入元素 $x$
pq.pop()	弹出元素
pq.top()	访问优先队列的堆顶元素
pq.empty()	查看优先队列是否为空，空则返回 true，否则返回 false
pq.size()	查看优先队列大小，返回值为 size_t（size_t 的大小跟操作系统和编译器有关，$32$ 位操作系统下可能是 unsigned int，$64$ 位操作系统下可能是 unsigned long long）

pq.push(x) 跟 pq.pop() 操作时间复杂度是 $O(\log n)$ 的，其余操作时间复杂度都是 $O(1)$ 的。

推荐题目

• 洛谷 P1090
• 洛谷 P1668
• 洛谷 P2085
• 洛谷 P1631

ST 表

ST 表（Sparse Table，稀疏表）是用于解决 可重复贡献问题（例如对某些区间的最大值/最小值的重复询问）的数据结构。

• ST 表是基于倍增的思想实现的，在重复贡献问题上 ST 相比于树状数组、线段树等数据结构的优势在于 ST 表能做到 $O(1)$ 查询，但是 ST 表不支持修改并且预处理的时间复杂度是 $O(n\log n)$。
• 具体实现（假设是要求区间最大值）：
  • 设 $f_{i,j}$ 表示从 $i$ 开始，长度为 $2^j$ 的区间，即 $[i,i+2^j-1]$ 区间内的最大值。
  • 根据定义可以得出 $f_{i,j}=\max (f_{i,j-1},f_{i+2^{j-1},j-1})$，所以预处理时只需要分别枚举 $i$ 和 $j$ 即可。由于 $i\le n$ 并且 $2^j\le n$ 即 $j\le \log n$，所以预处理的时间复杂度是 $O(n\log n)$。
  • 查询操作：对于每一个查询操作，我们可以将查询的区间 $[l,r]$ 分为 $[l,l+2^j-1]$ 和 $[r-2^j+1,r]$，这两个区间最大值的最大值就是答案，即 $\max (f_{l,j},f_{r-2^j+1,r})$。由于 $\frac{r-l+1}{2}<2^j\le r-l+1$，所以取 $j=\lfloor {\log }_2(r-l+1)\rfloor$ 即可。

参考代码

#include <iostream>
#include <vector>
using namespace std;int main() {ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);int n;cin >> n;// 预处理 logvector<int> Log(n);Log[1] = 0;for (int i = 2; i <= (int)Log.size(); i++) Log[i] = Log[i / 2] + 1;vector<vector<int>> f(n + 1, vector<int>(Log[n] + 1));for (int i = 1; i <= n; i++) cin >> f[i][0];for (int j = 1; j <= Log[n]; j++)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]);return 0;
}

推荐题目

• 洛谷 P3865
• 洛谷 P2251
• 洛谷 P2880

并查集

并查集是一种用于管理元素所属集合的数据结构，它的实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。

并查集的两种操作：

• 合并 (Union)：并两个元素所属集合。
• 查询 (Find)：查询某个元素所属集合，这可以用于判断两个元素是否属于同一集合。

并查集一般是通过一个数组 $f_i$ 记录 $i$ 节点指向的节点，例如 $f_i=j$ 表示 $i$ 节点指向 $j$ 节点，也就是说 $i$ 和 $j$ 节点属于同一个集合。并查集在经过修改后可以支持单个元素的删除、移动；使用动态开点线段树还可以实现可持久化并查集。

初始化

最开始时，每个节点指向自己，表示每一个节点都是一个单独的集合。

vector<int> f(n + 1);
for (int i = 1; i <= n; i++) f[i] = i;

查询

并查集本质是通过森林去维护元素所属的集合，所以要判断两个节点是否属于同一个集合，只需要判断两个节点所在森林的根节点是否相同即可。

int find(int x) {return f[x] == x ? x : find(f[x]);
}

上面这段代码 f[x] == x 如果成立，代表 x 节点指向自己、没有父节点，所以 x 节点就是根节点；如果 f[x] == x 不成立，那么代表 x 节点不是根节点，那就接着查询 x 的父节点 f[x] 是否是根节点。

合并

并查集的合并，本质上是将两个集合合并，也就是将森林中的两棵树进行合并，实际操作只需要将一棵树的根节点指向另一棵树的根节点即可。

void union(int x, int y) {f[find(x)] = find(y);
}

这么时间复杂度是什么？有什么问题？

• 最坏情况下，每一次合并都是将一棵链状的树连接到另一个单独的节点上，那么并查集就会森林就会逐渐退化成链表，每一次查询操作的复杂度都是 $O(n)$，效率十分低下。

怎么解决

• 启发式合并（也叫按秩合并）：在合并操作的时候不是将任意一个根节点接到另一个节点上，而是将深度较小的树的根节点接到另一棵树的根节点上，这样子最坏情况下树的深度不会超过 $O(\log n)$，因此查询操作的最坏复杂度不会超过 $O(\log n)$。
• 路径压缩：并查集维护的是元素所属的集合，而判断元素属于哪个集合只需要判断元素所属集合的树的根节点，因此对于任何元素，我们并不关心该元素在走向根节点路径上有哪些节点，我们只需要直到这个元素对应哪一个节点即可。根据这个发现，我们在查询操作的时候，就可以进行路径压缩，实质操作就是在查询的时候，让同一分支的所有节点都指向根节点。

参考代码

#include <vector>vector<int> f, h;int find(int x) {return f[x] == x ? x : f[x] = find(f[x]);// f[x] != x 时，上面的表达式等价于// f[x] = find(f[x]);// return f[x];
}void union(int x, int y) {int rootX = find(x), rootY = find(y);if (h[rootX] < h[rootY]) f[rootX] = rootY;else {if (h[rootX] == h[rootY]) h[rootX]++;f[rootY] = rootX;}
}int main() {int n;cin >> n;f.resize(n + 1), h.resize(n + 1);for (int i = 1; i <= n; i++) f[i] = i, h[i] = 1;
}

二叉堆