一、引例
1、区间最值
【例题1】给定一个n（n <= 100000）个元素的数组A，有m(m <= 100000)个操作，共两种操作：
1、Q a b 询问：表示询问区间[a, b]的最大值；
2、C a c 更新：表示将第a个元素变成c；
静态的区间最值可以利用RMQ来解决，但是RMQ的ST算法是在元素值给定的情况下进行的预处理，然后在O(1)时间内进行询问，这里第二种操作需要实时修改某个元素的值，所以无法进行预处理。
由于每次操作都是独立事件，所以m次操作都无法互相影响，于是时间复杂度的改善只能在单次操作上进行优化了，我们可以试想能否将任何的区间[a, b]（a < b）都拆成log(b-a+1)个小区间，然后只对这些拆散的区间进行询问，这样每次操作的最坏时间复杂度就变成log(n)了。
2、区间求和
【例题2】给定一个n(n <= 100000)个元素的数组A，有m(m <= 100000)个操作，共两种操作：
1、Q a b 询问：表示询问区间[a, b]的元素和；
2、A a b c 更新：表示将区间[a, b]的每个元素加上一个值c；
先来看朴素算法，两个操作都用遍历来完成，单次时间复杂度在最坏情况下都是O(n)的，所以m次操作下来总的时间复杂度就是O(nm)了，复杂度太高。
再来看看树状数组，对于第一类操作，树状数组可以在log(n)的时间内出解；然而第二类操作，还是需要遍历每个元素执行add操作，复杂度为nlog(n)，所以也不可行。这个问题同样也需要利用区间拆分的思想。
线段树就是利用了区间拆分的思想，完美解决了上述问题。
二、线段树的基本概念
1、二叉搜索树
线段树是一种二叉搜索树，即每个结点最多有两棵子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。线段树的每个结点存储了一个区间（线段），故而得名。
图二-1-1
如图二-1-1所示，表示的是一个[1, 6]的区间的线段树结构，每个结点存储一个区间（注意这里的存储区间并不是指存储这个区间里面所有的元素，而是只需要存储区间的左右端点即可），所有叶子结点表示的是单位区间（即左右端点相等的区间），所有非叶子结点（内部结点）都有左右两棵子树，对于所有非叶子结点，它表示的区间为[l, r]，那么令mid为(l + r)/2的下整，则它的左儿子表示的区间为[l, mid]，右儿子表示的区间为[mid+1, r]。基于这个特性，这种二叉树的内部结点，一定有两个儿子结点，不会存在有左儿子但是没有右儿子的情况。
基于这种结构，叶子结点保存一个对应原始数组下标的值，由于树是一个递归结构，两个子结点的区间并正好是父结点的区间，可以通过自底向上的计算在每个结点都计算出当前区间的最大值。
需要注意的是，基于线段树的二分性质，所以它是一棵平衡树，树的高度为log(n)。
2、数据域
了解线段树的基本结构以后，看看每个结点的数据域，即需要存储哪些信息。
首先，既然线段树的每个结点表示的是一个区间，那么必须知道这个结点管辖的是哪个区间，所以其中最重要的数据域就是区间左右端点[l, r]。然而有时候为了节省全局空间，往往不会将区间端点存储在结点中，而是通过递归的传参进行传递，实时获取。
再者，以区间最大值为例，每个结点除了需要知道所管辖的区间范围[l, r]以外，还需要存储一个当前区间内的最大值max。
图二-2-1
以数组A[1:6] = [1 7 2 5 6 3]为例，建立如图二-2-1的线段树，叶子结点的max域为数组对应下标的元素值，非叶子结点的max域则通过自底向上的计算由两个儿子结点的max域比较得出。这是一棵初始的线段树，接下来讨论下线段树的询问和更新操作。
在询问某个区间的最大值时，我们一定可以将这个区间拆分成log(n)个子区间，并且这些子区间一定都能在线段树的结点上找到（这一点下文会着重讲解），然后只要比较这些结点的max域，就能得出原区间的最大值了，因为子区间数量为log(n)，所以时间复杂度是O( log(n) )。
更新数组某个元素的值时我们首先修改对应的叶子结点的max域，然后修改它的父结点的max域，以及祖先结点的max域，换言之，修改的只是线段树的叶子结点到根结点的某一条路径上的max域，又因为树高是log(n)，所以这一步操作的时间复杂度也是log(n)的。
3、指针表示
接下来讨论一下结点的表示法，每个结点可以看成是一个结构体指针，由数据域和指针域组成，其中指针域有两个，分别为左儿子指针和右儿子指针，分别指向左右子树；数据域存储对应数据，根据情况而定(如果是求区间最值，就存最值max；求区间和就存和sum)，这样就可以利用指针从根结点进行深度优先遍历了。
以下是简单的线段树结点的C++结构体：
|
1 2 3 4 |
struct treeNode { Data data; // 数据域 treeNode *lson, *rson; // 指针域 }*root; |
4、数组表示
实际计算过程中，还有一种更加方便的表示方法，就是基于数组的静态表示法，需要一个全局的结构体数组，每个结点对应数组中的一个元素，利用下标索引。
例如，假设某个结点在数组中下标为p，那么它的左儿子结点的下标就是2*p，右儿子结点的下标就是2*p+1(类似于一般数据结构书上说的堆在数组中的编号方式)，这样可以将所有的线段树结点存储在相对连续的空间内。之所以说是相对连续的空间，是因为有些下标可能永远用不到。
还是以长度为6的数组为例，如图二-4-1所示，红色数字表示结点对应的数组下标，由于树的结构和编号方式，导致数组的第10、11位置空缺。
图二-4-1
这种存储方式可以不用存子结点指针，取而代之的是当前结点的数组下标索引，以下是数组存储方式的线段树结点的C++结构体：
|
1 2 3 4 5 6 |
struct treeNode { Data data; // 数据域 int pid; // 数组下标索引 int lson() { return pid << 1; } int rson() { return pid<<1|1; } // 利用位运算加速获取子结点编号 }nodes[ MAXNODES ]; |
接下来我们关心的就是MAXNODES的取值了，由于线段树是一种二叉树，所以当区间长度为2的幂时，它正好是一棵满二叉树，数组存储的利用率达到最高（即100%），根据等比数列求和可以得出，满二叉树的结点个数为2*n-1，其中n为区间长度（由于C++中数组长度从0计数，编号从1开始，所以MAXNODES要取2*n）。那么是否对于所有的区间长度n都满足这个公式呢？答案是否定的，当区间长度为6时，最大的结点编号为13，而公式算出来的是12（2*6）。
那么 MAXNODES 取多少合适呢？
为了保险起见，我们可以先找到比n大的最小的二次幂，然后再套用等比数列求和公式，这样就万无一失了。举个例子，当区间长度为6时，MAXNODES = 2 * 8；当区间长度为1000，则MAXNODES = 2 * 1024；当区间长度为10000，MAXNODES = 2 * 16384。至于为什么可以这样，明眼人一看便知。
三、线段树的基本操作
线段树的基本操作包括构造、更新、询问，都是深度优先搜索的过程。
1、构造
线段树的构造是一个二分递归的过程，封装好了之后代码非常简洁，总体思路就是从区间[1, n]开始拆分，拆分方式为二分的形式，将左半区间分配给左子树，右半区间分配给右子树，继续递归构造左右子树。
当区间拆分到单位区间时（即遍历到了线段树的叶子结点），则执行回溯。回溯时对于任何一个非叶子结点需要根据两棵子树的情况进行统计，计算当前结点的数据域，详见注释4。
|
1 2 3 4 5 6 7 8 9 |
void segtree_build(int p, int l, int r) { nodes[p].reset(p, l, r); // 注释1 if (l < r) { int mid = (l + r) >> 1; segtree_build(p<<1, l, mid); // 注释2 segtree_build(p<<1|1, mid+1, r); // 注释3 nodes[p].updateFromSon(); // 注释4 } } |
注释1：初始化第p个结点的数据域，根据实际情况实现reset函数
注释2：递归构造左子树
注释3：递归构造右子树
注释4：回溯，利用左右子树的信息来更新当前结点，updateFromSon这个函数的实现需要根据实际情况进行求解，在第四节会详细讨
构造线段树的调用如下：segtree_build(1, 1, n);
2、更新
线段树的更新是指更新数组在[x, y]区间的值，具体更新这件事情是做了什么要根据具体情况而定，可以是将[x, y]区间的值都变成val（覆盖），也可以是将[x, y]区间的值都加上val（累加）。
更新过程采用二分，将[1, n]区间不断拆分成一个个子区间[l, r]，当更新区间[x, y]完全覆盖被拆分的区间[l, r]时，则更新管辖[l, r]区间的结点的数据域，详见注释2和注释3。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
void segtree_insert(int p, int l, int r, int x, int y, ValueType val) { if( !is_intersect(l, r, x, y) ) { // 注释1 return ; } if( is_contain(l, r, x, y) ) { // 注释2 nodes[p].updateByValue(val); // 注释3 return ; } nodes[p].giveLazyToSon(); // 注释4 int mid = (l + r) >> 1; segtree_insert(p<<1, l, mid, x, y, val); // 注释5 segtree_insert(p<<1|1, mid+1, r, x, y, val); // 注释6 nodes[p].updateFromSon(); // 注释7 } |
注释1：区间[l, r]和区间[x, y]无交集，直接返回
注释2：区间[x, y]完全覆盖[l, r]
注释3：更新第p个结点的数据域，updateByValue这个函数的实现需要根据具体情况而定，会在第四节进行详细讨论
注释4：这里先卖个关子，参见第五节的lazy-tag
注释5：递归更新左子树
注释6：递归更新右子树
注释7：回溯，利用左右子树的信息来更新当前结点
更新区间[x, y]的值为val的调用如下：segtree_insert(1, 1, n, x, y, val);
3、询问
线段树的询问和更新类似，大部分代码都是一样的，只有红色部分是不同的，同样是将大区间[1, n]拆分成一个个小区间[l, r]，这里需要存储一个询问得到的结果ans，当询问区间[x, y]完全覆盖被拆分的区间[l, r]时，则用管辖[l, r]区间的结点的数据域来更新ans，详见注释1的mergeQuery接口。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
void segtree_query (int p, int l, int r, int x, int y, treeNode& ans) { if( !is_intersect(l, r, x, y) ) { return ; } if( is_contain(l, r, x, y) ) { ans.mergeQuery(p); // 注释1 return; } nodes[p].giveLazyToSon(); int mid = (l + r) >> 1; segtree_query(p<<1, l, mid, x, y, ans); segtree_query(p<<1|1, mid+1, r, x, y, ans); nodes[p].updateFromSon(); // 注释2 } |
注释1：更新当前解ans，会在第四节进行详细讨论
注释2：和更新一样的代码，不再累述
四、线段树的经典案例
线段树的用法千奇百怪，接下来介绍几个线段树的经典案例，加深对线段树的理解。
1、区间最值
区间最值是最常见的线段树问题，引例中已经提到。接下来从几个方面来讨论下区间最值是如何运作的。
数据域：
|
1 2 3 |
int pid; // 数组索引 int l, r; // 结点区间(一般不需要存储) ValyeType max; // 区间最大值 |
初始化：
|
1 2 3 4 |
void treeNode::reset(int p, int l, int r) { pid = p; max = srcArray[l]; // 初始化只对叶子结点有效 } |
单点更新：
|
1 2 3 |
void treeNode::updateByValue(ValyeType val) { max = val; } |
合并结点：
|
1 2 3 |
void treeNode::mergeQuery(int p) { max = getmax( max, nodes[p].max ); } |
回溯统计：
|
1 2 3 4 |
void treeNode::updateFromSon() { max = nodes[ lson() ].max; mergeQuery( rson() ); } |
结合上一节线段树的基本操作，在构造线段树的时候，对每个结点执行了一次初始化，初始化同时也是单点更新的过程，然后在回溯的时候统计，统计实质上是合并左右结点的过程，合并结点做的事情就是更新最大值；询问就是将给定区间拆成一个个能够在线段树结点上找到的区间，然后合并这些结点的过程，合并的结果ans一般通过引用进行传参，或者作为全局变量，不过尽量避免使用全局变量。
2、区间求和
区间求和问题一般比区间最值稍稍复杂一点，因为涉及到区间更新和区间询问，如果更新和询问都只遍历到询问（更新）区间完全覆盖结点区间的话，会导致计算遗留，举个例子来说明。
用一个数据域sum来记录线段树结点区间上所有元素的和，初始化所有结点的sum值都为0，然后在区间[1, 4]上给每个元素加上4，如图四-2-1所示：
图四-2-1
图中[1, 4]区间完全覆盖[1, 3]和[4, 4]两个子区间，然后分别将值累加到对应结点的数据域sum上，再通过回溯统计sum和，最后得到[1, 6]区间的sum和为16，看上去貌似天衣无缝，但是实际上操作一多就能看出这样做是有缺陷的。例如当我们要询问[3, 4]区间的元素和时，在线段树结点上得到被完全覆盖的两个子区间[3, 3]和[4, 4]，累加区间和为0 + 4 = 4，如图四-2-2所示。
图四-2-2
这是因为在进行区间更新的时候，由于[1, 4]区间完全覆盖[1, 3]区间，所以我们并没有继续往下遍历，而是直接在[1, 3]这个结点进行sum值的计算，计算完直接回溯。等到下一次访问[3, 3]的时候，它并不知道之前在3号位置上其实是有一个累加值4的，但是如果每次更新都更新到叶子结点，就会使得更新的复杂度变成O(n)，违背了使用线段树的初衷，所以这里需要引入一个lazy-tag的概念。
所谓lazy-tag，就是在某个结点打上一个“懒惰标记”，每次更新的时候只要更新区间完全覆盖结点区间，就在这个结点打上一个lazy标记，这个标记的值就是更新的值，表示这个区间上每个元素都有一个待累加值lazy，然后计算这个结点的sum，回溯统计sum。
当下次访问到有lazy标记的结点时，如果还需要往下访问它的子结点，则将它的lazy标记传递给两个子结点，自己的lazy标记置空。
这就是为什么在之前在讲线段树的更新和询问的时候有一个函数叫giveLazyToSon了。接下来看看一些函数的实现。
数据域：
|
1 2 3 4 |
int pid; |
