差分
考虑一个问题，给出 n 个数据，每次给出一个请求(x, y, k)，每次将 x 到 y 位置的数据加上 k，要求在 O(n) 的时间内解决。
- 暴力解法 —— O(n2)，明显不行。
- 线段树或树状数组 —— O(qlogn)，q 为请求次数。
- 差分 —— O(n)，不辱使命。
实现方法
- 开一个于原数组相同大小的数组用于差分。
- 进行差分操作，比如需要 2~5 位置的元素都加 1，那么我们就将位置 2 标记为 +1，位置 6 标记为 -1，这样操作所有请求(不懂也先照做)。
- 计算前缀和，然后再来看结果，就是 q 请求后的结果。
- 再遍历一次加到原数组即可。
