基础算法

基础因人而异，下面罗列的是个人认为相对基础的知识点。只有熟练掌握了以下基础算法，才有可能理解更复杂的算法从而解出更高难度的问题。

贪心

贪心算法其实并不简单，很多时候需要敢想敢猜并且证明往往并不容易，但因为这种方法套路不多，就放在第一个基础算法部分展开。

贪心考虑的是局部最优，即每次做决策时都是选当前的局部最优解。当然，如果可以举出贪心后的反例，就可以考虑使用动态规划等其他全局性的策略来解决问题了。

对于贪心问题的证明，我总结出了两个证明方法。如下：

反证法：假设取一种方案比贪心方案更好，得出相反的结论；
边界法：从边界开始考虑，因为满足边界条件更加容易枚举，从而进行后续的贪心。

前缀和与差分

前缀和与差分是两类算法，但由于是相辅相成的关系，故将其列在一起。两种算法的适用场景如下：

前缀和算法适用于「频繁求子数组之和、不频繁修改数组元素」的场景；
差分算法适用于「频繁增减子数组元素值、不频繁求数组元素」的场景。

更精简地说：

前缀和算法适用于「频繁区间查询、不频繁单点修改」的场景；
差分算法适用于「频繁区间修改、不频繁单点查询」的场景。

Tip

如果需要同时频繁地「区间修改、区间查询」，可以使用进阶数据结构诸如树状数组或线段树来实现。

前缀和算法

为了学习差分算法，我们有必要先学习前缀和算法。具体地，对于一个长度为 $n$ 的数组 $a$，我们定义 $s_i$ 表示： $$ s_i=\sum_{j=0}^{i}a_j $$

那么当进行区间查询求解数组中下标在闭区间 $[p,q]$ 中的元素和时，只需要 $s_q-s_{p-1}$ 地 $O(1)$ 计算出来即可。我们称 $s$ 为数组 $a$ 的前缀和数组。为了维护出 $s$，我们采用递推算法。即：

\[ s_i= \begin{cases} a_0,&i=0\\ s_{i-1}+a_i,&i\ge1 \end{cases} \]

差分算法

为了实现给数组中下标在闭区间 $[i,j]$ 中的元素 $s_{i\sim j}$ 同时增加 $x$，我们可以借助前缀和算法的思路来实现。具体地，仍然记原始数组为 $a$，前缀和数组为 $s$，如果将 $a_i+x$ 同时 $a_{j+1}-x$，那么在维护前缀和数组 $s$ 时，$s_{i\sim j}$ 中的每一个元素就都增加了 $x$。

利用上述思路，我们可以将待操作的数组看做已经维护好的前缀和数组 $s$，并利用 $a_i=s_i-s_{i-1}$ 计算出差分数组 $a$，后续如果需要频繁地给待操作数组进行区间修改，只需要 $O(1)$ 地修改差分数组的两个边界即可。

综上所述：

前缀和算法高效的前提是数组元素尽可能保持不变，如果需要频繁变动数组元素，利用前缀和算法进行区间求和就不合适了；
差分算法高效的前提是不需要频繁的索引数组元素，如果需要频繁索引数组元素，利用差分算法进行区间修改就不合适了。

二分

二分本质上就是对「具有单调性的序列」进行加速查询的操作。假设有一个含有 $n$ 个元素的序列 $a$，其属性 $attr$ 是单调递增的。现在想要查询属性 $attr$ 取值为 $tar$ 的元素在序列中的位置。显然我们可以遍历一边序列 $a$ 并逐个比较即可，但由于属性 $attr$ 是单调的，在下标范围为 $[l,r]$ 的序列中查找时，只需要不断比较 $tar$ 和 $a_{(l+r)/2}$ 的值即可，具体地：

如果 $tar < a_{(l+r)/2}$，那么答案一定在 $[l,(l+r)/2]$ 中；
如果 $tar > a_{(l+r)/2}$，那么答案一定在 $[(l+r)/2,r]$ 中；
如果 $tar = a_{(l+r)/2}$，那么答案就是 $(l+r)/2$。

