差分数组

给定一个数组A：A[1]、A[2]、A[3]、A[4]、A[5].......A[i]，令数组B为：B[1]、B[2]、B[3]、B[4].......B[i]，满足B[1]=A[1]，B[2]=A[2]-A[1]，B[3]=A[3]-A[2]，B[4]=A[4]-A[3]，B[5]=A[5]-A[5]........B[i]=A[i]-A[i-1]，则称数组B为差分数组。

进一步对数组B分析，可以发现数组B的前缀和Sum，存在Sum[i]=B[1]+B[2]+B[3]+B[4]+B[5]........+B[i]=A[1]+A[2]-A[1]+A[3]-A[2]+A[4]-A[3]+A[5]-A[5]......+A[i]-A[i-1]=A[i]，即前缀和Sum[i]=A[i]。

意义 

若存在这样的一个问题，对数组A的某个区间【start,end】多次加某个数num，一次操作需要对数组A操作（end-start+1）次，若需要操作n次，那么时间复杂度就很高！但如果在数组A的差分数组中每次只需要操作2次，即B[start]+num，B[end+1]-num。再通过数组B重构出数组A，就可以实现在区间【start,end】加上num的效果，而且对于区间【0,start-1】和【end+1,n】没有丝毫影响！

 例题1：美团笔试

一条直线上等距离放置了n台路由器。路由器自左向右从1到n编号。第i台路由器到第j台路由器的距离为| i-j |。  每台路由器都有自己的信号强度，第i台路由器的信号强度为ai。所有与第i台路由器距离不超过ai的路由器可以收到第i台路由器的信号（注意，每台路由器都能收到自己的信号）。问一共有多少台路由器可以收到至少k台不同路由器的信号。

输入描述：

输入第一行两个数n , k（1≤n , k≤10^5）
第二行n个数, a1 , a2 , a3……… , an（0≤ai≤10^9）

输出描述：

输出一个数，一共有多少台路由器可以收到至少k台不同路由器的信号

示例1

输入：

4 4

3 3 3 3

输出：

4

#include <bits/stdc++.h>
using namespace std;

int main(int argc,char* argv[]){
    int n,k;
    cin>>n>>k;
    int chafen[n+1];//差分数组
    memset(chafen,0,sizeof(chafen));
    int num=0;
    for(int i=0;i<n;++i){
        cin>>num;
        chafen[max(0,i-num)]++;//最左发送范围
        chafen[min(n,i+num+1)]--;//最右发送范围
    }
    int ret=0,sum=0;
    for(int i=0;i<n;++i){
        sum+=chafen[i];//还原出数组第i项
        if(sum>=k) ret++;
    }
    cout<<ret<<endl;
    return 0;
}

 例题2： Color the ball

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

#include <bits/stdc++.h>
using namespace std;

int main(int argc,char* argv[]){
    int n,x,y;
    cin>>n>>k;
    int arr[100010];
    while(scanf("%d",&n)&&n){
         memset(arr,0,sizeof(arr));
         for(int i=1;i<=n;++i){
             scanf("%d%d",&x,&y);
             arr[x]++;
             arr[y+1]--;
         }
         for(int i=1;i<=n;++i){
             arr[i]+=arr[i-1];
             printf("%d%c",a[i],i==n?'\n':' ');
         }
    }
    return 0;
}