经过近一星期的学习，总算是将基础算法部分给拿下了，简单的总结下吧。

一. 排序

1.排序常用的一般便是快排与归并。

2.快排: 利用了分治的思想，也就是先排序，再递归，简单来说分为3步。

(1) 确定分界点，一般是q[l], q[r], q[l + r >> 1], 为防止出现边界问题，建议使用q[l + r >> 1]。

(2) 调整区间。即使分界点左边的数小于等于分界点，右边的数大于等于分界点。

(3) 递归处理左右区间，即对左右区间，重复以上步骤。

3.归并排序: 先分别对左右区间的数排好序后，再有序的将左右区间的数合并为一个有序序列。

(1) 确定分界点：mid = l + r >> 1;

(2) 递归排序左右区间。

(3) 归并-合二为一。

二. 二分

二分分为整数二分与浮点数二分。

1.整数二分

个人感觉，整数二分的核心在于，将一个序列分为两个区间。
其中一个区间内的数严格满足某个性质，而另一个区间的数不满足，因此边界点有着两个值。
根据所求边界的不同，套用的模板也不同，
（求左区间的边界点，mid = l + r + 1 >> 1; 求右区间的边界点, mid = l + r >> 1;)

2.浮点数二分

类似于整数二分，但无需考虑边界问题，因为边界点仅有一个，根据题目要求的精度，得到最后的边界点。

三. 前缀和

前缀和较为简单，目的在于能够快速得到一个区间内所有数的和。
前缀和分为一维和二维。

1.一维

S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]

2.二维

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]

四. 差分

差分的目的在于能够快速对某个区间的数加上一个相同的值。
不必注重差分数组的构建，重点在于如何进行更新。
差分同样分为一维和二维。

1.一维

给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c

2.二维

给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

五.位运算

1.求n的第k位数字: n >> k & 1；
2.返回n的最后一位1：lowbit(n) = n & -n；

六.双指针算法

很多地方都会用到，比如快排和归并，但自己却又不知道何时该用，需要经验的积累。

一般可先使用暴力来写，然后通过找寻规律，将暴力的方法进行优化。

七.离散化

离散化一般用于给出的定义域（下标）跨度很大，但实际用到的下标却很少的情况。
将用到的下标储存到一个新的数组中(一般使用vector)，新数组的下标即是原下标离散化后的值。

一般的思路是：

1.储存所有待离散化的值。

2.将新的储存离散化后的值的数组进行排序。

3.对新的储存离散化后的值的数组进行去重。

八.区间合并

该算法目的在于，对于一系列给出的区间，将这些区间进行合并。

核心思想:

1.用pair储存每一个区间，开一个新数组储存合并后的区间。

2.对于给出的区间的左端点进行排序。

3.自身维护一个区间（初始区间我使用排序后的第一个区间)
排序后的每个区间与自身维护的区间仅有两种关系，有交集和无交集。

有交集：更新自身维护区间的右端点。

无交集: 将维护的区间加入储存新区间的数组，
然后将自身维护的区间设置为与其无交集的区间。

4.对所有的区间判断完毕后，最后再将维护的区间加入储存新区间的数组。

ok,总结完毕，接下来也要继续加油！