跳到主要内容

分享丨【题单】常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）

By 灵茶山艾府

题目已按照难度分排序，右侧数字为难度分。

如果遇到难度很大，题解都看不懂的题目，建议直接跳过，二刷的时候再来尝试。

数据结构题单数据结构入门数据结构新手教程

一、前缀和​

§1.1 基础​

原理讲解

§1.2 前缀和与哈希表​

§1.3 距离和​

图解

§1.4 前缀异或和​

§1.5 其它一维前缀和​

§1.6 二维前缀和​

【图解】一张图秒懂二维前缀和！

二维前缀最小值：

二、差分​

§2.1 一维差分（扫描线）​

原理讲解（推荐和【图解】从一维差分到二维差分 一起看）

§2.2 二维差分​

【图解】从一维差分到二维差分

三、栈​

§3.1 基础​

§3.2 进阶​

§3.3 邻项消除​

§3.4 合法括号字符串​

注：部分题目可以不用栈，而是用一个数字记录嵌套深度。

§3.5 表达式解析​

§3.6 对顶栈​

§3.7 单调栈​

见 单调栈题单。

四、队列​

队列常用在 BFS 中，见 网格图题单 和 图论题单。与此相比，栈常用在 DFS 中，但无需我们手动维护。

§4.1 基础​

§4.2 设计​

§4.3 单调队列​

个人觉得叫单调双端队列更准确。

原理讲解

§4.4 单调队列优化 DP​

一般用来维护一段转移来源的最值。

  1. 前提：区间右端点变大时，左端点也在变大（同滑动窗口）。
  2. 转移前，去掉队首无用数据。
  3. 计算转移（直接从队首转移）。
  4. 把数据（一般是 f[i]f[i] ）插入队尾前，去掉队尾无用数据。

五、堆（优先队列）​

§5.1 基础​

§5.2 进阶​

§5.3 重排元素​

§5.4 第 K 小/大​

部分题目也可以用二分解决。

§5.5 反悔堆​

基于堆的反悔贪心。

§5.6 懒删除堆​

§5.7 对顶堆​

另见 图论题单 中的 Dijkstra 算法。

六、字典树（trie）​

§6.1 基础​

§6.2 进阶​

§6.3 字典树优化 DP​

§6.4 0-1 字典树（异或字典树）​

部分题目也可以用试填法解决。

七、并查集​

§7.1 基础​

见 网格图题单 中的 DFS 和 图论题单 中的 DFS，其中大部分题目可以用并查集实现。

§7.2 进阶​

§7.3 公因数并查集​

§7.4 数组上的并查集​

§7.5 区间并查集​

§7.6 边权并查集​

八、树状数组和线段树​

能用树状数组解决的题目，也能用线段树解决（反过来不一定）。但树状数组实现简单，代码短。

为方便大家练习，我把适合用树状数组解决的题目分到树状数组中，其余分到线段树中。

§8.1 树状数组​

讲解：带你发明树状数组！附数学证明

§8.2 逆序对​

也可以在归并排序的同时计算。

§8.3 线段树（无区间更新）​

§8.4 Lazy 线段树（有区间更新）​

§8.5 动态开点线段树​

部分题目也可以用珂朵莉树解决。

专题：离线算法​

对询问排序，通过改变回答询问的顺序，使问题更容易处理。

相应的，在线算法就是按照输入的顺序处理，来一个处理一个。

编辑此页
最后由 Heng_Xin_666 于 更新
请作者喝奶茶:
Alipay IconQR Code
Alipay IconQR Code
本文遵循 CC CC 4.0 BY-SA 版权协议, 转载请标明出处
Loading Comments...
0%