差分数组介绍

定义

对于已知有n个元素的离线数列d，我们可以建立记录它每项与前一项差值的差分数组f：
$$f[i]=\{\begin{array}{ll}d[1]& \text{if }i=1,\\ d[i]-d[i-1]& \text{if }i>1.\end{array}$$

性质

性质1: 计算数列第i项的值

数列第i项的值是可以用差分数组的前i项的和计算的，这是因为差分数组第一项就是原数列的值，后续都是数列的差分变化，有起始数据和后续的变化数据，就可以推导出原始的真实数据。推导公式如下：
$$d[i]=\sum _{j=1}^{i}f[j]$$
由于d[i-1]已经计算出差分数组前i-1项的和，所以进一步优化为
$$d[i]=\{\begin{array}{ll}f[1]& \text{if }i=1,\\ f[i]+d[i-1]& \text{if }i>1.\end{array}$$