查分算法

差分可以看做是求前缀和的逆向过程。

差分数组的定义为
d[i] = a[i]-a[i-1];
例如现在有一个数组为
[1,3,5,4,2]
那么它的差分数组为
[0,2,2,-1,-2]

差分数组如何做到时间复杂度为O(1)的数组区间修改的。

例如，现在想对区间[l,r]的进行加v的操作。
那么只需要在差分数组进行操作：
d[l]=d[l]+v;
d[r+1]=d[r+1]-v;
这样在求回原数组的时候，d[l]增加了v，由于累加的性质，那么它后面直到下标r都增加了v。 对于d[r+1]来说，由差分数组的定义，被减数不变，减数增加了v那么它必定也要减小v，所以进行该两项进行操作。

模板例题

https://leetcode-cn.com/problems/corporate-flight-bookings/