例题：小白逛公园
（似乎线段树 macw 写过了，不管了看看能不能再水一篇
本篇只讲基础线段树。以下内容以求区间和线段树为例。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
前置知识：
二分、分治思想，堆式建树。
对于节点 iii，他的左孩子节点索引为 2×i2\times i2×i，右孩子索引为 2×i+12\times i+12×i+1。这样我们可以将线段树储存在数组中。我们先准备两个取儿子函数，其中 now 为当前节点，后面要用。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
什么是线段树？
> 线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。
> 线段树可以在 O(logn)\mathcal{O}(\log n)O(logn) 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。
> —— OIOIOI WikiWikiWiki
线段树将一个区间按照递归顺序逐步往下分解，每个长度大于 111 的区间被分解为两个小区间，这些小区间会被继续分解知道不能再分为止。线段树可以用于维护具有结合律特性的区间查询操作。例如加法，乘法，最值。
举个例子，比如说对于序列 {1,2,3,4,5,6}\{1,2,3,4,5,6\}{1,2,3,4,5,6}，设定其左右区间分别为 1,61,61,6。那么可以绘制出线段树如下图所示：
为了方便理解我们转换成树形结构。
可见线段树通常被视为一颗完全二叉树（更准确地说是平衡二叉树）。这颗二叉树的每一个叶子节点都代表着这个序列其中一个元素的值。（因为左区间与右区间相等）
那么接下来，我们开始学习线段树的相关操作。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
建树
根据线段树的特性（即将每一个长度不为一的区间划分成左右两个区间），我们可以将一个区间对半分，然后递归对半分后的两个区间，再给它对半分，一直到区间长度为 111 为止，然后再回溯求区间和。下面我们用一个具体例子来描述这一过程。
首先我们有一个长度为 666 的序列，为 {1,20,2,6,5,4}\{1,20,2,6,5,4\}{1,20,2,6,5,4}。我们先构建出这棵线段树。
将区间 [1,6][1,6][1,6] 对半分，分为 [1,3],[4,6][1,3],[4,6][1,3],[4,6] 两个区间。
接下来来我们按照递归顺序递归左孩子，将区间 [1,3][1,3][1,3] 对半分，分为 [1,2],[3,3][1,2],[3,3][1,2],[3,3] 两个区间。
按照顺序，我们把区间 [1,2][1,2][1,2] 对半分，分为 [1,1],[2,2][1,1],[2,2][1,1],[2,2] 两个区间
此时我们发现两个区间的长度都为 111 了，那么我们就把这两个叶子节点赋值，分别为赋值为 1,201,201,20。回溯至区间 [1,2][1,2][1,2]，赋值为它的两个孩子值的和，即为 1+20=211+20=211+20=21。此时回溯到区间 [1,3][1,3][1,3]，递归右孩子 [3,3][3,3][3,3]，发现区间长度为 111，赋值为 222。回溯到区间 [1,3][1,3][1,3]，赋值为两个孩子之和，即为 21+2=2321+2=2321+2=23。
接下来我们回溯到区间 [1,6][1,6][1,6]，递归右孩子 [4,6][4,6][4,6]。对半分分为区间 [4,5],[6,6][4,5],[6,6][4,5],[6,6]
后面我就不细讲了，最终的线段树如下图所示。
那么我们就可以写出线段树的建树函数。
时间复杂度分析：
线段树可以被看作一棵完全二叉树，若序列长度为 nnn，那么线段树的节点数为 2n−12n-12n−1，故复杂度为 O(n)\mathcal{O}(n)O(n)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
区间查询
现在我们构建好了一棵线段树，那么我们该如何进行区间查询操作呢？
我们按照上述构建好的线段树为例，来查询区间 [2,4][2,4][2,4] 的和。
首先我们看区间 [1,6][1,6][1,6]
我们发现所求区间与区间 [1,6][1,6][1,6] 并不匹配[1]，所以我们向下进行寻找。我们来到区间 [1,6][1,6][1,6] 的两个孩子。
这时候我们发现这两个区间与所求区间仍然不匹配，我们就继续向下寻找
此时我们发现只有区间 [3,3][3,3][3,3] 与所求区间匹配，我们就将结果加上区间 [3,3][3,3][3,3] 的值 222。对于区间 [6,6][6,6][6,6]，我们发现他不匹配所求区间，我们直接返回 000 即可[2]。对于其他区间，我们继续向下递归。
同样的，筛去不匹配的区间，我们最终剩下了：
最后区间 [2,4][2,4][2,4] 的结果就是这三个区间的值相加。结果为 21+2+6=2921+2+6=2921+2+6=29。
由此我们可以写出线段树区间查询函数的代码，如下所示
时间复杂度分析
线段树最多有 2n+12n+12n+1 个节点，每次递归左右两边的区间，平均一下复杂度为 O(logn)O(\log n)O(logn)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
区间更新
如果根据查询函数直接写更新函数，需要下降更新这个区间中的每一个元素，复杂度高达 nlognn \log nnlogn，这个时候我们引入一个新的概念用以优化，懒标记。
懒标记 LAZYLAZYLAZY TAGTAGTAG 优化
懒标记，顾名思义就是让你偷懒的（
我们发现只有当操作时经过这一区间时才需要获取他的值，我们大可以等到需要用到这个区间的值时在进行更新。
我们将储存线段树的数组加上一个值 lazylazylazy 用于储存这个节点的懒标记。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. 这里我们定义当前区间为 [l1,r1][l_1,r_1][l1 ,r1 ]，所求区间为 [l2,r2][l_2,r_2][l2 ,r2 ]，我们说当前区间与所求区间相匹配当且仅当 l2≤l1≤r1≤r2l_2 \leq l_1 \leq r_1 \leq r_2l2 ≤l1 ≤r1 ≤r2 ↩︎
2. 我们需要根据实际需求进行返回，这里返回 000 的原因是因为一个数加上 000 仍得原数。如果我们要求区间最大值，可以返回 INT_MIN。 ↩︎
