算法基础
\(\text{Update: 2024 - 07 - 22}\)
复杂度
定义
衡量一个算法的快慢，一定要考虑数据规模的大小。
一般来说，数据规模越大，算法的用时就越长。
而在算法竞赛中，我们衡量一个算法的效率时，最重要的不是看它在某个数据规模下的用时，而是看它的用时随数据规模而增长的趋势，即时间复杂度。
符号定义
相等是\(\Theta\)，小于是\(O\)，大于是\(\Omega\)。
大\(\Theta\)符号
对于函数\(f(n)\)和\(g(n)\)，\(f(n)=\Theta(g(n))\)，当且仅当\(\exists c_1,c_2,n_0>0\)，使得\(\forall n \ge n_0, 0\le c_1\cdot g(n)\le f(n) \le c_2\cdot g(n)\)。
大\(O\)符号
\(\Theta\)符号同时给了我们一个函数的上下界，如果只知道一个函数的渐进上界而不知道其渐进下界，可以使用\(O\)符号。\(f(n) = O(g(n))\)，当且仅当\(\exists c,n_0\)，使得\(\forall n \ge n_0,0\le f(n)\le c\cdot g(n)\)。
研究时间复杂度时通常会使用\(O\)符号，因为我们关注的通常是程序用时的上界，而不关心其用时的下界。
大\(\Omega\)符号
同样的，我们使用\(\Omega\)符号来描述一个函数的渐进下界。\(f(n) = \Omega(g(n))\)，当且仅当\(\exists c, n_0\)，使得\(\forall n \ge n_0, 0 \le c \cdot g(n) \le f(n)\)。
主定理
建议背下来，不是很好理解。
那么
需要注意的是，这里的第二种情况还需要满足\(\text{regularity condition}\), 即 \(a f(n/b) \leq c f(n)\)，\(\text{for some constant}\)\(c < 1\)\(\text{and sufficiently large}\)\(n\)。
几个例子：
\(T(n) = 2T(\frac{n}{2}) + 1\)，那么\(a = 2, b = 2, {\log_2 2} = 1\)，那么\(\epsilon\)可以取值在\((0, 1]\)之间，从而满足第一种情况，所以\(T(n) = \Theta(n)\)。
\(T(n) = T(\frac{n}{2}) + n\)，那么\(a = 1, b = 2, {\log_2 1} = 0\)，那么\(\epsilon\)可以取值在\((0, 1]\)之间，从而满足第二种情况，所以\(T(n) = \Theta(n)\)。
\(T(n) = T(\frac{n}{2}) + {\log n}\)，那么\(a = 1, b = 2, {\log_2 1} = 0\)，那么\(k\)可以取值为\(1\)，从而满足第三种情况，所以\(T(n) = \Theta(\log^2 n)\)。
\(T(n) = T(\frac{n}{2}) + 1\)，那么\(a = 1, b = 2, {\log_2 1} = 0\)，那么\(k\)可以取值为\(0\)，从而满足第三种情况，所以\(T(n) = \Theta(\log n)\)。
空间复杂度
类似地，算法所使用的空间随输入规模变化的趋势可以用空间复杂度来衡量。
枚举
实际上一些题的正解就是枚举，但需要很多优化。
要点：
建立简洁的数学模型。
减少不必要的枚举空间。
选择合适的枚举顺序。
模拟
模拟即为将题目描述中的操作用代码实现，码量一般比较大，写错比较难调，相当浪费时间。
写模拟题时有以下注意的点：
在写代码之前，尽量在演草纸上自习分析题目的实现过程。
在代码中尽量把每个部分抽离出来写成函数，模块化。
将题目中的信息转化，不要残留多种表达。
如果一次没过大样例，分块调试。
实现代码时按照演草纸上的思路一步步实现。
递归
定义
我们可以用以下代码理解递归：
long long f(传入数值) { if(终止条件) return 最小子问题解; return f(缩小问题规模);}递归的优点
- 结构清晰、可读性强，可以参考归并排序的两种实现方式。
- 练习分析为题的结构，当发现问题可以分解成相同结构的小问题时，递归写多了就能敏锐发现这个特点，进而高效解决问题。
递归的缺点
在程序执行中，递归是利用堆栈来实现的。每当进入一个函数调用，栈就会增加一层栈帧，每次函数返回，栈就会减少一层栈帧。而栈不是无限大的，当递归层数过多时，就会造成栈溢出的后果。
显然有时候递归处理是高效的，比如归并排序；有时候是低效的，比如数孙悟空身上的毛，因为堆栈会消耗额外空间，而简单的递推不会消耗空间。比如这个例子，给一个链表头，计算它的长度：
// 典型的递推遍历框架int size(Node *head) { int size = 0; for (Node *p = head; p != nullptr; p = p->next) size++; return size;}// 我就是要写递归，递归天下第一int size_recursion(Node *head) { if (head == nullptr) return 0; return size_recursion(head->next) + 1;}
递归优化见后文搜索优化和记忆化搜索。
要点
明白一个函数的作用并相信它能完成这个任务，千万不要跳进这个函数里面企图探究更多细节，否则就会陷入无穷的细节无法自拔，人脑能压几个栈啊。
递归与枚举的区别
枚举是横向地把问题划分，然后依次求解子问题；而递归是把问题逐级分解，是纵向的拆分。
递归与分治的区别
递归是一种编程技巧，一种解决问题的思维方式；分治算法很大程度上是基于递归的，解决更具体问题的算法思想。
分治
定义
就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
过程
分治算法的核心思想就是「分而治之」。
大概的流程可以分为三步：分解\(\to\)解决\(\to\)合并。
分解原问题为结构相同的子问题。
分解到某个容易求解的边界之后，进行递归求解。
将子问题的解合并成原问题的解。
分治法能解决的问题一般有如下特征：
该问题的规模缩小到一定的程度就可以容易地解决。
该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质，利用该问题分解出的子问题的解可以合并为该问题的解。
该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
注意：如果各子问题是不独立的，则分治法要重复地解公共的子问题，也就做了许多不必要的工作。此时虽然也可用分治法，但一般用动态规划较好。
贪心
适用范围
贪心算法在有最优子结构的问题中尤为有效。
最优子结构的意思是问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。
证明
贪心算法有两种证明方法：反证法和归纳法。
一般情况下，一道题只会用到其中的一种方法来证明。
反证法：如果交换方案中任意两个元素/相邻的两个元素后，答案不会变得更好，那么可以推定目前的解已经是最优解了。
归纳法：先算得出边界情况（例如\(n = 1\)）的最优解\(F_1\)，然后再证明：对于每个\(n\)，\(F_{n + 1}\)都可以由\(F_{n}\)推导出结果。
常见题型
在提高组难度以下的题目中，最常见的贪心有两种。
「我们将\(XXX\)按照某某顺序排序，然后按某种顺序（例如从小到大）选择。」。
「我们每次都取\(XXX\)中最大/小的东西，并更新\(XXX\)。」（有时「\(XXX\)中最大/小的东西」可以优化，比如用优先队列维护）
二者的区别在于一种是离线的，先处理后选择；一种是在线的，边处理边选择。
排序解法
用排序法常见的情况是输入一个包含几个（一般一到两个）权值的数组，通过排序然后遍历模拟计算的方法求出最优值。
后悔解法
思路是无论当前的选项是否最优都接受，然后进行比较，如果选择之后不是最优了，则反悔，舍弃掉这个选项；否则，正式接受。如此往复。
排序
几种排序算法的比较
一张表格速通
| 排序方法 | 平均情况 | 最好情况 | 最坏情况 | 空间 | 稳定性 |
|---|---|---|---|---|---|
| 选择排序 | \(O(n^2)\) | \(O(n^2)\) | \(O(n^2)\) | \(O(1)\) | 不稳定 |
| 冒泡排序 | \(O(n^2)\) | \(O(n)\) | \(O(n^2)\) | \(O(1)\) | 稳定 |
| 插入排序 | \(O(n^2)\) | \(O(n)\) | \(O(n^2)\) | \(O(n)\) | 稳定 |
| 计数排序 | \(O(n + w)^1\) | \(O(n + w)\) | \(O(n + w)\) | \(O(n + w)\) | 稳定 |
| 基数排序 | \(O(kn + \sum\limits_{i = 1}^{k} w_i)^2\) | \(O(kn + \sum\limits_{i = 1}^{k} w_i)\) | \(O(kn + \sum\limits_{i = 1}^{k} w_i)\) | \(O(n + k)\) | 稳定 |
| 快速排序 | \(O(n \log n)\) | \(O(n \log n)\) | \(O(n^2)\) | \(O(\log n) \sim O(n)\) | 不稳定 |
| 归并排序 | \(O(n \log n)\) | \(O(n \log n)\) | \(O(n \log n)\) | \(O(n)\) | 稳定 |
| 堆排序 | \(O(n \log n)\) | \(O(n \log n)\) | \(O(n \log n)\) | \(O(1)\) | 不稳定 |
| 桶排序 | \(O(n + \frac{n^2}{k} + k)^3\) | \(O(n)\) | \(O(n^2)\) | \(O(n + m)^4\) | 稳定 |
| 希尔排序 | \(O(n \log n) \sim O(n^2)\) | \(O(n^{1.3})\) | \(O(n^2)\) | \(O(1)\) | 不稳定 |
| 锦标赛排序 | \(O(n \log n)\) | \(O(n \log n)\) | \(O(n \log n)\) | \(O(n)\) | 稳定 |
| \(\text{tim}\)排序 | \(O(n \log n)\) | \(O(n)\) | \(O(n \log n)\) | \(O(n)\) | 稳定 |
\(^1\)：其中\(w\)为排序元素的值域。
\(^2\)：其中\(k\)为排序元素的最大位数，\(w_i\)为第\(i\)个关键字的值域。
\(^3\)：其中\(k\)表示将\(n\)个元素放进\(m\)个桶中，每个桶的数据为\(k = \frac{n}{m}\)。
\(^4\)：其中\(m\)表示将\(n\)个元素放进的\(m\)个桶。
前缀和
定义
前缀和可以简单理解为「数列的前\(\text{i}\)项的和」，是一种重要的预处理方式，能大大降低查询的时间复杂度。
一维前缀和
预处理递推式为：
查询\([l, r]\)的数值：
二维前缀和
预处理递推式为：
查询\((i, j) \sim (k, w)\)的数值：
树上前缀和
设\(s_i\)表示结点\(i\)到根节点的权值总和。
若是点权，\(x, y\)路径上的和为\(s_x + s_y - s_{lca} - s_{fa_{lca}}\)
若是边权，\(x, y\)路径上的和为\(s_x + s_y - 2 \times s_{lca}\)
差分
定义
差分是一种和前缀和相对的策略，可以当作是求和的逆运算。
这种策略的定义是令\(b_i = \begin{cases} a_i - a_{i - 1} \, &i \in[2, n] \\ a_1 \, &i = 1 \end{cases}\)
性质
\(a_i\)的值是\(b_i\)的前缀和，即\(a_n = \sum\limits_{i = 1}^n b_i\)。
计算\(a_i\)的前缀和\(sum = \sum\limits_{i = 1}^n a_i = \sum\limits_{i = 1}^n \sum\limits_{j = 1}^{i} b_j = \sum\limits_{i = 1}^n (n - i + 1) b_i\)。
它可以维护多次对序列的一个区间加上一个数，并在最后询问某一位的数或是多次询问某一位的数。注意修改操作一定要在查询操作之前。
树上差分
树上差分可以理解为对树上的某一段路径进行差分操作，这里的路径可以类比一维数组的区间进行理解。例如在对树上的一些路径进行频繁操作，并且询问某条边或者某个点在经过操作后的值的时候，就可以运用树上差分思想了。
树上差分通常会结合树基础和最近公共祖先来进行考察。树上差分又分为点差分与边差分，在实现上会稍有不同。
点差分
举例：对树上的一些路径\(\delta(s_1, t_1), \delta(s_2, t_2), \delta(s_3, t_3)\dots\)进行访问，问一条路径\(\delta(s, t)\)上的点被访问的次数。
对于一次\(\delta(s, t)\)的访问，需要找到\(s\)与\(t\)的公共祖先，然后对这条路径上的点进行访问（点的权值加一），若采用\(\text{DFS}\)算法对每个点进行访问，由于有太多的路径需要访问，时间上承受不了。这里进行差分操作：
其中\(f(x)\)表示\(x\)的父亲节点，\(d_i\)为点权\(a_i\)的差分数组。
可以认为公式中的前两条是对蓝色方框内的路径进行操作，后两条是对红色方框内的路径进行操作。不妨令\(\textit{lca}\)左侧的直系子节点为\(\textit{left}\)。那么有\(d_{\textit{lca}} - 1 = a_{\textit{lca}} - (a_{\textit{left}} + 1)\)，\(d_{f(\textit{lca})} - 1 = a_{f(\textit{lca})} - (a_{\textit{lca}} + 1)\)。可以发现实际上点差分的操作和上文一维数组的差分操作是类似的。
边差分
若是对路径中的边进行访问，就需要采用边差分策略了，使用以下公式：
由于在边上直接进行差分比较困难，所以将本来应当累加到红色边上的值向下移动到附近的点里，那么操作起来也就方便了。对于公式，有了点差分的理解基础后也不难推导，同样是对两段区间进行差分。