定义：除开最后一层是满二叉树
存储形式：一维数组(堆的储存形式)
算法原理: 我们将查询区间分成几段, 在线段树中找到这几段区间, 根据这几段区间的属性(比如最大值), 求出查询区间的属性(最值). 线段树中的分段必定不会重叠, 按照算法查询下去, 最后合格的几段拼在一起正好就是查询区间. (这个可以画图理解一下, 同时从原理上也是很好理解的, 因为线段树上划分的区间都无重叠, 那你两路合格的区间也一定没有重叠)
算法时间复杂度
因为线段树是每次二分直到分到某一个值为止, 二分时间复杂度就是它的时间复杂度。
区间, 单点修改: $O(4logn)$
查询: $O(4logn)$
所有操作：
1. pushup
2. pushdown(维护懒标记, 延迟标记)
3. modify -> 单点(不需要懒标记也能logn, 该算法根本不需要用到懒标记), 区间(会用到pushdown, 不用的话时间复杂度无法保证logn) $O(logn)$
4. query $O(logn)$
5. build(将一段区间初始化为线段树)
线段树基本要素：
1. 结构体节点(结构体节点中的需要维护的变量, 根据我们看父节点的特性, 需要子节点的哪些特性才能够求出来, 那么结构体就需要维护那些特性, 当然查询的变量时一定要存的)
2. 父节点 x >> 1
3. 左子节点 x << 1
4. 右子节点 x << 1 | 1
注意事项：

• 线段树的储存数组大小一般开4 * N的空间。
• 子区间无交集, 分界点为下取整。

区间修改<利用查询操作的思想和懒标记实现logn时间复杂度>
1. 使用前提: 懒标记只有在需要将区间所有数改变为某个数的时候才必须用, 当对区间加减操作时, 可以用差分解决, 懒标记能不用尽量不用, 因为容易错且复杂。
2. 时间复杂度: $O(logn)$
3. 实例讲解与模板

注意查询操作的一点小变化, 查询区间小于所有已修改区间时, 现查询现修改~
4. F.A.Q
- 什么是懒标记? 懒标记其实就是线段树中一个结构体节点中需要累加维护的变量, 我们通过pushdown操作来维护.

区间问题 – Segment tree, BIT, RMQ, 前缀和, 贪心
线段树与树状数组的区别