介绍:
线段树是一棵二叉搜索树，思想与分治很想，把一段区间平分平分再平分，平分到不能平分为止，可以进行方便的区间修改和区间查询，当然，树状数组能做的单点修改、单点查询，线段树也可以更好地实现，总之，线段树是树状数组的升级版，此外，线段树能做的平衡树也能做，但平衡树码量太大，考场上一般写不出来，其次有些特殊的线段树如权值线段树也可以水过平衡树，可见，线段树的应用还是十分广泛的
建树：
一般的线段树都是递归建树，当然，也有一种不用递归建树的线段树，即非递归线段树——zkw 线段树
当然，zkw 线段树并不是我们现在的主角，我们讲一下递归建树的操作
首先，可以设置三个方便的宏定义
typedef long long ll;
#define ls (p << 1)
#define rs (p << 1 | 1)
#define mid ((l + r) >> 1)
// ls 左儿子 rs 右儿子 mid 中间值
因为线段树是棵二叉树，，至于这个
区间修改
还是刚刚的图
修改区间 ，它的含义是对当前节点的区间中所有的元素都进行一个操作，
其他
，非递归线段树，因为不递归，跑的是真的很快，但是不好理解，其次在竞赛中，初学者是真的不会用这个去做题，所以对像我这样的蒟蒻而言，也就拿它玩玩，水水模板，然后就吃灰了，这里给出洛谷普通线段树 \(1\) 的 zkw 线段树代码
其他方面的这些东西，有些很有用，有些也就图一乐，以后如果学会了，我会来补坑的。
标记永久化：「学习笔记」线段树标记永久化
可持久化线段树（权值线段树）：「学习笔记」可持久化线段树