递归

递归是编程入门的最后一关，也是打开新世界的钥匙。所谓递归，就是让一个函数自己调用自己从而实现一系列诸如：搜索、分治等算法。

关于递归函数中调用自己的操作，你可以先不用 care 她到底是怎么执行的，你只需要关心她到底做了什么。比如现在有一个需求，需要封装一个函数 sum(x) 返回 $\sum_{i=1}^x,\ (x\ge 1)$ 的计算结果。你完全可以写出下面的程序：

int sum(int x) {
    int ans = 0;
    for (int i = 1; i <= x; i++) {
        ans += i;
    }
    return ans;
}

但如果使用递归，就可以不用 for 循环，比如下面的程序：

int sum(int x) {
    if (x == 1) {
        return 1;
    }
    return x + sum(x - 1);
}

你不需要关心 sum(x - 1) 到底发生了什么，你只需要知道她算出了 $\sum_{i=1}^{x-1}$，那么再加上 $x$ 就是$\sum_{i=1}^x$，是不是很简单？

当然，你一定发现了第三行的 return 语句，这是为了让函数递归调用自己时有一个终点。所有的递归函数都有一个终点，如果递归的终点是可控的，就可以不写 return 语句（比如在遍历图时），但上述程序的终点显然是不可控的，因为程序并不知道什么时候不需要再调用 sum(x - 1)。

推而广之，所有使用递归思想的算法都有同一套逻辑：

return_value function_name() {
    # 1. 递归终点
    # 2. 调用自己解决完全一样的逻辑但是规模更小的问题
}

现在可以学习使用递归逻辑的一系列算法了。

搜索

所谓搜索，就是在一个「解空间」中通过递归程序将所有可行解搜索出来的算法。这里的解空间可能有些抽象，我们就以一棵根树（可以简单查阅一下树的定义）为例。假设一个问题的解空间就是一棵根树（无环连通图，后用树代称），答案就存在树中的某些结点上。那么我们要做的就是遍历这棵树从而找到所有的可行解。

那么问题来了，怎么遍历？我们知道树有着很多优美的性质，比如以任意一个结点为根都对应了一棵和根树完全一样的结构，而这恰好满足前文所说的「逻辑完全一样但是规模更小」的递归性质。因此遍历一棵树只需要两个逻辑：

遍历当前结点；
遍历当前结点的所有子结点。

而这，就可以称作搜索。以上述树的搜索为例，就有下面的伪代码：

return_value search(node_index) {
    # 1. 遍历当前结点
    # 2. 遍历当前结点的所有子结点
}

没有返回值？确实。如果我们单纯的遍历一棵树，是不需要返回值的，因为当前结点的所有子结点都遍历结束后，程序就会开始回溯。相比于上面的 sum(x) 函数，这里的递归终点是已经存在的。

分治

分治是一个很有意思的递归算法。我们先不 care 分治算法是怎么样的。我们先看看校长是怎么惩罚翘课学生的：从最高的校长开始，ta 不 care 你上没上课，ta 只需要向各个学院的院长询问情况即可，而各个院长也不 care 你上没上课，ta 们只需要向所有年级的辅导员询问情况即可，而辅导员也不 care 你上没上课，ta 们只需要向所有的任课老师询问情况即可，任课老师上课点名了，你没来？那你有福了，任课老师和辅导员说你没来上课，辅导员和院长说你没来上课，院长和校长说你没来上课，校长知道了，那你彻底凉了（才怪）。

至此一个现实场景中的分治策略就淋漓精致地体现出来了。分治算法也是一个道理，只不过用代码模拟出来，仅此而已。所以为什么要这么干呢？本质上是因为通过这种方法可以将办事效率提升到最大。

当然聪明的你也一定发现了分治算法和上述递归算法中有一些类似的东西：比如校长向所有院长询问，所有院长向所有辅导员询问等等，这些其实都是更小规模的子问题。那么就可以套用递归的逻辑，不断调用自己即可。

