前缀和与差分

• 引入
  如果给你一个数组，让你对于给出的[L,R]区间中的数据加上1，相信这是非常容易实践的，只需要暴力就完全可以解决这个问题。
  但是在算法竞赛中，像这样的暴力做法很可能会导致TLE，导致我们不能拿到全部分数。
  于是我们有了前缀和与差分。
  （本文章中只涉及到一维的前缀和与差分。）

• 前缀和
  前缀和，顾名思义就是将前缀的数据加到一起。将文字转化为代码会更容易理解。

  pre[0] = 0;
  for(int i = 1; i <= n; i++)
     pre[i] = pre[i - 1] + a[i];
  

  仔细理解上面三行代码的功能，相信大家都已经理解了。

• 差分
  前缀和与差分总是结伴出现，这肯定是有原因的。
  如果一个数组a是数组b的前缀和数组，那么数组b就是数组a的差分数组。

  b[i]=a[i]-a[i];
  

  对前缀和数组进行差分操作或者对差分数组进行一个前缀和操作就可以还原出原数组。
  当将[L,R]区间上的a数组全部加上x，也就是将b[L]+=x,b[R+1]-=x；（注意此处的R+1。因为b[R]仍是要+x的，所以在b[R+1]才开始-x。）

在实际的算法竞赛中，前缀和与差分数组通常是配合使用的。