差分数组

差分数组简介

这道题是我头一次领略到差分数组的威力。以往听到这个名词，总是敬而远之，不知道这是个啥东西，也有点畏惧接触。直到碰到这个科普帖子，

【算法小课堂】差分数组

才让我恍然大悟。原来差分数组就是离散函数的导数。早该知道到，差分的英文是differential，也有微分的意思。

• differential equations: 差分方程
• differentiable: 可微分的

我们回到离散数组$\{a_i{\}}_{i=1}^n$, 其差分数组定义为

$$d_i=\{\begin{array}{ll}{a}_1& \text{if}i=1\\ a_i-a_{i-1}& \text{if}i>1\end{array}$$

通俗理解就是，差分数组就是原数组相邻两项的增量构成的数组，并约定首项等于原数组首项。

研究差分数组主要因为它有一些性质。

性质1（积分）：从左到右累加差分数组中的元素，即可得到原数组。即，

$$\forall k\in [1,n],a_k=\sum _{i=1}^k{d}_i.$$

性质2：for $1\le i<j<n$ and $x\in N$, $\{a_k+x{\}}_{k=i}^j⟺d_i+x$, $d_{j+1}-x$.

说明，

1. 性质1就是离散积分的过程，因为差分数据是通过离散求导得到的，因此积分出来当然得到原函数。
2. 性质2将原数组的一个区间的操作，转换为差分数组上两个边界的操作。大大降低了算法复杂度。更通俗的描述，
   • 对原数组的子区间$[i,j]$, 将$a_i,a_{i+1},\dots ,a_j$都加上$x$. 等价于，
   • 把差分数组的$d_i$增加$x$，$d_{j+1}$减少$x$.

什么意思？利用性质2，我们可以原数组上对子区间的批量运算（$O(n)$）转换成差分数组上的两次运算（$O(1)$)，然后通过性质1复原数组。这在降低算法复杂度的时候非常有用！