- 第一章 基础算法
- 一、排序
- 快速排序
- 归并排序
- 二、二分
- 整数二分
- 浮点数二分
- 三、高精度
- 高精度加法
- 高精度减法
- 高精度乘法
- 高精度除法
- 第三章 前缀和与差分
- 一、一维前缀和
- 二、二维前缀和（矩阵前缀和）
- 三、一维差分
- 四、二维差分
- 五、双指针算法
- 六、位运算
背算法模板，并且理解代码的思想和流程，背的不是代码，不是单词，而是思路。
针对不同模板做相应的模板题，课下做模板题，针对做过的题，课下把代码删除后再做3~5次。
数据结构与算法可视化网站：https://visualgo.net/zh
数据输入输出大于1e6，建议用scanf，否则cin。
很多难题其实是一些基础算法堆砌而成的，人类做题的过程其实是一个 dfs 的过程，分解的过程中发现有些步骤是一些经典问题：
现在就是把这些叶节点的算法学会，最后如何有机的结合到一起就是难题了。
基于分治思想
- 确定分界点：q[l]、q[r]、q[l+r/2]、随机值
- 调整区间：却保左边都小于等于 分界点值 x，右边大于等于分界点值 x，分界点值不一定是中间值，可能是一个奇怪的值**——重点**
- 递归处理 左 右 两段
（暴力方法：定义两个数组，分别存储左右区间，最后合并）
优美方法：定义两个指针，i、j，分别位于数组两端，向中间移动，直到i、j顺序都不对时，交换i、j的值
void quick_sort(vector&q, int l, int r) { if (l >= r) return; //注意这里是>= int i = l - 1, j = r + 1, x = q[l + r >> 1]; while (i < j) { while (q[++i] < x); //注意这里无论结果如何i都会+1，故初始化时i=l-1，且才能跳出循环 while (q[--j] > x); if (i < j) swap(q[i], q[j]); } quick_sort(q, l, j); quick_sort(q, j + 1, r); }
快排为不稳定排序，但也可以变为稳定排序，只要将每一个数变为不同就可以，如：将 a[i]，变为 < a[i]，i >，变为一个二元组，进行双关键字排序即可。
时间复杂度
每一次划分，期望都是 n/2，每次递归的层数，期望是log n。
思路：基于分治思想
- 确定分界点: 中间点 mid = l+r >> 1
- 递归排序 - 分界点左右
- 归并——合二为一
void merge_sort(int q[], int l, int r)
{
if (l >= r) return; //return边界
int mid = l + r >> 1;
merge_sort(q, l, mid); //排序左半
merge_sort(q, mid + 1, r); //排序右半
int k = 0, i = l, j = mid + 1; //将i，j分别指向两数组第一个元素
while (i <= mid && j <= r) //若两数组都没结束，选小的进
if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
else tmp[k ++ ] = q[j ++ ];
while (i <= mid) tmp[k ++ ] = q[i ++ ]; //一数组结束，另外一数组剩下元素依次进
while (j <= r) tmp[k ++ ] = q[j ++ ];
for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
时间复杂度：
n 除了 log n 次可以除到 1，每一层的时间复杂度都是O(n)，最后的时间复杂度是：n log n
数据有单调性，一定可以二分，可以二分的题目，并不一定有单调性。
所以二分的本质并不是单调性
二分的本质是：边界，可以划分为满足某种性质与不满足某种性质的两个区间，用二分法可以找到两区间边界的左右两个点。
数据可以划分为红色和绿色两个部分，如果判断不在红色部分，那一定在绿色部分。
1、以红色为边界点
2、以绿色为边界点
一般不需要考虑这么细。
如找到一个数的左右边界，检查的就是是否为当前数，不为则是false
整数二分int bsearch_1(int l, int r) //寻找右边界
{
while (l < r)
{
int mid = l + r + 1 >> 1; //右边界需+1
if (q[mid]>k) r = mid-1; //mid不满足<=，直接将右边界置mid左边
else l = mid; //左边界一点点贴近右边界
}
return l;
}
int bsearch_2(int l, int r) //寻找左边界，同理
{
while (l < r)
{
int mid = l + r >> 1;
if (q[mid]
浮点数二分
void bsearch_3(double l, double r) //所有可能的范围如[-10000,10000]
{
const double eps = 1e-8; //要求精度多两位
while (abs(r - l) > eps)
{
double mid = (l + r) / 2;
if (n-pow(mid,3)
三、高精度
分为：A + B、A - B、A * a、A / a
高精度加法
- 大整数存储，将大整数的每一位转为整数，倒叙存入数组
void add(vector&a,vector&b){
if(a.size()b，由于都是正整数，所以可以这么操作
int c=0;
for(int i=0;i
a[i]+=c; //a+b+c（进位符）
if(i=0;i--) printf("%d",a[i]);
}
高精度减法
void sub(vector&a,vector&b){
int c=0;
for(int i=0;i //同理变成减
a[i]-=c;
if(i=0;i--) printf("%d",a[i]);
}
高精度乘法
乘法与加法类似，但由长整数乘以短整数，故不是一位乘一位，是以长整数的一位乘整个短整数。
void mult(vector&a,int b){
int c=0;
for(int i=0;i
a[i]=b*a[i]; //同理，注意先乘后加
a[i]+=c;
c=a[i]/10;
a[i]%=10;
}
while(c!=0){ //若用新数组保存值每次push_back，for循环条件可以为a.size()||c，减少这个while语句
a.push_back(c%10);
c/=10;
}
while(a.size()!=1&&a.back()==0) a.pop_back();
for(int i=a.size()-1;i>=0;i--) printf("%d",a[i]);
}
高精度除法
模拟除法，从高位开始，（余数*10+高位）除以除数得商的高位，%除数得新的余数，循环。
void div(vector&a,int b){
int t=0;
vector c;
for(int i=0;i
t=t*10+a[i];
if(c.size()!=0||t/b!=0) c.push_back(t/b); //用if去除高位的0，可以用reverse函数倒置去0同理
t%=b;
}
if(c.size()==0) c.push_back(0);
for(int i=0;i
第三章 前缀和与差分
一、一维前缀和
假设有一组长度为 n 的数组：a[1]，a[2]，a[3] …… a[n]。
前缀和数组：S[i] = a[1] + a[2] + … a[I]。前缀和不是一个模板，而是一个公式。
- 如何求 S[i]
答：遍历数组，求前 i 项和。 - S[i] 的作用
答：更快速的求出 [ l，r ] 的和，如果有前缀和数组，则可通过 S[r] - S[l-1] 求出。求 [ 1，x ] 的和也是同理，S[x] - S[0]。
没有前缀和数组，只能遍历求和，时间复杂度为 O(n)，有前缀和数组，时间复杂度为 O(1)。
S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]
二、二维前缀和（矩阵前缀和）
同理假设有一组二维数组 a[i][j] 。
S[i][j] 代表 从 a[1][1] 到 a[i][j] 所有元素的和，是个矩阵。
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]。
S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]
三、一维差分
前缀和的逆运算。
假设有一组长度为 n 的数组：a[1]，a[2]，a[3] …… a[n]。
构造 b 数组：b[1]，b[2]，b[3] …… b[n]。
使得 a[n] = b[1] + b[2] + b[3] + …… + b[n]。
a 数组是 b 数组的前缀和，b 为 a 的差分。
如果想要将数组 a 中的每一个数 + c，如果遍历来做，时间复杂度为 O(n)，用差分来做，时间复杂度为 O(1)。
给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c
原理：若在a数组的区间[l, r]上依次加val，时间复杂度 O(n)；若在b数组上 b[l ] + val、b[r+1] - val，最后求它的前缀和数组 a，[l, r] 区间内得到相同结果，时间复杂度 O(1)。
思路：虽然题目初始化的数组有值，但我们仍初始化一个全0的差分数组b，模拟在 [l, l] 上每一个位置依次进行插入初始值C，然后按题目要求在[l,r]上插入即可；
void insert(int l,int r,int val){ //由于最后结果是前缀和数组，在差分数组l上加val，使得[l, + ∞)上都加val，在r+1上减val得到仅在区间[l,r]上加val
q[l]+=val;
q[r+1]-=val;
}
四、二维差分
同上
void insert(int x1,int y1,int x2,int y2,int v){ //注意容斥问题、矩阵从a11开始、矩阵初始化大小行列都得+2
q[x1][y1]+=v;
q[x1][y2+1]-=v;
q[x2+1][y1]-=v;
q[x2+1][y2+1]+=v;
}
五、双指针算法
第一种对于两个序列，维护某种次序：
在归并排序时，两个数组合并，就是一个双指针算法，两个指针分别位于数组相应的位置，依次向右遍历，当数组执行到尾部，合并完成。
第二种是对于一个序列，用两个指针维护一段区间：
如快排，两个指针分别位于左右两端，依次中间比较交换。
双指针算法最核心的思想就是将原本两层循环 O(n^2) 的算法优化为 O(n)。
只要能够满足以上思想，都可以称为双指针算法。
如下，输入多个单词，每个单词之间都会有一个空格，依次输出单词，每行一个。
最后为如下模板：
for (int i = 0, j = 0; i < n; i ++ )
{
while (j < i && check(i, j)) j ++ ; //寻找i，j的单调关系
// 具体问题的逻辑
}
双指针算法就是针对朴素算法中发现一些性质，尤其是发现一些单调性，使得原本要枚举 O(n^2) 的算法优化为 O(n)。
六、位运算
常见题：
n 的二进制表示数字中，第 k 个数字是多少。
n = 15 = (1111) 2
- 先把第 k 位 移到最后一位：n >> k
- 看个位是多少：x & 1，即：n >> k & 1
求二进制中1的个数
lowbit(x)：返回x的最后一个1，即101000得1000；
原理：x&-x = x&(~x+1)
int lowbit(int x){
return x & -x;
}
源码：x 的二进制
反码：x 的二进制取反
补码：反码 + 1
