差分

•  定义一个差分数组dif和原数组a

特别地      

dif1 = a1

接下来每个数定义为

difi = ai - ai-1

• 性质

           差分数组前 i 项和等于第 i 项的值  sumi = ai = difi + sumi-1 = dif1 +dif2 +...+difi 

           sum的差分数组为第i项的值    ai = sumi - sumi-1

修改区间时转换为点修改 (l,r) +n   -->  difl+=n; difr+1- = n;

         以上性质在树状数组中有体现。了解可以通过以下两道题

题目：

[USACO07JAN]区间统计Tallest Cow

[Poetize6] IncDec Sequence