【数据结构与算法】差分数组

定义

设原数组为a，长度为n，在a上构造它的差分数组d，构造方法如下：

$$d[i]= \begin{cases} a[0]& \text{i=0}\\ a[i]-a[i-1]& \text{0<i<n} \end{cases}$$

由此可得差分数组d的定义:

• 差分数组是一个原数组长度相等的数组，其中元素表示原数组相邻元素的差。

性质

对差分数组d求前缀和：

$$preSumD[i] = {\Sigma}_{j=0}^id[j]=d[0]+d[1]+ ... +d[i]$$

代入上述定义式可得：

$$preSumD[i]=a[0]+(a[1]-a[0])+(a[2]-a[1])+...+(a[i]-a[i-1])=a[i]$$

由此可得差分数组d的

性质1

• 差分数组的前缀和preSum[i]等于其原数组中的对应元素a[i]。

继续对原数组a求前缀和：

$$\begin{align} preSumA[i]=& {\Sigma}_{j=0}^ia[j]\\ =&{\Sigma}_{j=0}^i{\Sigma}_{k=0}^jd[k]{\quad}（代入性质1）\\ =&{\Sigma}_{k=0}^0d[k]+{\Sigma}_{k=0}^1d[k]+...+{\Sigma}_{k=0}^id[k]{\quad}（先计算最外层）\\ =&(i+1)·d[0]+(i)·d[1]+...+2·d[i-1]+d[i]{\quad}（合并同类项）\\ =&{\Sigma}_{j=0}^i(i-j+1)·d[i]{\quad}（归纳） \end{align}$$

由此可得

性质2

• 原数组的前缀和可以由差分数组求得。

用途

区间修改

根据上述性质1，可以把对原数组中元素的修改转化为对差分数组的修改。特别地，对于区间的批量修改，若对原数组的某个区间[l, r]中的所有元素都增加x，只需要对差分数组执行以下操作：

d[l] += x;
d[r+1] -= x;

• 对 d[l] += x：由于差分是前缀和的逆向过程，这个操作对于将来的查询而言，带来的影响是对于所有的下标大于等l的位置都增加了值 x；
• 对 d[r+1] -= x：由于我们期望只对 [l, r][产生影响，因此需要对下标大于r的位置进行减值操作，从而抵消“影响”。

单点查询

• 利用性质1，可以通过求差分数组的前缀和来查询原数组中的某个元素。
• 利用性质2，可以通过公式计算原数组的前缀和/区间和。

技巧

构造差分数组时，不一定需要直接使用原数组，有时候可以使用区间修改的方式。

例如：1109. 航班预订统计

对于涉及区间修改、单点查询的区间求和问题，可以考虑使用差分数组。

相关题目

995. K 连续位的最小翻转次数

1109. 航班预订统计

…待补充