精心整理2万字c++知识点

admin管理员组

文章数量:1533915

制作不易，求一键三连~

文章目录

• 1、基本数据结构
• • 数组
  • 链表
  • 队列、单调队列、双端队列
  • 栈
• 2、中极数据结构
• • 堆
  • 并查集与带权并查集
  • hash表
  • • 自然溢出
    • 双hash
• 3、高级数据结构
• • 树状数组
  • 线段树及其合并
  • • Zkw线段树
    • Fhq线树
    • 超哥线段树
  • 平衡树
  • • Treap随机平衡二叉树
    • Splay伸展树
    • Scapegoat Tree替罪羊树
    • 后缀平衡树
  • 块状数组、块状链表
  • 树套树
  • • 线段树套线段树
    • 线段树套平衡树
    • 平衡树套线段树
  • 可并堆
  • • 左偏树
    • 配对堆
  • KDTree、四分树
  • 舞蹈链（DLX）、二进制分组
  • 划分树
• 4、可持久化数据结构
• • 可持久化线段树（主席树）
  • 可持久化平衡树
  • 可持久化块状数组
• 5、字符串相关算法及数据结构
• • KMP
  • AC自动机
  • 后缀数组
  • 后缀树
  • 后缀自动机
  • 字典树Trie
  • Manacher
• 6、图论相关
• • 最小生成树
  • • Prim
    • Kruskal
  • 最短路、次短路、K短路
  • • Spfa
    • Dijkstra
    • Floyd
  • 图的联通
  • • 连通分量
    • 割点、割边
  • 网络流
  • • 最大流
    • 最小割
    • 费用流
    • 分数规划
  • 树相关
  • • 树上倍增、公共祖先
    • 树链剖分
    • 树的分治算法（点分治、边分治、动态树分治）
  • 动态树（LCT、树分块）
  • 虚树
  • prufer编码
  • 拓扑排序
  • 欧拉图
  • 二分图
  • • KM算法
    • 匈牙利算法
  • 仙人掌算法
• 7、数学相关
• • （扩展）欧几里得算法、筛法、快速幂
  • • 斐蜀定理
    • 更相减损术
  • 欧拉函数与降幂
  • 费马小定理
  • 排列组合
  • • Lucas定理
    • 杨辉三角
  • 乘法逆元
  • 矩阵乘法
  • 数学期望与概率
  • 博弈论
  • • Sg函数
    • 树上删边游戏
  • 拉格朗日乘子法
  • 中国剩余定理
  • 线性规划与网络流
  • 辛普森积分
  • 模拟线性方程组
  • 容斥原理与莫比乌斯反演
  • 快速傅立叶变换
  • 大步小步BSGS法（扩展）
  • 高斯消元
  • 线性筛
  • Min25筛与杜教筛
  • 母函数
  • Burnside引理与Polya计数
  • Miller-Robin素数检测
  • Pollard大数分解
• 8、动态规划
• • 基础形式（记忆化搜索、斯坦纳树、背包九讲）
  • • 背包dp
    • 线性dp
    • 区间dp
    • 状压dp
    • 环形dp
    • 树形dp
    • 数位dp
    • 倍增dp
    • 插头dp
  • 斜率优化与四边形不等式优化
  • 环+外向树上的dp
• 9、计算几何
• • 计算几何基础
  • 三位计算几何初步
  • 梯形剖分与三角形剖分
  • 凸包
  • 旋转卡壳
  • 半平面交
  • pick定理
  • 扫描线
• 10、搜索相关
• • dfs、bfs
  • A*算法
  • 迭代加深搜索（IDA*）、双向广搜
• 11、特殊算法
• • 莫队算法、树上莫队
  • 模拟退火
  • 爬山算法
  • 随机增量算法
• 12、其他重要工具与方法
• • 模拟与贪心
  • 二分法、三分法（求偏导）
  • 分治、CDQ分治
  • 高精度
  • 离线
  • ST表
• 13、STL
• • map
  • priority_queue
  • set
  • bitset
  • rope
• 14、非常见算法
• • 朱刘算法
  • 弦图与区间图

1、基本数据结构

数组

数组（Array）是有序的元素序列。 [1] 若将有限个类型相同的变量的集合命名，那么这个名称为数组名。组成数组的各个变量称为数组的分量，也称为数组的元素，有时也称为下标变量。用于区分数组的各个元素的数字编号称为下标。数组是在程序设计中，为了处理方便， 把具有相同类型的若干元素按有序的形式组织起来的一种形式。 [1] 这些有序排列的同类数据元素的集合称为数组。
数组是用于储存多个相同类型数据的集合。

链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。链表可以在多种编程语言中实现。像Lisp和Scheme这样的语言的内建数据类型中就包含了链表的存取和操作。程序语言或面向对象语言，如C,C++和Java依靠易变工具来生成链表。

