线段树，也称为区间树。线段树是一棵二叉树，树上每个节点对应一个线段（区间），同一层节点所代表的区间，相互不会重叠。叶子节点的区间是单位长度，不可再分。
线段树适用于和区间统计相关的问题。比如某些数据可以按区间进行划分，按区间动态进行修改，而且需要按区间多次进行查询，那么使用线段树可以达到较快的查询速度。
线段树细分为：离散型和连续型
连续型线段树和离散型线段树区别有：
- 叶子节点：离散型中，叶子节点是[i,i]，而连续型中则是[i,i+1]
- 区间分解：离散型中，一段区间向下分解为[l,m]和[m+1,r]，而在连续型中分解为[l,m]和[m,r]
离散型线段树可以为下图
连续型线段树则可以为下图
1. 离散型区间树
1.1 单点更新
- hiho 1077: 线段树最基础的单点更新和区间查询
1.2 区间更新
如果是对线段树中某一段区间进行统一的更新，更新函数完全没有必要更新到叶子节点，巧妙地利用懒惰标记优化更新以及查询的时间复杂度：
如果当前正在遍历的线段树节点 正好 等于需要更新的区间，那么通过设置该节点的懒惰标记，则无须继续向下（子节点方向）遍历更新。但需要注意的时，设置懒惰标记时应该立即更新相应节点维护的数据值，此数据值将用于更新父节点的数据值，懒惰标记的目的仅仅是在将来的某个时候去更新子节点的数据值。如果需要更新或查询的区间在当前节点的子节点中（更新或查询区间小于当前节点区间），而且当前节点存在懒惰标记，说明当前节点的子孙节点们维数的数据值都处于未更新状态，因此需要将当前节点的标记进行下放，直到遇到某节点的区间等于需要查询或更新的区间停止遍历。
1.3 线段树的应用
- hihocoder 1116: 线段树的应用，难点在于设计好线段树节点需要保存哪些信息，以及如何自底向上动态更新这些信息。
2. 连续型线段树
hiho 1079：利用连续型线段树解决
References
- 有一份PKU讲解线段树的PPT