差分数组介绍
差分数组
差分数组介绍
定义
对于已知有n个元素的离线数列d，我们可以建立记录它每项与前一项差值的差分数组f：
f [ i ] = { d [ 1 ] if i = 1 , d [ i ] − d [ i − 1 ] if i > 1. f[i] = \begin{cases} d[1] & \text{if } i = 1, \\ d[i] - d[i-1] & \text{if } i \gt 1. \end{cases} f[i]={
d[1]d[i]−d[i−1]if i=1,if i>1.
性质
性质1: 计算数列第i项的值
数列第i项的值是可以用差分数组的前i项的和计算的，这是因为差分数组第一项就是原数列的值，后续都是数列的差分变化，有起始数据和后续的变化数据，就可以推导出原始的真实数据。推导公式如下：
d [ i ] = ∑ j = 1 i f [ j ] d[i] = \sum \limits _{j = 1}^i f[j] d[i]=j=1∑if[j]
由于d[i-1]已经计算出差分数组前i-1项的和，所以进一步优化为
d [ i ] = { f [ 1 ] if i = 1 , f [ i ] + d [ i − 1 ] if i > 1. d[i] = \begin{cases} f[1] & \text{if } i = 1, \\ f[i] + d[i-1] & \text{if } i \gt 1. \end{cases} d[i]={
f[1]f[i]+d[i−1]if i=1,if i>1.
原文地址：https://blog.csdn.net/Yuzhiyuxia/article/details/142439551
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！