HDU 1556

原题：

http://acm.hdu.edu.cn/showproblem.php?pid=1556

这道题是线段树的区间更新，单点查询问题，我在之前的博文里写出了线段树的具体的实现，以及怎样运用线段树解决RMQ问题，地址如下：

http://www.cnblogs.com/zqy123/p/4899197.html

运用之前的线段树的知识，稍加思考，就能做出很好的变通。这道题一个一个更新肯定是会超时的，题目每次给出一个区间段的更新，也就是去更新线段树的一个区间段。（这里是这道题的关键！）最后，再从根节点开始，从头向下，把父节点的值加到子节点上，这样，最后的叶子节点的值就是对应点的被涂色次数。

有一个地方大家可能会有疑惑的是，如果更新的区间正好与当前节点只有一个边界重合怎么办？也就是说，更新区间的时候，一个节点所维护区间的其中一个节点要更新，这时，就不能更新这个节点所维护区间的值了，就要进入这个区间，直接更改叶子节点的值。

我会在代码中再多做一点注释，有关线段树具体的实现，就不再赘述了，大家可以点我上面的链接参考我之前的博文~

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define maxn 100005
 4 int n,k;
 5 int tree[4*maxn];
 6 void init(){
 7     k = 1;
 8     while(k<n)
 9         k<<=1;
10     memset(tree,0,sizeof(tree));
11 }
12 void query(int a,int b,int index,int l,int r){
13     if(a>r||b<l)
14         return;
15     //这里当更新的区间与该节点维护的区间只有一个边界重合的时候，就会直接更新叶子节点的 
16     if(r-l==1){
17         if(b==l){
18             tree[index*2]++;
19             return;
20         }
21         if(a==r){
22             tree[index*2+1]++;
23             return;
24         }
25     }
26     if(a<=l&&b>=r){
27         tree[index]++;
28     }else{
29         query(a,b,index*2,l,(l+r)/2);
30         query(a,b,index*2+1,(l+r)/2+1,r);
31     }
32 }
33 int main(){
34     while(scanf("%d",&n)!=EOF&&n){
35         int a,b;
36         init();
37         for(int i = 0;i<n;i++){
38             scanf("%d%d",&a,&b);
39             query(a,b,1,1,k);
40         }
41         //这里就是从根节点向下更新每个节点的值，叶子节点就是对应的每个气球的涂色的次数 
42         for(int i = 1;i<k;i++){
43             tree[2*i] += tree[i];
44             tree[2*i+1] += tree[i];
45         }
46         for(int i = k;i<k+n-1;i++)
47             printf("%d ",tree[i]);
48         printf("%d
",tree[k+n-1]);
49     }
50     return 0;
51 }

PS:看到网上很多讨论这道题也可以用树状数组来做，但是我还不会（= =），所以等我学会了我会继续更新的。。。