队列、单调队列、双端队列

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
单调队列，即单调递减或单调递增的队列。使用频率不高，但在有些程序中会有非同寻常的作用。
deque（double-ended queue，双端队列）是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，相比list增加[]运算符重载。

栈

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

2、中极数据结构

堆

堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。

并查集与带权并查集

并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中。其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，只能用并查集来描述。
并查集是一种树型的数据结构，用于处理一些不相交集合（disjoint sets）的合并及查询问题。常常在使用中以森林来表示。
带权并查集是普通并查集的进阶版本，功能更加强大。

普通并查集只能判断两个元素是否在一个集合中，带权并查集可以维护集合元素之间的关系，这个关系由每个元素的权值维护。

对权值的维护，我们需要在find()，unite()操作中分别进行修改。

hash表

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。

自然溢出

溢出哈希表是在hash 表填入过程中，将冲突的元素顺序填入到溢出表中，而当查找过程中发现冲突时，就在溢出表中进行顺序查找。

双hash

双重哈希属于开放地址哈希中的一种解决冲突方案，也就是说如果一次哈希不能解决问题的时候，要再次哈希

3、高级数据结构

树状数组

树状数组或二叉索引树（英语：Binary Indexed Tree），又以其发明者命名为Fenwick树，最早由Peter M. Fenwick于1994年以A New Data Structure for Cumulative Frequency Tables为题发表在SOFTWARE PRACTICE AND EXPERIENCE。其初衷是解决数据压缩里的累积频率（Cumulative Frequency）的计算问题，现多用于高效计算数列的前缀和， 区间和。

线段树及其合并

线段树合并说全来就是动态开点权值线段树合并，所以你需要掌握权值线段树的基本知识以及知道什么是动态开点

对于两个普通权值线段树如果暴力合并的话复杂度将会是n log ⁡n，更别说是合并n棵权值线段树了（炸空间、炸内存），但是在动态开点权值线段树中，这一操作是可以优化为log n的。

Zkw线段树

递归式线段树的常数很大，经常被卡，而zkw线段树的常数很小

Fhq线树

FHQ Treap，又名无旋Treap，是一种不需要旋转的平衡树，是范浩强基于Treap发明的。FHQ Treap具有代码短，易理解，速度快的优点。（当然跟红黑树等更高级的平衡树比一下就是……）至少它在OI中算是很优秀的数据结构了。

超哥线段树

超哥线段树，实际上是线段树的标记永久化。

平衡树

平衡树(Balance Tree，BT) 指的是，任意节点的子树的高度差都小于等于1。常见的符合平衡树的有，B树（多路平衡搜索树）、AVL树（二叉平衡搜索树）等。平衡树可以完成集合的一系列操作, 时间复杂度和空间复杂度相对于“2-3树”要低，在完成集合的一系列操作中始终保持平衡，为大型数据库的组织、索引提供了一条新的途径。 [1]
设“2-3 树”的每个结点存放一组与应用问题有关的数据, 且有一个关键字 (>0的整数) 作为标识。关键字的存放规则如下:对于结点X, 设左、中、右子树均不空, 则左子树任一结点的关键字小于中子树中任一结点的关键字;中子树中任一结点的关键字小于结点X的关键字;而X的关键字又小于右子树中任一结点的关键字, 称这样的“2-3树”为平衡树。[1]

Treap随机平衡二叉树

树堆（Treap）是二叉排序树（Binary Sort Tree）与堆（Heap）结合产生的一种拥有堆性质的二叉排序树。

Splay伸展树

Splay(伸展树)是一种二叉排序树，它能在O(log2 n)的时间内完成插入、查找和删除操作。

Splay(伸展树)能实现线段树不能实现的操作，比如区间翻转。

Splay的核心函数是旋转操作，将点x旋转至点k下面。特别的rotate (x, 0)表示把x旋转至根。旋转操作不会改变每个节点在该树的中序遍历中的位置。

旋转的目的：在每次查询、修改操作完，将操作的节点旋转到根，就像是输入法，常用的词汇会在第一页就出现，如果是第一次用，则需要翻好几页。可以保证均摊的时间复杂度为 [公式] 。

Scapegoat Tree替罪羊树

替罪羊树是计算机科学中，一种基于部分重建的自平衡二叉搜索树。在替罪羊树上，插入或删除节点的平摊最坏时间复杂度是O(log n)，搜索节点的最坏时间复杂度是O(log n)

后缀平衡树

如果需要动态维护后缀数组，支持在字符串前端插入一个字符，询问后缀的大小关系，如何做呢？

这是一个不断插入的问题，可以从增量的角度考虑。我们在前端插入一个字符，其实就是插入了一个新的后缀。我们的问题其实就是这个后缀排名多少。我们可以用平衡树维护一下后缀数组，从根节点开始二分比较这个后缀的大小，看看它应该被插到哪里。现在问题就变成了快速比较一个新的后缀和一个已有的后缀。

