水题：树状数组的巧妙运用

Color the ball
N个气球排成一排，从左到右依次编号为1,2,3....N.每次给定2个整数a b(a <= b),lele便为骑上他的“小飞鸽"牌电动车从气球a开始到气球b依次给每个气球涂一次颜色。但是N次以后lele已经忘记了第I个气球已经涂过几次颜色了，你能帮他算出每个气球被涂过几次颜色吗？
题意很简单，每次都有a到b的气球加一，所以很快就写出了代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string.h>
#define MMAX 100005
using namespace std;
int C[MMAX];
void main()
{
    int i,j,n,m,k,l;
    while(scanf("%d",&n)&&n!=0)
    {
        memset(C,0,sizeof (C));
        for (i=0;i<n;i++)
        {
            scanf("%d%d",&k,&l);
            for(j=k;j<=l;j++)
                C[j]++;
        }
        for (i=1;i<=n;i++)
        {
            printf("%d",C[i]);
            if (i!=n)
                printf(" ");
        }
        printf("\n");
    }
}

不出所料，是超时的，所以不得不做的是分析浪费时间的原因和相应的解决方案。
遍历输出的方面是不能改的，因为每一次遍历都需要输出一位数，那么浪费时间的主要步骤就是累加了，既然不能从a到b逐个加，那么就应该找一个方法尽量使该加法得到最简化。
真的是非常巧妙的运用，在做题时如果想不到可以直接使用线段树，但是代码不会如此精简。
首先我们以数组A的每一个结点来代替一个气球被染色的次数：

如图，便是最开始的思想了，那么又该如何优化呢？同时，又该怎样运用到求和当中去呢？可以如此处理：

这样，只在起始位置加上一个单位，那么如果要输出的是第五个气球，除了第三个以外都是零，那么就是1了，需要注意的是，每次染色都是在一个范围 内的，为了避免之后的气球在累加的时候也会数目增多，如图，假设染色范围是（3，6），那么，只需要在6+1个气球处减1即可：

不妨多举几个例子验证一下，把前n项求和，得到的便是第n个气球的染色次数。

#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;

int c[100010];
int n;
int lowbit(int x){
    return x&-x;
}

void modify(int pos,int val){
    while(pos<=n){//n-->b;
        c[pos]+=val;
        pos+=lowbit(pos);
    }
}

int getr(int pos){
    int sum=0;
    while(pos>0){
        sum+=c[pos];
        pos-=lowbit(pos);
    }
    return sum;
}
int main(){
    int a,b,i;
    while(cin>>n,n){
        memset(c,0, sizeof(c));
        for(i=0;i<n;i++){
            scanf("%d%d",&a,&b);
            modify(a,1);
            modify(b+1, -1);
        }
        for( i=1;i<=n;i++){
            printf("%d%c",getr(i)," \n"[i==n]);
        }
    }
    return 0;
}