学步园

基础  树状数组

每输入一组数，就对染色次数进行修改；

树状数组中的每个节点都代表了一段线段区间，每次更新的时候，根据树状数组的特性可以把b以前包含的所有区间都找出来，然后把b以前的区间全部加一次染色次数。然后，再把a以前的区间全部减一次染色次数，这样就修改了树状数组中的[a,b]的区间染色次数，查询每一个点总的染色次数的时候，就可以直接向上统计每个父节点的值，就是包含这个点的所有区间被染色次数，这就是树状数组中向下查询，向上统计的典型应用

<span style="font-size:14px;">#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int s[100005],a;
int low(int i)
{
    return i&(-i);
}

void show(int q,int w)
{
    while(q>0)
    {
        s[q]+=w;
        q-=low(q);
    }
}
int yy(int num)//向上统计每个区间被染色的次数
{
    int sum=0;
    while(num<=a)
    {
        sum+=s[num];
        num+=low(num) ;
    }
    return sum;
}

int main()
{
    int b,c;
    while(scanf("%d",&a)&&a)
    {
        memset(s,0,sizeof(s));
        for(int i=1;i<=a;i++)
        {
            scanf("%d %d",&b,&c);
            show(b-1,-1);
            show(c,1);
        }
        for(int i=1;i<a;i++)
        {
            printf("%d ",yy(i));
        }
        printf("%d\n",yy(a));
    }
    return 0;
}</span>