Dijkstra 朴素算法

1、最短路 1：给定 $n$ 个点 $m$ 条边的有向图($n \leq 1000$)，输出点 $1$ 到 $n$ 的最短距离。对于 $m$ 条边，每次输入 $u、v、w$ ，表示存在一条从 $u$ 到 $v$ 的权值为 $w$ 的有向边。如果不存在路径，输出 $-1$
2、先前在图与回溯中介绍过权值相等最短路(无权最短路)，现在有了权值，需要做一个结构体保存。Dijkstra还使用一个数组 $d[]$ ，$d[i]$ 表示从起点 $st$ 到 $i$ 的最短距离
3、Dijkstra 思路如下图：起始时，建图，标记所有 $d[i]$ 为 $\infty$，以 $1$ 为起点，向外走一层，将经过的边松弛(用边的权值更新所到点的 $d[i]$ ，$d[i]$ 取较小值)；接下来，比较得到最小的 $d[i]$ ，以该点为当前起点(图中为点 $2$)，先前的点已经可以忽略，继续向外走一层，将经过的边松弛(注意，$d[3]$ 取较小值更新为 $3$)；以此类推，以 $4$ 为当前起点发现点 $4$ 没有出点，返回；以 $3$ 为当前起点，走到终点，更新 $d[5]$ 为 $6$，所以最短路为 $6$
4、该算法结合了贪心和DP的思想，每个点只拓展一次，且拓展时已为最短距离

并查集

1、并查集是一种支持合并和查询操作的集合形式的数据结构，它支持两个集合的合并，并可以查询点与点之间的连通关系
2、并查集只需要一个数组 $pre[]$ 存储点的前导点(父节点)，在初始化时 $pre[i] = i$ ，表示点与自己连通，是单独的连通块，该功能由 $init()$ 函数完成。并查集中还需要一个函数 $root(u)$ ，该操作将找到点 $u$ 所属的连通块(的根节点)。该函数将递归查找 $u$ 的父节点，直至找到根节点
3、对于两个点 $u$ 和 $v$ 的合并操作，只需要将 $u$ 和 $v$ 所属的连通块的其中一个根指向另一个根，即 $pre[root(u)] = root(v)$ ；对于两个点 $u$ 和 $v$ 的查询操作，只需要判断 $u$ 和 $v$ 所属的连通块的根是否相同
4、但前述 $root(u)$ 函数的朴素算法每次都需要查找一整条父节点链，效率太低，可以通过路径压缩优化程序： pre[u] = (pre[u] == u ? u : root(pre[u]))，这样同一连通块在第一次查找后，每个节点都将直接指向当前根节点，提高以后查找的效率，时间复杂度接近 $O(1)$

树状数组

1、树状数组常用于维护区间和，有以下操作：单点修改 $O(\log n)$，区间修改 $O(\log n)$，区间查询 $O(\log n)$
2、树状数组的结构如下图，注意树状数组中一定不能用下标 $0$ 。$T[i]$ 所存的值为管辖区间的和，$T[i]$ 所覆盖的管辖区间为 $[i - lowbit(i) + 1, i]$ ，管辖区间长度为 $lowbit(i)$
3、$lowbit(i)$ 表示 $i$ 的二进制只保留最后一位 $1$ 的结果(例如二进制 $1101100$ 只保留后三位变为 $100$)，公式为 $lowbit(x) = x \land -x$

单调栈

1、在栈的基础上，如果保持栈内元素是有序的，则称为单调栈，分为单调递增栈和单调递减栈
2、通常单调栈主要用于求位置最近的更大值或更小值，我们将在具体样例中分析

适用前提

1、简言之：可以找到一个局部最优解；可以从局部最优解推广到全局最优解
2、严谨地说，两个条件分别是最优子结构和贪心选择性质
3、一般来说，贪心法往往是将某个东西排序，或者用堆(优先队列)等数据结构，每一步都取局部最优解，进而得到全局最优解

邻接表

1、在计算机中，图的存储方式有多种，最常用的是邻接表和邻接矩阵。邻接矩阵由于适用范围很小，故一般不考虑这种写法
2、出度：如下图便是一幅有向图，其中一个节点指向的其他节点称为这个节点的出度，指向出度节点的路径称为这个节点的出边。如下图中 $2$、$5$ 为 $1$ 的出度
3、邻接表：就是将一个点的所有出点(邻接点)保存在一个数组中；拓展的过程，也就是遍历这个数组的过程。这个数组我们称为邻接表

素数判断

1、最简单的判断质数的方式，便是从 $2 \to x$ 依次尝试，如果尝试到有因子，则其不是质数。需要特判 $2$ 为质数、小于 $2$ 的都不是质数(质数范围是大于 $1$ 的自然数)
2、朴素筛法可以简单进行优化，实际需要尝试的因子最多只到 $\sqrt{x}$ 。比如判断 $25$ 时，易知只需要判断 $2 \to 5$ 有没有因子，因此不需要重复判断 $\gt \sqrt{x}$ 的因子。提前使用变量记录 $\sqrt{x}$ ，可以避免循环中重复计算sqrt的开销
3、但假如要计算 $2 \to 10^6$ 中有多少个质数时，只使用素数判断的效率很低($10^6$ - $218ms$)，其额外判断了大量无用的数据，所以需要效率更高的筛法

二叉查找树

1、二叉查找树：又称二叉排序树/二叉搜索树，其任意节点与其左右子节点的大小关系都有左 < 中 < 右，其中序遍历会得到一个递增序列，常用于元素的排序和查找，如下图
2、查找元素：二叉查找树是以二分查找为原型的数据结构，因此其查找操作的时间复杂度为 $O(\log_2 n)$ 。其查找元素的动作为从根节点起，如果要查找的值比根小，则继续查找左子树，否则查找右子树
3、插入元素：与查找元素类似。如在下面的二叉查找树中插入新元素 $12$ ，应放在元素 $11$ 的右子节点处(从根节点依次比较 $12$ 与 $10$、$13$、$11$ 的关系)
4、删除元素：实质是保持中序遍历(即递增序列)的顺序不变从中删除节点，重点在于如何填补空缺。如下图展示了三棵二叉树，分别代表三种删除情景：情景一要删除节点 $6$(只有一边子树)，可以直接将子树整体上移；情景二要删除节点 $7$(两边都有子树)，可以将其中序遍历的前/后一个节点(即节点 $6$ 或 $8$)填充到此处；情景三要删除节点 $10$，如果选择填充节点 $14$(其仍有子树)，则还应递归处理 $14$ 的空缺(按照前两种情景选择方法处理)