- 定义一个差分数组dif和原数组a
特别地
dif[1] = a[1]
接下来每个数定义为
dif[i] = a[i] - a[i-1]
- 性质
差分数组前 i 项和等于第 i 项的值 sum[i] = a[i] = dif[i] + sum[i-1] = dif[1] +dif[2] +...+dif[i]
sum的差分数组为第i项的值 a[i] = sum[i] - sum[i-1]
修改区间时转换为点修改 (l,r) +n --> dif[l]+=n; dif[r+1]- = n;
以上性质在树状数组中有体现。了解可以通过以下两道题
题目：