WU-蓝桥杯算法提高VIP-分苹果 （C++代码）(线段树）

解题思路:

这个题解是我从博客上摘抄下来的 
和大家一起分享
这个题目用到了线段树的知识  因为用普通的循环  我们得到的时间复杂度为O(m*n) 肯定会超时
 
这个题目比较复杂 我写的也不是很好  大家多看几遍  多理解 
个人水平 有限  欢迎批评指正~

所谓的线段树如下图：

每个数的结点 里面包含的是线段  

比如根结点包含的线段范围为[a,b]

那么它的左子结点 包含线段的范围为[a,(a+b)/2]   右子结点包含的线段范围为[(a+b)/2+1,b]

(a+b)/2即为mid,如此这样一直分支下去 直到每个结点中包含的线段成了一个点  线段树便构建好了

参考代码:

#include <iostream>  
#include <string.h>  
#include <algorithm>  
#include <cstdio>  
#include <math.h>  
using namespace std;  
const int N=100000+10;  
struct Node{  
    int l,r,v;  
}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 ne=now<<1;    //将结点的序号*2；
      Init(ne,le,mid);  //构建左子树
      Init(ne+1,mid+1,ri);  //构建右子树
      node[now].l=le;  //给当前结点的线段左右端点赋值
      node[now].r=ri;  
      node[now].v=0;  //给结点赋值
}  
void insert(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 ne=now<<1;  //结点的序号*2，方便构建新的结点
     if(ri<=mid){  
        insert(ne,le,ri,add);  //如果寻找的区间的右端点小于中点 则在左边寻找
     }      
    else if(le>mid){  
         insert(ne+1,le,ri,add);  //反之在右边寻找
    }          
    else  
    {  
        insert(ne,le,mid,add);  //如果横跨两边  左右两边都寻找
        insert(ne+1,mid+1,ri,add);  
    }  
}   
void print(int now){  
    if(node[now].l==node[now].r){  
        cout<<node[now].v<<" ";  
        return;  
        }   //如果是最后的叶子结点 输出小朋友的苹果总数
    int ne=now<<1;  
    //父亲的范围大 包含的儿子结点的区间   所以父亲下面儿子结点也要加上父亲结点被发的苹果数  
    node[ne].v+=node[now].v;  
    print(ne);  
    node[ne+1].v+=node[now].v;  
    print(ne+1);  
}  
int main(){  
    int n,m,i,a,b,c;  
    while(cin>>n>>m){  
        Init(1,1,n);  
        for(i=0;i<m;i++){  
            cin>>a>>b>>c;  
            insert(1,a,b,c);  
        }  
        print(1);  
    }  
    return 0;  
}