素数判断

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$ 的空缺(按照前两种情景选择方法处理)

认识树结构

1、树：指有层次关系的 $N$ 个节点的有限集合(如下图)；对于空树，$N = 0$ ；对于非空树，有且仅有一个根。除根外，可分为多个互不相交的有限集合，称为子树
2、节点：每个数据就是一个节点。节点可分为根节点、分支节点、叶子结点。在两个节点的关系上分为前驱(父节点)和后继(子节点)
3、在树中：边用来表明两个节点之间的层次关系(父子关系)；高度指的是深度(层次)，树的高度指的是整个树最深的层次数，如下图 $E$ 的高度为 $3$ ，树的高度为 $4$ ；度指的是边的个数(子节点的个数)，树的度指的是整个树各节点度的最大值，如下图 $A$ 的度为 $3$，$C$ 的度为$1$，树的度为 $3$

引入

1、对于模意义下的运算，例如我们知道有 $(a + b) \bmod p = (a \bmod p) + (b \bmod p)$ 或者 $(a * b) \bmod p = (a \bmod p) * (b \bmod p)$ 成立，但是对于模意义下的除法却不成立：$(a / b) \bmod p \not= (a \bmod p) / (b \bmod p)$ 。不过，我们可以把模意义的除法转换成模意义的乘法
2、举例探讨：$(7 / 2) \bmod 5$ 中，把除法转成乘法写作 $(7 * \frac{1}{2}) \bmod 5$ ，再将分数写成幂的形式写作 $(7 * 2^{-1}) \bmod 5$
3、由于取模运算的结果一定是整数，所以 $(7 * 2^{-1}) \bmod 5$ 结果一定是整数，即说明必定能把 $2^{-1}$ 这个分数转换成某个整数。所以，问题的关键就在于能转换成哪个整数
4、这时便需要引入乘法逆元的概念了，它可以辅助我们完成模意义的除法到模意义的乘法的转换

欧几里得算法

1、求两个数的最大公约数，除了分解质因数法，我们通常使用欧几里得算法(即辗转相除法)，其思路如下
2、求 $m, n$ 的最大公约数，就计算 $m \div n$，然后令 $m = n$、$n = m \bmod n$ ，继续循环计算。直到 $n = 0$ 时停止，这时的 $m$ 就是最大公约数；或者提前一步，到 $m \bmod n = 0$ (结果余数为 $0$)时停止，这时的 $n$ 就是最大公约数(推荐后者，在写拓展欧几里得算法时更方便)
3、gcd 的性质：$gcd(a, b) = gcd(a, ka + b)$ ；$gcd(ka, kb) = k \times gcd(a, b)$ ；$a \div gcd(a, b)$ 与 $b \div gcd(a, b)$ 互素；多个整数的最大公约数 $gcd(a, b, c) = gcd(gcd(a, b), c)$ ；$a \gt b$ 时，$gcd(a, b) = gcd(a, b-a)$

引入

1、假设我们要计算 $a^n$ 的值，最朴素的做法是循环 $n$ 次，每次在结果上乘以 $a$。显然这种做法的时间复杂度为 $O(n)$，但当 $n$ 非常大时这种做法的效率仍然较低，而快速幂可以解决这个问题
2、我们先从一个特例引入：当 $n$ 是 $2$ 的幂时，例如求 $a^{64}$ 的值，我们可以按照下表的方式计算。每次将上一次循环得到的结果自乘，就得到了指数为下一级 $2$ 的幂的结果，以此类推，便很快就能得到指数为所求 $2$ 的幂的结果
3、而对于任意的 $n$，例如求 $a^{105}$ 的值，我们可以将指数 $n$ 拆分成多个 $2$ 的幂之和，例如 $a^{105} = a^{1+8+32+64} = a^1 \times a^8 \times a^{32} \times a^{64}$ ，而单独计算这些幂便十分简单了，因此最终只需要将需要的 $2$ 的幂的结果相乘即可
4、因此，快速幂又称二进制取幂(平方法)，其英文为Binary Exponentiation，其时间复杂度仅需 $O(log_2 n)$ 对数级

离散化

1、对于元素个数不多、值域很大的有序无重复数列，且更关注数列的相对大小(而不是绝对大小)，可以使用离散化的方式优化程序。离散化本质上是一种哈希，即把一个数字映射为另一个数字
2、例如对于一个长 $100$ 的有序无重复数列 $\{1, 5, 20, \ldots, 10^{18}\}$ (元素最大值为 $10^{18}$)，只判断相对大小关系，可将其映射为 $\{0, 1, 2, \ldots, 99\}$，便可以代表所需要的相对大小信息
3、离散化通常可以将大数组的零散数据映射到小数组中。例如存储一条 $10^9$ 的数轴上的点的值，但却只有较少数据量的一些零散数据，如 $\{[0]:3, [4]:7, [11]:4, [10000]:21\}$ ，如果开辟 $10^9$ 的数组会爆栈无法开辟。如果使用时只关注下标的相对大小，最好的办法是将有数据的点按照下标离散化为 $\{[0]:3, [1]:7, [2]:4, [3]:21\}$ ，这样便存储到了小数组中

例题引入

1、给定一个已知序列且数组元素都是正数(例如 $\{2, 3, 1, 2, 4, 3\}$)，再给定一个 $target$(例如 $7$)，从中找出最短的一个子序列，使子序列的和 $\geq target$，输出最短子序列的长度
2、普通的暴力做法是两层循环分别枚举子序列的左右端点，显然这样的时间复杂度为 $O(n^2)$，运行速度很慢
3、另一种思路是使用双指针：由于数组元素都是正数，因此当子序列向右延伸时和一定递增。我们先以 $[0, 3]$ 为第一个子序列，和为 $8$；向右移动左指针，发现 $[1, 3]$ 和为 $6$ 不满足条件，便向右移动右指针指向 $[1, 4]$ ，和为 $10$；继续向右移动左指针，发现 $[2, 4]$ 和为 $7$ 满足条件；以此类推直至末尾。最终发现最短子序列是 $[4, 5]$ 长度为 $2$
4、这种思路下，左右指针都不需要向左回退，因此两个指针都最多只需要遍历一次数列，时间复杂度为 $O(n)$