a[i] = b[1] + b[2 ]+ b[3] +,,,,,, + b[i]
也就是说,a数组是b数组的前缀和数组,反过来我们把b数组叫做a数组的差分数组。换句话说,每一个a[i]都是b数组中从头开始的一段区间和。
考虑如何构造差分b数组?
最为直接的方法
如下:
a[0 ]= 0;
b[1] = a[1] - a[0];
b[2] = a[2] - a[1];
b[3] =a [3] - a[2];
........
差分公式
b[n] = a[n] - a[n-1];
b[n] = a[n] - a[n-1];
b[n] = a[n] - a[n-1];
对a
数组的 [l, r] + c
, 只用对b[l] + c
, b[r+1] -= c
即可,不影响r + 1及后边的
加完后, 输出a[i]
b[i] = a[i] - a[i-1]
a[i] = b[i] + a[i-1]