如果这个新的后缀和当前比较的后缀的首字符不同，那么比较结果是显然的；如果新的后缀和当前比较的后缀的首字符相同，那么问题就转化成了比较原来已有的两个后缀的大小关系。我们在平衡树的每个节点上维护一个值x∈[0,1]，代表它的大小，左儿子为的关键值为[l,mid]，右儿子的关键值为[mid,r]，那么只要直接比较这个值就可以啦。

然而如果平衡树的深度过大，那么这个值会爆实数的精度。所以我们采用深度为O(logn)的平衡树。但如果平衡树需要旋转，那么它的子树需要全部重新计算关键值。所以我们需要使用重量平衡树，其子树大小均摊O(logn)，所以每次插入旋转后整个子树重算一下。

块状数组、块状链表

块状数组，即把一个数组分为几个块，块内信息整体保存，若查询时遇到两边不完整的块直接暴力查询。一般情况下，块的长度为O(√n) 。

树套树

线段树套线段树

树套树写法还是比较好理解的，不过要是让自己硬套的话可能很不容易套出来的

这里的二维线段树，外层线段树是对方阵的正投影，而内层线段树是对方阵的侧投影

线段树套平衡树

线段树的作用是区间修改和查询，平衡树的作用是查询第k大，k的排名，前驱，后继。这两个结合起来，就变成了可以区间修改和查询第k大，k的排名，前驱，后继的数据结构：树套树-线段树套平衡树。

平衡树套线段树

线段树维护的是区间，然后对于线段树维护的区间的所有数字都维护一个平衡树，然后所有的操作都对每个平衡树单独处理。

可并堆

可并堆，顾名思义，就是可以合并的堆。堆满足一个性质，就是当前节点，都大于或者等于他的所有子树上的节点，自然在这里我所讲的是结点的权值。显而易见，既然可并堆是堆的一种，容易推出，可并堆也满足这个性质。

左偏树

左偏树（英语：leftist tree或leftist heap），也可称为左偏堆、左倾堆，是计算机科学中的一种树，是一种优先队列实现方式，属于可并堆，在信息学中十分常见，在统计问题、最值问题、模拟问题和贪心问题等等类型的题目中，左偏树都有着广泛的应用。斜堆是比左偏树更为一般的数据结构。

配对堆

配对堆是一种实现简单、均摊复杂度优越的堆数据结构，由Michael Fredman、罗伯特·塞奇威克、Daniel Sleator、罗伯特·塔扬于1986年发明。配对堆是一种多叉树，并且可以被认为是一种简化的斐波那契堆。对于实现例如普林姆最小生成树算法等算法，配对堆是一个更优的选择，

KDTree、四分树

kd-tree（k-dimensional树的简称），是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。 [1] 主要应用于多维空间关键数据的搜索（如：范围搜索和最近邻搜索）。K-D树是二进制空间分割树的特殊的情况。
在计算机科学里，k-d树（ k-维树的缩写）是在k维欧几里德空间组织点的数据结构。k-d树可以使用在多种应用场合，如多维键值搜索（例：范围搜寻及最邻近搜索）。k-d树是空间二分树（Binary space partitioning ）的一种特殊情况。 [2]

四分树就是用一个类似于线段树的东西来维护一个矩阵，就是每个点有四个儿子
然后每个儿子代表切分之后的一块区域

舞蹈链（DLX）、二进制分组

舞蹈链（Dancing Links）算法在求解精确覆盖问题时效率惊人。

二进制分组就是把操作的数量二进制拆分，每个二进制位数用数据结构维护
合并的时候，暴力重构
每次查询，从logn个块依次用维护的数据结构查询

划分树

划分树定义为,它的每一个节点保存区间[lft,rht]所有元素,元素顺序与原数组(输入)相同,但是,两个子树的元素为该节点所有元素排序后(rht-lft+1)/2个进入左子树,其余的到右子树,同时维护一个num域,num[i]表示lft->i这个点有多少个进入了左子树。

4、可持久化数据结构

可持久化线段树（主席树）

主席树，也叫做可持久化线段树，准确来说，应该叫做可持久化权值线段树，因为其中的每一颗树都是一颗权值线段树。

所谓权值线段树，就是指线段树的叶子节点保存的是当前值的个数。这样说起来比较抽象，下面用具体例子来简单阐述。

可持久化平衡树

treap = tree + heap，即同时满足二叉搜索树和堆的性质。

为了使树尽可能的保证两边的大小平衡，所以有一个key值，使他满足堆得性质，来维护树的平衡，key值是随机的。
treap有一般平衡树的功能，前驱、后继、第k大、查询排名、插入、删除。也比较好写

可持久化块状数组

题目中要求可以查询历史状态，最暴力的想法是开a[m][n]的二维数组，每次修改暴力复制并修改，每次查询暴力扫描，时间复杂度是O(mn)的，

本文标签： 知识点万字精心