只想自己做个记录当笔记，并不太想发表QAQ，但好像必须得发表出来。

听完了一遍算法基础课，今天复习了第一章，发现之前听过的很多内容都有所遗忘。一方面是因为刷题不够，另一方面没有把一些容易混淆的点记录下来。
1、 快速排序和归并排序部分没有什么特别需要纠结的，按照给出的模板默写即可，不用考虑边界问题。
2、二分是最容易混淆忘记的地方，主要抓住两个要点：一个是二分性质分界线的范围是在左边还是右边。根据性质在左边还是右边有两个模板，这两个模板共同点在于，判断满足性质之后都是需要某个端点等于mid。当r=mid的时候，mid不需要加一，当l= mid时候，需要加一。可以这么记忆：因为l + r >> 1 的表达式中，如果r=mid，这个r离表达式里的r更近，所以不用加一，但如果是l=mid，l离表达式里面的l更远，所以不用加一。
3、高精度加减乘除背模板即可，但需要记住，数据的存储顺序。
4、前缀和与差分
4.1 前缀和注意数组中的下标要从1开始，(出现了i-1这种下标就应该从1开始)
4.2 [L,R]区间和的计算s[R] - s[L - 1].
4.3 由原数组求差分数组有两种写法：for (int i = 1; i <= n; i++) a[i] += a[i], a[i + 1] -= a[i];或者for (int i = n; i; i–) a[i] -= a[i - 1];
4.4 二维前缀和求和(注意下标都从1开始)：a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];求x1, y1, x2, y2z范围内的值a[x2][y2] - a[x1 - 1][y2] - a[x2][y1 - 1] + a[x1 - 1][y1 - 1];
4.5 由原数组求二维差分数组有两种写法：一种是insert(x1, y1, x2, y2, c) a[x1][y1] += c, a[x2 + 1][y1] -= c, a[x1][y2 + 1] -= c, a[x2 + 1][y2 + 1] += c;调用insert(i, j, i, j, a[i][j]); 第二种写法为倒序遍历，把求前缀和的过程反过来：

for (int i = n; i; i--) {
    for (int j = m; j; j--) {
        a[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1];
    }
}