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