数据结构
type
status
date
slug
summary
tags
category
icon
password
类别
内容
单链表
双链表
栈
队列
单调栈
单调队列
KMP
Trie
并查集
堆
平衡树
可持久化数据结构
树状数组
哈希表
树链剖分
树套树
线段树
ST表
二维/动态开点线段树
动态树
单链表
双链表
栈
队列
单调栈
单调队列
KMP
并查集
并查集的代码简短，且思路巧妙
基本原理
- 每个集合用一个树来表示
- 树根的编号就是整个集合的编号
- 每个节点存储它的父节点，p[x]表示x的父节点
并查集的作用：
- 将两个集合合并
- 询问两个元素是否在同一个集合当中（在近乎O(1)的时间里）
实现步骤
- 在数据输入时，直接将每个树都表示一个单独的数
- find找根节点：通过不断的递归寻找自己的父亲节点，找到自己的祖宗节点，知道自己属于哪个集合
- 优化：在不断递归寻找祖宗节点的同时，进行路径压缩优化
- 当需要合并两个集合时，直接找到祖宗节点，更换祖宗节点的父亲节点
可以通过一些额外的空间，来存储集合中的相关消息，如集合中元素个数等
堆
堆本质上是一个完全二叉树，因此可以通过一个一维数组来存储一个堆
- 父节点：x
- 左子节点:2x
- 右子节点：2x + 1
不同的是，堆中的每个元素是由大小关系的
堆的分类：
- 大根堆：父节点的值大于左右子节点的值
- 小根堆：父节点的值小于左右子节点的值
堆的两个重要操作：
- up
- down
经典题---堆排序
模拟堆
哈希表
ST表
ST表（Sparse Table， 即稀疏表）
主要用来解决RMQ（区间最大/最小值查询）问题。主要应用倍增思想，可以实现O(nlogn)预处理、O(1)查询。
- 预处理ST表
倍增法递推：用两个等长小区间拼凑一个大区间
示意图如下：
- 处理询问
对查询区间[l, r]做分割、拼凑。
推理如下：
重点是：要保证两个区间可以完全覆盖查询区间，从而做到不漏元素
凡是符合结合律且可重复贡献的信息查询都可以使用ST表。
显然最大值、最小值、最大公因数、最小公倍数、按位或、按位与 都符合这个条件。
但如果涉及区间修改操作，就要使用线段树。
线段树
- 线段树是一个二叉树，树状数组能完成的任务线段树都能做
- 线段树数据结构示意图：
线段树主要解决下面几类问题：
- 单点修改，区间求值
- 区间修改，单点求值
- 区间修改，区间查询
区间修改，单点求值
区间修改，区间查询
Last update: 2024-04-07
🎉此博客仅为本人记录生活，技术交流所用🎉
-- 如有侵权，请与我联系 ---
-- 感谢您的支持😁 ---