一, 差分数组的定义及用途
1. 定义:
对于已知有 n 个元素的数列 d, 建立记录它每项与前一项差值的差分数组 f: 显然, f[1]=d[1]-0=d[1]; 对于整数 i∈[2,n], 我们让 f[i]=d[i]-d[i-1].
2. 简单性质:
(1)计算数列各项的值: 观察 d[2]=f[1]+f[2]=d[1]+d[2]-d[1]=d[2]可知, d[i]=f[i]的前缀和.
(2)计算数列每一项的前缀和: 第 i 项的前缀和即为数列前 i 项的和, 那么推导可知
即可用差分数组求出数列前缀和;
3. 用途:
(1)快速处理区间加减操作:
对数列区间 [L,R] 中的每个数加上 x, 我们通过性质 (1) 知道, 第一个受影响的差分数组中的元素为 f[L], 即令 f[L]+=x, 那么后面数列元素在计算过程中都会加上 x;
最后一个受影响的差分数组中的元素为 f[R], 所以令 f[R+1]-=x, 即可保证不会影响到 R 以后数列元素的计算.
这样我们不必对区间内每一个数进行处理, 只需处理两个差分后的数即可;
(2)询问区间和问题:
由性质 (2) 我们可以计算出数列各项的前缀和数组 sum 各项的值; 那么显然, 区间 [L,R] 的和即为 ans=sum[R]-sum[L-1];
参考博客:
差分数组
来源: http://www.bubuko.com/infodetail-3260667.html