在做题时，经常会遇到需要我们维护一个序列的问题，例如给定一个整数序列，每次操作会修改序列某个位置上的数，或是询问序列中某个区间内所有数的和或最大值、最小值。
考虑到暴力算法，单点修改的复杂度为O(1)，询问区间和的单次复杂度为O(区间长度)。
考虑到利用前缀和，询问单次为O(1)，但单点修改为O(区间长度)。
但这类问题的m（询问次数）和n（区间长度）往往是105级别的，这两种方法就都不能用了。
一、什么是线段树
a. 线段树是：利用分治思想处理对一段序列进行大量区间操作(区间修改、区间查询) 的数据结构；
b. 线段树可以在O(nlogn)的时间复杂度内，完成区间修改/区间查询操作。
c. 线段树的叶节点即为原序列，内部节点除了左右儿子之外，还保存着其分管的某段区间信息，如区间和、区间最值。显然，每个结点所分管的区间即为以其为根的子树中所有结点。
二、线段树的拆分原理
a.将［l,n］分解成若干特定的子区间；
b.将每个区间［L,R］都分解为少量特定的子区间；
c.通过对子区间的修改或统计，来实现快速对［L,R］区间的修改、统计。
三、相关算法对比
四、线段树的使用前提
使用线段树的问题，必须符合区间加法：也就是通过合并区间的解，一定能得到问题的最终解。
可以使用线段树问题举例：
a. 数字和问题：总数字之和=左区间数字之和+右区间数字之和；
b. 最大公约数：总gcd = gcd(左区间GCD ,右区间GCD)；
c. 最大值问题：总最大值=max(左区间最大值，右区间最大值)；
不能用线段树求解问题举例：
a. 众数：无法根据左右区间众数，得知总区间众数；
b. 最长连续出现的字母：无法根据左右区间的最长连续出现的字母，得知总区间的解;
五、线段树建树操作
六、线段树单点修改
七、线段树区间査询
八、区间修改：延迟标记与标记永久化 有时我们需要解决的不只是单点修改区间询问，而是区间修改、区间询问。以区间内所有数同时加上一个值，以及单点询问某位置的值为例。考虑在每个节点上维护一个值add，表示这个节点所对应的区间内的所有数都加上了add。区间修改时，将区间拆成许多子区间，并在线段树对应的节点上修改。
add[k]：延迟标记（懒标记），为编号为k的结点的所有子结点，都增加一个值。（注意：不包含当前的结点，当前的结点会立刻将和的增量计算出来）。
当不向下递归时，当前结点就需要计算增量，并打上延迟标记。
标记下放（pushdown）：当需要从有延迟标记的结点向下递归时，需要将当前的延迟标记下放到子结点，并清除当前延迟标记的值。
pushup：回溯利用子结点更新父结点。