线段树
第一部 概念引入
线段树是一种二叉树，也就是对于一个线段，们会用一个二叉树来表示。比如说一个长度为4的线段，们可以表示成这样：
性质：节点i的权值=她的左儿子权值+她的右儿子权值。
们知道，一颗二叉树，她的左儿子和右儿子编号分别是她2和她2+1
再根据刚才的性质，得到式子：tree[i].sum=tree[i2].sum+tree[i2+1].sum;就可以建一颗线段树了！
1.建树：
代码如下：
2.区间查询
们总结一下，线段树的查询方法：
1、如果这个区间被完全包括在目标区间里面，直接返回这个区间的值
2、如果这个区间的左儿子和目标区间有交集，那么搜索左儿子
3、如果这个区间的右儿子和目标区间有交集，那么搜索右儿子
代码：
3.区间点修改
4.区间修改
区间修改和单点查询，们的思路就变为：如果把这个区间加上k，相当于把这个区间涂上一个k的标记，然后单点查询的时候，
就从上跑道下，把沿路的标记加起来就好。这里面给区间贴标记的方式与上面的区间查找类似，原则还是那三条，只不过第一条：
如果这个区间被完全包括在目标区间里面，直接返回这个区间的值变为了如果这个区间如果这个区间被完全包括在目标区间里面，讲这个区间标记k。
6.单点查询
然后就是单点查询了，这个更好理解了，就是dis在哪往哪跑，把路径上所有的标价加上就好了：
进阶线段树
区间修改、区间查询，你可能会认为，把上一章里面的这两个模块加在一起就好了，然后你就会发现你大错特错。
因为如果对于14这个区间，你把13区间+1，相当于把节点12和3标记，但是如果你查询24时，你会发现你加的时没有标记的2节点和没有标记的3~4节点加上去，结果当然是错的。
那么们应该怎么办？这时候pushdown的作用就显现出来了。
你会想到，们只需要在查询的时候，如果们要查的2节点在12区间的里面，那们就可以把12区间标记的那个+1给推下去这样就能顺利地加上了。
怎么记录这个标记呢？们需要记录一个"懒标记"lazytage，来记录这个区间
区间修改的时候，们按照如下原则：
1、如果当前区间被完全覆盖在目标区间里，讲这个区间的sum+k(tree[i].r-tree[i].l+1)*
2、如果没有完全覆盖，则先下传懒标记
3、如果这个区间的左儿子和目标区间有交集，那么搜索左儿子
4、如果这个区间的右儿子和目标区间有交集，那么搜索右儿子
原文创作：希望每天涨粉
