差分

· · 个人记录 

a[0]=0
b[1]=a[1]-a[0];
b[2]=a[3]-a[2];
a[n]=b[n]+......+b[3]+b[2]+b[1];

给 a[l]~a[r] 区间加上 c,只需对差分数组b做b[l]+c,b[r+1]-=c; 复杂度为O(1)。 差分解决区间加减问题，前缀和解决区间求和问题