XP02 DAY2 贪心、前缀和、差分学习笔记
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
一、贪心算法
1. 贪心算法的专业概念
贪心算法是指：
这句话里有两个关键词：
用更通俗的话说：
2. 生活中的贪心例子
假设你要买一本 37 元的书，手里有很多面值的钱：
如果想用尽量少的纸币张数付款，一种自然想法是：
过程：
最后用了：
这个过程就是一种贪心：
3. 贪心算法不是乱选
贪心不是随便选一个看起来舒服的答案。
它需要有一个明确规则，例如：
而且这个规则必须真的能得到正确答案。
所以使用贪心时，要想清楚：
4. 样例解释：最多能买几支笔
题目：
输入：
其中 ai 表示第 i 支笔的价格。
样例：
意思是：
5. 贪心分析
想买尽量多的笔，就应该优先买便宜的笔。
为什么？
所以贪心规则是：
我们可以先把价格从小到大排序：
然后从便宜到贵买：
最多可以买：
6. 代码实现
7. 代码解释
排序：
把价格从小到大排好。
统计答案：
表示已经买了多少支笔。
如果钱够：
就买这支笔：
如果钱不够：
因为后面的笔更贵，也买不起了，可以直接停止。
8. 贪心题的思考步骤
做贪心题，可以按下面顺序想：
9. 贪心算法提醒
贪心很快，也经常很好写。
但要注意：
如果一个题目中：
那么贪心就可能错误。
初学阶段先记住：
10. 作业：T1、T2
T1、T2 是贪心算法练习题。
做题时请先写出：
建议解题格式：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二、前缀和
1. 问题引入：蚂蚁吃米
有一只蚂蚁连续吃了 n 天米。
第 i 天吃了 ai 粒米。
现在有 q 次询问，每次问：
例如：
如果问：
答案是：
2. 暴力解法
最直接的方法是：
代码大概是：
这个方法容易理解。
但如果：
每次都重新加一遍，就会很慢。
3. 暴力解法的时间复杂度
一次询问，最坏可能要加 n 个数。
如果有 q 次询问，那么最坏大约是：
例如：
那么大约要做：
也就是 10^10 次。
这通常会超时。
所以我们要想办法优化。
4. 前缀和能解决什么问题？
前缀和主要解决：
也就是：
例如：
5. 前缀和的算法思想
前缀和就是提前算好：
我们用 s[i] 表示：
例如：
那么：
表格：
i 1 2 3 4 5 a[i] 2 4 1 3 6 s[i] 2 6 7 10 16
6. 前缀和的算法过程
先定义：
然后从 1 到 n 计算：
这句话的意思是：
如果要求 [l, r] 的和：
可以用：
为什么？
因为：
两者相减，前面多余的部分就去掉了。
剩下：
7. 前缀和代码实现：数组准备
为了让公式更好写，本节课使用从 1 开始的下标。
定义数组：
为什么用 long long？
因为很多数加起来可能超过 int 范围。
例如：
这个数比 int 能存的范围大，所以用 long long 更安全。
8. 前缀和代码实现：读入数据
这里：
9. 前缀和代码实现：计算 S 数组
这段代码是前缀和最核心的部分。
每次计算：
例如：
表示：
10. 前缀和代码实现：回答询问
每次输入 l 和 r：
区间 [l, r] 的和是：
所以：
11. 前缀和完整代码
12. 前缀和复杂度
计算前缀和数组：
每次询问：
如果有 q 次询问，总复杂度：
比暴力的：
快很多。
13. 前缀和易错点
易错点一：忘记 s[0] = 0
当 l = 1 时，要用：
所以 s[0] 很重要。
易错点二：公式写错
正确公式：
不是：
易错点三：没用 long long
如果数据较大，总和可能超过 int，建议使用：
14. 算法应用：T3、T4
T3、T4 是前缀和应用题。
看到题目中有这些关键词时，要想到前缀和：
做题时先写出：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三、差分
1. 问题引入：区间加
现在有一个数组：
有 m 次操作，每次操作给出：
表示：
最后输出整个数组。
例如：
表示第 2 到第 4 个数都加 10。
结果：
2. 暴力解法
最直接的方法：
一次操作最坏要改 n 个数。
如果有 m 次操作，最坏复杂度是：
如果：
大约要做：
次操作，通常会超时。
所以需要优化。
3. 差分能解决什么问题？
差分主要解决：
特别是这种操作：
如果题目最后才问整个数组结果，差分非常适合。
4. 差分和前缀和的关系
差分是依托前缀和的。
可以这样理解：
如果有原数组：
差分数组 b 可以这样定义：
得到：
如果我们对 b 求前缀和：
又能得到原数组：
所以：
5. 差分的算法思想
如果要让 [l, r] 这一段都加上 x，差分数组只需要改两个位置：
为什么这样可以？
从 l 开始：
到 r + 1：
所以真正受到影响的是：
6. 用例子理解差分
原数组：
先建立差分：
所以：
现在执行操作：
也就是 [2, 4] 每个数加 10。
差分中操作：
新的差分：
对 b 求前缀和还原：
结果：
正好是我们想要的。
7. 差分的算法过程
差分题一般分四步：
8. 差分代码实现：定义数组
这里也建议使用 long long。
因为多次区间加之后，数字可能变得很大。
9. 差分代码实现：读入原数组
其中：
10. 差分代码实现：建立差分数组
根据定义：
代码：
这里默认：
所以：
11. 差分代码实现：处理区间加
每次操作输入：
执行：
注意：
所以数组要开大一点：
12. 差分代码实现：还原最终数组
处理完所有操作后，对 b 求前缀和：
这一步表示：
然后输出：
13. 差分完整代码
14. 差分复杂度
建立差分数组：
每次区间加：
还原数组：
如果有 m 次操作，总复杂度：
比暴力的：
快很多。
15. 差分易错点
易错点一：忘记修改 r + 1
正确写法：
易错点二：数组没有开大
因为会访问：
如果 r = n，就会访问：
所以数组要多开一点。
易错点三：还原数组时公式写错
正确写法：
也可以直接累加输出：
易错点四：把前缀和和差分混在一起
记住：
16. 算法应用：T5、T6
T5、T6 是差分应用题。
看到题目中有这些关键词时，要想到差分：
做题时先写出：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
四、本节课总结
1. 贪心
贪心算法是：
做贪心题要先确定：
2. 前缀和
前缀和解决：
核心公式：
区间 [l, r] 的和：
3. 差分
差分解决：
区间 [l, r] 全部加 x：
最后通过前缀和还原数组。
4. 前缀和与差分的区别
算法 主要解决 核心操作 前缀和 区间和查询 s[r] - s[l - 1] 差分 区间加修改 b[l] += x; b[r + 1] -= x;
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
课后练习
T1：贪心练习
完成题单中的 T1。
做题时写清楚：
T2：贪心练习
完成题单中的 T2。
如果题目需要排序，请想清楚：
T3：前缀和应用
完成题单中的 T3。
看到区间和询问时，先写：
然后用：
回答询问。
T4：前缀和应用
完成题单中的 T4。
注意检查：
T5：差分应用
完成题单中的 T5。
遇到区间加时，先想到：
T6：差分应用
完成题单中的 T6。
注意最后要通过前缀和还原：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
本节课最重要的五句话
1. 贪心是每一步选择当前最优，但必须有正确的贪心规则。
2. 前缀和用于快速求区间和。
3. 前缀和公式是 s[i] = s[i - 1] + a[i]。
4. 差分用于快速进行区间加。
5. 差分修改公式是 b[l] += x; b[r + 1] -= x;。
