hdu 1556 树状数组+点查询

树状数组

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

用了树状数组的区间更新单点查找（一般为单点更新区间查找）

例如区间（2,4）加1

则Updata(2,1) Updata(4+1,-1)

实现了更新（2,4）的值而不改变其他值

求Sum时即可得到某一点的值

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 
 5 const int MAXN=100010;
 6 int c[MAXN];
 7 int n;
 8 
 9 int lowbit(int x)
10 {
11     return x&(-x);
12 }
13 void add(int i,int val)
14 {
15     while(i<=n)
16     {
17         c[i]+=val;
18         i+=lowbit(i);
19     }
20 }
21 int sum(int i)
22 {
23     int s=0;
24     while(i>0)
25     {
26         s+=c[i];
27         i-=lowbit(i);
28     }
29     return s;
30 }
31 int main()
32 {
33     int a,b;
34     while(scanf("%d",&n),n)
35     {
36         memset(c,0,sizeof(c));
37         for(int i=0;i<n;i++)
38         {
39             scanf("%d%d",&a,&b);
40             add(a,1);
41             add(b+1,-1);
42         }
43         for(int i=1;i<n;i++)
44           printf("%d ",sum(i));
45         printf("%d
",sum(n));
46     }
47     return 0;
48 }