但是这里有一个问题，每一级的工作人员都需要先拿到下一级工作人员传递的数据，整合以后才能往上一级传递。这就需要先让终点阶段的递归函数先执行，先前的递归函数才能继续执行。而这就是分治的精髓，先递归处理终点，再回溯传递数据。比如下面的伪代码：

return_value divide_and_conquer(stage) {
    # 1. 解决所有的子问题
    # 2. 联合处理所有子问题的结果
    # 3. 返回总结果
}

因此，分治算法可以总结为以下三个步骤：

divide。将待处理的问题划分为多个互斥的子问题；
conquer。递归处理子问题；
combine。联合子问题的处理结果得到最终的结果。

当然，如果一个问题无法拆分为多个互斥的子问题，分治算法就不适用了，此时可以采用更高效的动态规划算法来尝试解决。

排序

很多教程或教材都喜欢把这一块单独拿出来讲，可能因为排序算法是很多算法策略的具体实现。但这里有一些算法并不适合新手学习，如果遇到不怎么懂的排序策略，请先跳转到对应的知识点进行学习，之后再过来学习对应的排序算法会好很多。此处只讨论「快速排序」、「归并排序」和「堆排序」三种较为复杂的排序算法，其余排序算法请自行查阅。

首先讲一个排序衍生出的概念：稳定性。如果一个排序算法，在对所有元素排序后，原来相同关键字的顺序保持不变，则称该排序算法是稳定的，反之如果相同关键字的顺序改变了就称该排序算法是不稳定的。

快速排序

这是一种不稳定的排序算法，核心思想是分治。具体地，以升序为例，如果一个序列是有序的，那么对于该序列中的每一个元素，其左边所有元素都应该比右边所有元素小。基于该先验，我们就有了快速排序算法：

选择序列中任意一个元素作为基准；
基于该基准，扫描一遍序列将比基准小的元素排在基准的左边，比基准大的元素排在基准的右边；
递归左右两边的序列直到序列只有 1 个元素为止。

在计算时间复杂度时，我们可以将分治的逻辑想象成一棵二叉树，对于二叉树的每一层都会有 $O(n)$ 的遍历开销，而二叉树的层数平均有 $O(\log n)$ 层，因此排序的时间复杂度就是 $O(n\log n)$。当然如果每次选择的基准刚好是所在序列的最值，就会导致二叉树的层数退化到 $O(n)$，但一般来说不会这么极端。

快速排序 C++ 示例代码：

vector<int> a = {3, 1, 4, 2, 5};  // 待排序数组

void quick_sort(int l, int r) {
    if (l >= r) return;

    // conquer
    int i = l - 1, j = r + 1, x = a[(l + r) >> 1];
    while (i < j) {
        while (a[++i] < x);
        while (a[--j] > x);
        if (i < j) swap(a[i], a[j]);
    }

    // divide
    quick_sort(l, j);
    quick_sort(j + 1, r);
}

quick_sort(0, a.size() - 1);  // 调用示例

归并排序

这是一种稳定的排序算法，核心思想同样是分治且符合标准的三步分治策略。同样以升序为例，如果两个有序序列都是升序或都是降序，那么可以双指针扫描一遍从而 $O(n)$ 地合并这两个序列为一个有序序列。基于该先验，我们就有了归并排序算法：

将序列等分为左右两部分；
分治左右两部分使得左右两部分都是升序或都是降序；
合并左右两个有序序列。

时间复杂度的计算与快速排序类似，只不过这里的分治递归二叉树一定是 $O(\log n)$ 层，那么时间复杂度就是稳定的 $O(n \log n)$。

归并排序 C++ 示例代码：

vector<int> a = {3, 1, 4, 2, 5};  // 待排序数组
vector<int> t(a.size(), 0);       // 临时数组

void merge_sort(int l, int r) {
    if (l >= r) return;

    // divide
    int mid = (l + r) >> 1;

    // conquer
    merge_sort(l, mid), merge_sort(mid + 1, r);

    // combine
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
        if (a[i] < a[j]) t[k++] = a[i++];
        else t[k++] = a[j++];
        cnt++;
    }
    while (i <= mid) t[k++] = a[i++];
    while (j <= r) t[k++] = a[j++];

    for (i = l, j = 0; i <= r; i++) a[i] = t[j++];
};

