线段树:要满足区间合并:维护的某一性质能否合并到一个集合
eg: l mid到mid+1 r 能否合并到l,r 之间
比如 知道左侧区间和和右侧区间和,那么总区间和就知道了
但是如果知道左侧元素种类和右边元素种类,则总区间种类不知道
符合区间加法的例子：
数字之和——总数字之和 = 左区间数字之和 + 右区间数字之和
最大公因数(GCD)——总GCD = gcd( 左区间GCD , 右区间GCD );
最大值——总最大值=max(左区间最大值，右区间最大值)
不符合区间加法的例子：
众数——只知道左右区间的众数，没法求总区间的众数
01序列的最长连续零——只知道左右区间的最长连续零，没法知道总的最长连续零
线段树维护信息的条件之一是:区间信息满足可加性(信息的可加性)
1: 递归建树(类似于堆的建立)
2: 查找(query)
3: 修改 modify 修改之后会改变这值,所以说我们要pushup 一下,然后递归处理
4 pushup 修改,知道了自己的两个儿子,然后递归中进行修改要维护的值 修改值的时候都会出现这个,
5 pushdown 懒标记(目前不知道怎么形容)
懒标记是线段树的精髓所在
1 朴素做法:
使用递归的方式一层层修改(类似于线段树的建立)
但是复杂度很高,
2 懒标记:
对于正好是线段树的区间,我们不继续递归下去,
而是打上一个标记.将来用到它的字区间的时候,
再向下传递

zzuli自豪言:
分裂后一定要pushup
分裂前一定要pushdown
(修改的时候一定要pushup 一下)
线段树要记住这两个
区间修改一般都要进行懒标记
本蒟蒻口胡写的 (斯– 预览里面连空格 回车什么的都显示不出来吗)