差分数组总结

差分总结

一 差分数组定义及简单性质

• 定义： “差分数组”听名字是要应用到数组上的，我们先假设一个被应用到数组$d[n]$,我们设一个长度为n数组$d[n]$的差分数组为$f[n]$, 对差分数组中的某个元素$f[i]=d[i]-d[i-1]$ ,特别的当$i=1$的时候$f[1]=d[1]-0$,这就是差分数组定义

• “差分数组”的简单性质

1. 最明显的$d[i]=f[i]+f[i-1]+...+f[1]$,举例：$d[3]=f[3]+f[2]+f[1]=(d[3]-d[2])+(d[2]-d[1])+(d[1]-0)=d[3]-0$,概述：我们假设$f[]$数组的前缀和数组为$s[]$,此时$s[i]=f[1]+f[2]+..+f[i]$,则d[i]=s[i]

2. 由计算d[i]的前缀和（设为$sum[i]$），推论得下表达式：
   注意：$s[i]=f[1]+f[2]+..+f[i]$我们假设$s[i]$的前缀和为$pref[i]=s[1]+s[2]+...+s[I]$

$$sum[x]=\sum _{i=1}^{x}d[i]=pref[i]=\sum _{i=1}^{x}s[i]=\sum _{i=1}^x(x-i+1)\ast f[i]$$

二 差分数组的应用

• 用途一：差分数组常用于快速处理某个区间的所有有元素都 加/减某个数的问题，例如我们对$d[]$数组在$[l,r]$内的区间所有元素都加上$x$.

1. 为此我要进行的操作是把$f[l]+=x,f[r+1]-=x$,因为$d[l]$是第一个影响的数，我对$f[l]+=x$，其实这个时候我们考虑：$l<m<=r$,如果我们没有进区间操作的时候$d[m]=f[1]+f[2]+...+f[l]+...+f[m]$,当我们进行了$f[l]+x$操作之后:$d[m{]}^{\prime }=f[1]+f[2]+...+f[l]+...+f[m]+x=d[m]+x$,这样区间$[l,n]$的所有元素都加上了x，但是我们对我们$[r+1,n]$的区间也进行行了$+x$操作.
2. 我们要弥补这个措施就要进行第二个操作$f[r+1]-=x$,这样的对于区间$[l+1,n]$ 到n的元素就抵消了原来的$f[l]+=x$产生的副作用.

• 用途2:利用“差分数组性质2”，来快速求子区间$[l,r]$的和（设为$S$）
  $S=sum[r]-sum[l-1]=pref[r]-pref[l-1]$