merge_sort(0, a.size() - 1);  // 调用示例

堆排序

这是一种不稳定的排序算法。其实就是利用了堆结构及其支持的操作，每次输出堆顶然后维护堆结构即可实现堆排序。因此如果掌握了这一数据结构，堆排序算法就跃然纸上了：

将给定的序列维护成堆结构；
每次输出堆顶并重新维护堆结构即可。

为了计算堆排序算法的时间复杂度，我们分别考虑算法的两步中对应的计算开销：

对于维护堆结构。可以利用完全二叉树的性质，对于一个大小为 $n$ 的完全二叉树，其后 $n/2$ 个元素都一定满足堆的定义，因此只需要对前 $n/2$ 个元素执行 down() 操作即可，经过简单的错位相减运算可以得出该操作是 $O(n)$ 的；
对于输出堆顶并重新维护堆结构。输出是 $O(1)$ 的，重新维护堆结构其实就是删除完全二叉树的根结点，这里有一个技巧，就是将数组中的最后一个树中元素替换掉数组中的第一个元素（即根结点），然后 down() 这个新的根结点即可实现重新维护出一个堆结构，这样对于 $n$ 个元素，每次都要 $O(\log n)$ 地 down() 一次，那么就是 $O(n\log n)$。

最终的时间复杂度就是 $O(n\log n)$。

堆排序 C++ 示例代码（下标从 0 开始）：

非递归递归两种初始化完整代码

void down(int u) {
    int l = 2 * u + 1;
    int r = 2 * u + 2;
    int t = u;

    while (true) {
        if (l <= last && heap[u] > heap[l]) {
            t = l;
        }
        if (r <= last && heap[u] > heap[r] && heap[r] < heap[l]) {
            t = r;
        }

        if (t != u) {
            swap(heap[t], heap[u]);
            down(t);
            u = t;
            l = 2 * u + 1;
            r = 2 * u + 2;
        } else {
            break;
        }
    }
}

void up(int u) {
    int fa = (u - 1) / 2;

    while (fa >= 0 && heap[fa] > heap[u]) {
        swap(heap[fa], heap[u]);
        u = fa;
        fa = (u - 1) / 2;
    }
}

void down(int u) {
    int l = 2 * u + 1;
    int r = 2 * u + 2;

    int t = u;
    if (l <= last && heap[u] > heap[l]) {
        t = l;
    }
    if (r <= last && heap[u] > heap[r] && heap[r] < heap[l]) {
        t = r;
    }

    if (t != u) {
        swap(heap[t], heap[u]);
        down(t);
    }
}

void up(int u) {
    int fa = (u - 1) / 2;

    if (fa >= 0 && heap[fa] > heap[u]) {
        swap(heap[fa], heap[u]);
        up(fa);
    }
}

// 从下往上
for (int i = n / 2; i >= 0; i--) {
    down(i);
}

// 从上往下
for (int i = 1; i < n; i++) {
    up(i);
}

#include <iostream>

using namespace std;

int n, m;
int heap[100010];
int last;

void down(int u) {
    int l = 2 * u + 1;
    int r = 2 * u + 2;

    int t = u;
    if (l <= last && heap[u] > heap[l]) {
        t = l;
    }
    if (r <= last && heap[u] > heap[r] && heap[r] < heap[l]) {
        t = r;
    }

    if (t != u) {
        swap(heap[t], heap[u]);
        down(t);
    }
}

void up(int u) {
    int fa = (u - 1) / 2;

    if (fa >= 0 && heap[fa] > heap[u]) {
        swap(heap[fa], heap[u]);
        up(fa);
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> heap[i];
    }
    last = n - 1;

    // 初始化堆结构
    for (int i = n / 2; i >= 0; i--) {
        down(i);
    }

    // 输出堆顶 + 重新维护堆结构
    for (int i = 0; i < m; i++) {
        cout << heap[0] << " ";
        heap[0] = heap[last--];
        down(0);
    }

    return 0;
}