信竞学习笔记：算法复习
注：这是本人的课堂笔记。
本文主要介绍一些算法在提高级中的应用。
前缀和与差分
前缀和用于在 O(1) 的时间复杂度内求区间和，要求数组不变；差分用于在 O(1) 的时间复杂度内修改区间。
前缀和与差分是互逆的操作。
前缀和与差分可以和一些数据结构（如线段树、树状数组）相结合，实现更便捷的操作。
模板题：P2367
快速幂
快速幂可以快速求 a^b \bmod p 的值。其原理基于二进制。其核心思想是：指数 b 可以拆分成若干个 2^k 之和，采用分治算法实现。核心代码：
int qpow(int a, int b, int p) {
int res = 1;
while (b) {
if (b & 1) res = (long long)res * a % p;
a = (long long)a * a % p;
b >>= 1;
}
return res;
}
模板题：P1226
离散化
离散化用于处理大数之间的相对大小关系，而不关心它们具体的值。通常来说，离散化题目的数据范围普遍较大（如 10^9、2^31），但数据量较小（如 10^5 \sim 10^6）。其主要通过排序和二分实现。
模板题：B3694
堆/优先队列
堆能够实现如下功能：
- 将 x 加入到序列中；
- 输出序列中的最大/小值；
- 弹出序列中的最大/小值。
功能 1、3 的时间复杂度为 O(\log n)，功能 2 的时间复杂度为 O(1)。
STL 提供了一种数据结构——优先队列，底层是堆。定义优先队列如下：
priority_queue<int> q1; // 大根堆
priority_queue<int, vector<int>, greater<int> > q2; // 小根堆
priority_queue<int, vector<int>, less<int> > q3; // 大根堆
大根堆的堆顶是序列中的最大值；小根堆的堆顶是序列中的最小值。
优先队列支持如下操作：
q.top() // 取堆顶
q.pop() // 弹出堆顶
q.push(x) // 压入元素
q.empty() // 堆是否为空
q.size() // 堆的大小
模板题：P3378
STL map 容器
map 属于关联式容器，内容是键值对，底层为红黑树。定义如下：
map<key, T> mp;
其中 key 是键的类型，T 是值的类型。
map 支持如下方法：
mp[x] // 下标查询/插入
mp.insert(make_pair(x, y)) // insert 插入 pair 类型
mp.erase(key) // 根据键删除元素
mp.erase(pos) // 根据迭代器删除元素
mp.find(key) // 访问元素，若无返回 mp.end()，否则返回元素迭代器
mp.empty() // 容器是否为空
mp.size() // 容器大小
mp.clear() // 清空容器
双指针
双指针是一种优化技巧，核心思想是在序列上维护两个可以移动的指针，通过指针之间的范围控制并寻找答案。
例题：P1638