介绍：

差分数组用来记录一个数组中相邻数据的差，比如给出一个数组a，a[i]表示数组a的第i个元素，另外给出一个数组d表示差分数组那么d[i] = a[i] - a[i-1]，所以d[i]表示数组a中第i个元素与前一个元素的差值，那么差分数组的意义在哪呢？

下面给出一个数组a以及对应的差分数组

下标 0 1 2 3 4 5
数组a 1 3 5 2 7 10
数组d 2 2 -3 5 3

现在有这样一个操作：给数组a中下标从1到3的元素+2

下标 0 1 2 3 4 5
数组a 1 3+2=5 5+2=7 2+2=4 7 10
数组d 2+2=4 2 -3 5-2=3 3

这里不难发现，在执行完这个操作后，差分数组中只有处于1和4位置的元素发生了改变，所以得出结论，当对数组a的[l,r]位置的元素进行更新时，差分数组d只改变了第l元素的位置以及r+1位置的元素的位置，假设更新的值为v，那么可以得出如下结论：

d[l] = d[l]+v;
d[r+1] = d[r+1]-v;

差分数组常用来求前缀和，如果不使用差分数组的话，假设原数组a发生改变，那么每改变一次，都需要遍历一次去更新，同时更新前缀数组，这样的话是肯定会超时的。但使用差分数组来求前缀和时，每次只要更新端点值即可，假如更新的区间为[L,R],那么只需要更新L和R+1位置的数据即可，最后更新数组a时只需a[i] = a[i-1]+d[i]即可，这样就简单多了。

下面是利用差分数组求前缀和的过程

d[1] = a[1]
d[2] = a[2] - a[1]
d[3] = a[3] - a[2]
...
d[n] = a[n] - a[n-1]

sum[n](前n项的和) = d[1] + d[2] + d[3] +...+ d[n]

Tip:差分数组还经常与树状数组一起使用，具体使用方法参照树状数组的博客

模板题：

Color the ball

Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 39829 Accepted Submission(s): 18972

Problem Description

N个气球排成一排，从左到右依次编号为1,2,3….N.每次给定2个整数a b(a <= b),lele便为骑上他的“小飞鸽”牌电动车从气球a开始到气球b依次给每个气球涂一次颜色。但是N次以后lele已经忘记了第I个气球已经涂过几次颜色了，你能帮他算出每个气球被涂过几次颜色吗？

Input

每个测试实例第一行为一个整数N,(N <= 100000).接下来的N行，每行包括2个整数a b(1 <= a <= b <= N)。
当N = 0，输入结束。

Output

每个测试实例输出一行，包括N个整数，第I个数代表第I个气球总共被涂色的次数。

Sample Input

3
1 1
2 2
3 3
3
1 1
1 2
1 3
0

Sample Output

1 1 1
3 2 1

Author

8600

Source

HDU 2006-12 Programming Contest 

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5+5;
int a[maxn],d[maxn];
int n;

int main(){
    while(cin >> n && n){
        memset(a,0,sizeof(a));
        memset(d,0,sizeof(d));
        for(int i = 0 ; i < n ; i++){
            int l,r;
            cin >> l >> r;
            d[l]++,d[r+1]--;
        }
        for(int i = 1 ; i <= n ; i++){
            a[i] = a[i-1] + d[i];
            if(i != n) cout << a[i] << " ";
            else cout << a[i] << endl;
        }
    }
    return 0;
}