前缀 & 差分
前缀和
通过前缀和可以直接算出数组某段区间和
前缀和的思想是： 从0开始把数组中的元素累加起来，并且都存放到字典中，然后具体在累加每一个值的时候。再去字典中翻一下看看有没有合适的值。
前缀和并不一定真的要求出前缀和数组，往往都是在遍历数组的时候，一遍往后走，一遍把到当前为止的和放到字典中。
通常前缀和会和滑动窗口、单调栈、单调队列组合在一起。
滑动窗口适用于明确知道什么时候收缩的情况，但是当数组中存在负数时，滑动窗口失效了，因为不知道何时扩张何时收缩。所以采用前缀和。
经典题型
2Sum系列
关键在于利用hashmap来存储之前走过的值
rangsum系列
862. 和至少为 K 的最短子数组 滑动窗口+前缀和+单调队列
差分数组
差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减。
差分是和前缀相对的策略，可以当作是求和的逆运算。差分的定义如下：
有如下性质：
- 的值是 的前缀和，即：
- 计算 的前缀和：
差分数组可以维护多次对序列的一个区间加上一个数，并在最后询问某一位的数或是多次询问某一位的数。注意修改操作一定要在查询操作之前。
这样构造差分数组
diff，就可以快速进行区间增减的操作，如果你想对区间 nums[i..j] 的元素全部加 3，那么只需要让 diff[i] += 3，然后再让 diff[j+1] -= 3 即可：举个例子，若原数组
a = [0,0,0,0,0,0], 若给出(a, b, c) = (3, 2, 5)，即在区间[a:b]内的元素加3，则原数组变为[0,0,3,3,3,0], 差分数组变为[0,0,3,0,0,-3]，仅修改两个值。由差分数组得到原数组时， 只需要逆向变化即可。
class Difference: def __init__(self, nums): self.nums = nums # 构建差分数组 self.diff = [n for n in self.nums] for i in range(1, len(self.nums)): self.diff[i] = self.nums[i] - self.nums[i-1] def increment(self, i, j, val): # 对闭区间 nums[i:j] 内的元素逐个 加val self.diff[i] += val if j + 1 < len(self.nums): self.diff[j+1] -= val def res(self): # 返回修改后的数组 for i in range(1, len(self.nums)): self.nums[i] = self.nums[i-1] + self.diff[i] return self.nums
经典题目
798
速通
前缀和 & 差分速通 完整笔记参见 前缀 & 差分
前缀和 以及 差分算是 写题的简单技巧，尤其是在维护区间和的题目上，该技巧常与二分法、滑动窗口等题型相结合。此外，前缀和的技巧不仅可以应用于数组上，还经常应用与二叉树、链表中。
总结
前缀和、差分是算法，更是思想，尤其作为一种常用的预处理技巧