差分数组

差分数组

定义

设有数组,其对应的差分数组为

$$d_i=\left \{ \begin{align*} a_0,i&=0, \\ a_i-a_{i-1},i&\ge 1 \end{align*} \right.$$

性质

性质1： $ai=\sum{k=0}^{i}{d_k}da$。
性质2： 以下两个操作等价

• $di+x,d{j+1}-x$

其中，即对原数组中的每个元素加上同一个数，相当于对差分数组中的两个元素$did{j+1}x$。

对应的题目

1094-Car-Pooling