蓝桥杯 分苹果（线段树）---------C语言—菜鸟级

小朋友排成一排，老师给他们分苹果。
小朋友从左到右标号1…N。有M个老师，每次第i个老师会给第Li个到第Ri个，一共Ri-Li+1个小朋友每人发Ci个苹果。
最后老师想知道每个小朋友有多少苹果。

数据规模和约定
100%的数据，N、M≤100 000，1≤Li≤Ri≤N，0≤Ci≤100。

输入
第一行两个整数N、M，表示小朋友个数和老师个数。
接下来M行，每行三个整数Li、Ri、Ci，意义如题目表述。
输出
一行N个数，第i个数表示第i个小朋友手上的水果。
样例输入
5 3
1 2 1
2 3 2
2 5 3
样例输出
1 6 5 3 3

#include<stdio.h> 
#define N 100004 
typedef struct Node{  
    int l,r,v;  
} L;
L node[N*4]; //线段树的每个节点  其中包括三个参数 l为线段左端点的值 r:线段右端点的值  v：该节点所存储的值 
void Init(int now,int le,int ri){    //构建线段树 并将结点的值初始化全部为0   
      if(le==ri){  
        node[now].l=le;  
        node[now].r=ri;  
        node[now].v=0;  
        return;  
      }//如果线段的左端点==线段的右端点  那么即是最后的叶子结点 return  
      int mid=(le+ri)>>1;  //求出中点
      int next=now<<1;    //将结点的序号*2即下一代节点（子结点）序号；
      Init(next,le,mid);  //构建左子树(左区域 ） 
      Init(next+1,mid+1,ri);  //构建右子树(右区域 ） 
      node[now].l=le;  //给当前结点的线段左右端点赋值
      node[now].r=ri;  
      node[now].v=0;  //给结点赋值
}  
void f(int now,int le,int ri,int add){       //在线段树中寻找对应的区间  给对应该区间的结点加上该发的
//苹果数，即为在那个结点下的所有的子节点的区间里的小孩均会被发苹果。 （pinrt函数中会提到）
    if(node[now].l==le&&node[now].r==ri){  
        node[now].v+=add;  
        return;  
    }  //给对应该区间的结点加上发的苹果数
    int mid=(node[now].l+node[now].r)>>1;//求出中点  
    int next=now<<1;  //结点的序号*2(找到子节点） 
     if(ri<=mid){  
        f(next,le,ri,add);  //如果寻找的区间的右端点小于中点 则在左边寻找
     }      
    else if(le>mid){  
         f(next+1,le,ri,add);  //反之在右边寻找
    }          
    else  
    {  
        f(next,le,mid,add);  //如果横跨两边  左右两边都寻找
        f(next+1,mid+1,ri,add);  
    }  
}   
void out(int now){  
    if(node[now].l==node[now].r){  
       printf("%d ",node[now].v);  
        return;  
        }   //如果是最后的叶子结点 输出小朋友的苹果总数
    int next=now<<1;  
    //父亲的范围大 包含的儿子结点的区间   所以父亲下面儿子结点也要加上父亲结点被发的苹果数  
    node[next].v+=node[now].v;  
    out(next);  
    node[next+1].v+=node[now].v;  
    out(next+1);  
}  
int main(){  
    int n,m,i,a,b,c;  
    while(scanf("%d%d",&n,&m)!=EOF){  
        Init(1,1,n);  
        for(i=0;i<m;i++){  
            scanf("%d%d%d",&a,&b,&c);  
            f(1,a,b,c);  
        }  
        out(1);  
    }  
    return 0;  
}

  

 

  
 
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
 

文章来源: fivecc.blog.csdn.net，作者：Five-菜鸟级，版权归原作者所有，如需转载，请联系作者。

原文链接：fivecc.blog.csdn.net/article/details/79942492