给定一个包含33558www.Sina.com/5000万个元素的数组，有频繁的区间修改操作，那么什么是频繁的区间修改操作呢？ 例如，从第一个个数到第1000万个个数分别加1，而且该操作频繁进行。
这个时候该怎么办？ 容易想到的是，如果经常执行从第一个到第1000万个遍历，然后将每个数加1的操作，某些实时系统可能会克服这种暴力方法。
因此，今天的主角变成了——差分配排。
问题背景例如，我们现在有序列arr。 arr={ 0，2，5，4，9，7，10，0 }
那么什么是差分配列呢？ 其实差分配序列本质上也是一个序列。 将差分配列定义为d。 差分配序列d的大小与原始arr序列相同，而且d[i]=arr[i]-arr[i-1](i0，然后d[i]=0。 那个意思是什么？ 原来是位于数组I位置的要素和位于i-1位置的要素之差，得到的值是d[i]的值。
因此，与示例中的arr数组相对应的差分配数组值如下图所示。
做这样的东西有什么用呢？ 你是来浪费宝贵的内存空间的吗？ 嗯，我确实是来浪费宝贵的内存的，但是改变了时间上的效率。
现在有区间1~4中所有数值加3的区间修正操作。
我们不要傻傻地遍历arr数组的[ 1，4 ]范围，然后再给每个值加3。 此时，只要变更差分配列d即可。
很明显，只要不改变差分配列d在[ 2，4 ]范围内的值，而改变差分配列位置1和位置5的值即可. 即，d[1]=d[1] 3，而在d[5]=d[5]-3时，剩下的不变。 为什么会这样呢？ 差分配列定义为—— 算法原型
那么，如何从差分配列d推测arr所在位置的值呢？
例如，此时，假设您想知道arr[1]的值。 无法直接从arr[1]获得原始值。 因为区间修改操作没有修改arr的值，所以d [0]=arr [0]-0 (将arr [0]的第一个数定义为0。 这样，由于d[2]=arr[2]-arr[1]=3，所以arr[2]=3 arr[1]=8。
从d[i]=arr[i]-arr[i-1]可以看出，如果需要对L~R范围内的所有数据进行相同的操作，则不需要从L~R遍历arr对每个值进行相同的操作，只需在差分配列d中改变l和R 1的值即可。 但是，在调查arr排列内的某个位置的数据时，必须根据差分配排列从前方向后求出值。
因此，该方法适用于总结，而且适用于区间频繁修改的区间范围是比较大的情况。