树状数组 or 线段树（HDU 1556）

链接：

例题：HDU 1556

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

输入：

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

输出：

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

样例：

input：

1 1 1
3 2 1

 1 #include <stdio.h>
 2 #include <string.h>
 3 const int MAXN=110000;
 4 int n,c[MAXN];
 5 int lowbit(int x)
 6 //计算2^k
 7 {
 8     x=x&-x;
 9     return x;
10 }
11 void update(int num,int val)
12 //向下查询，num是要更新的子节点，val是要修改的值
13 {
14     while(num>0)
15     {
16         c[num]+=val;
17         num-=lowbit(num);
18     }
19 }
20 int getSum(int num)
21 //向上统计每个区间被染色的次数
22 {
23     int sum=0;
24     while(num<=n)
25     {
26         sum+=c[num];
27         num+=lowbit(num);
28     }
29     return sum;
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             //将b以下区间+1
41             update(b,1);
42             //将a以下区间-1
43             update(a-1,-1);
44         }
45         for(int j=1;j<n;j++)
46         {
47             printf("%d ",getSum(j));
48         }
49         printf("%d
",getSum(n));
50     }
51     return 0;
52 }

线段树的写法：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 const int maxn=100010;
 7 int n;
 8 struct node{
 9     int l;
10     int r;
11     int laz;
12     int sum;
13 }e[maxn<<2];
14 void build(int l,int r,int cur)
15 {
16     e[cur].l=l;
17     e[cur].r=r;
18     e[cur].sum=0;
19     e[cur].laz=0;
20     if(l==r)
21         return;
22     int mid=(l+r)/2;
23     build(l,mid,cur<<1);
24     build(mid+1,r,cur<<1|1);
25 }
26 void pushdown(int cur)
27 {
28     if(e[cur].laz!=0)
29     {
30         e[cur<<1].laz+=e[cur].laz;
31         e[cur<<1|1].laz+=e[cur].laz;
32         e[cur].laz=0;
33     }
34     return;
35 }
36 void update(int pl,int pr,int cur)
37 {
38     if(pl<=e[cur].l&&e[cur].r<=pr)
39     {
40         e[cur].laz++;
41         return;
42     }
43     int mid=(e[cur].l+e[cur].r)/2;
44     if(pl<=mid)
45         update(pl,pr,cur<<1);
46     if(pr>mid)
47         update(pl,pr,cur<<1|1);
48 }
49 void update1(int cur)
50 {
51     if(e[cur].l==e[cur].r)
52     {
53         return;
54     }
55     pushdown(cur);
56     update1(cur<<1);
57     update1(cur<<1|1);
58 }
59 int query(int pl,int pr,int cur)
60 {
61     if(pl<=e[cur].l&&e[cur].r<=pr)
62     {
63         return e[cur].laz;
64     }
65     int mid=(e[cur].l+e[cur].r)/2;
66     int ans=0;
67     if(pl<=mid)
68         ans+=query(pl,pr,cur<<1);
69     if(pr>mid)
70         ans+=query(pl,pr,cur<<1|1);
71 return ans;
72 }
73 int main()
74 {
75     int a,b;
76     while(~scanf("%d",&n)&&n)
77     {
78         build(1,100000,1);
79         for(int i=0;i<n;i++)
80         {
81             scanf("%d%d",&a,&b);
82             update(a,b,1);
83         }
84         update1(1);
85         for(int i=1;i<n;i++)
86         {
87             printf("%d ",query(i,i,1));
88         }
89         printf("%d
",query(n,n,1));
90     }
91 return 0;
92 }

树状数组 or 线段树 （HDU 1556）

树状数组 or 线段树（HDU 1556）