1.4 前缀和与差分
本次主要介绍前缀和、差分算法，前缀和与差分互为逆运算，是一种非常重要的算法思想。其中前缀和算法适用于需要频繁求出一段区间和的情况，差分算法适用于将某段区间的元素全部加上一个数的情况。为了操作统一性和简洁性，将前缀和数组和差分数组都初始化0，仅考虑插入元素操作，这样就可以只考虑更新，而不用考虑构造和初始化。
1.4.1 前缀和
前缀和主要是一种思想，适用于需要快速求出一段区间数字和的情况
将数组转换为前缀和数组之后，即可将快速求区间和的算法时间复杂度从
变成
初始化为了更好处理边界
一般步骤：
- 求前缀和
- 算部分和（子矩阵的和）
前缀和.png
前缀和1.png
1.4.2 差分
- 差分和前缀和互为逆运算
- 适用情景：操作：需要数组
在一个区间[l, r]使得该区间内所有数全部加上c。 (在该种操作很多的情境下，差分思想起到作用)
- 为了统一操作，可以假设原数组
都为0，每添加一个数，都在差分数组
上进行一次操作（这样可以只考虑更新，不考虑构造、初始化）
差分1.png
差分2维.png
