本篇只讲基础线段树。以下内容以求区间和线段树为例。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
前置知识：
二分、分治思想，堆式建树。
对于节点 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，这个时候我们引入一个新的概念用以优化，懒标记。
> 懒标记 LAZY TAG 优化
>
> 懒标记，顾名思义就是偷懒的（
>
> 我们发现只有当操作时经过这一区间时才需要获取他的值，我们大可以等到需要用到这个区间的值时在进行更新。
>
> 我们将储存线段树的数组加上一个值 lazylazylazy 用于储存这个节点的懒标记。只有当需要这个节点的值时，我们再将懒标记下发，并清空当前节点的懒标记。对于区间和问题，若需将区间 [l,r][l,r][l,r] 加上 kkk，下发懒标记时需要加上 (r−l+1)×k(r-l+1)\times k(r−l+1)×k。在懒标记优化后，每次搜索的时间可以优化为 O(logn)O(\log n)O(logn)。
>
> 据此，我们可以写出一个 pushdown 函数用来下传懒标记。如果当前节点懒标记不为 000 我们就下发他，否则不做任何操作，注意在下发完后把当前节点的懒标记设为 000。
在学习完懒标记优化后，我们来看区间更新代码实现过程。
1. 当区间完全不匹配时，我们直接返回。
2. 如果当前区间匹配，我们直接更新当前区间的值，并返回
3. 下发当前节点的懒标记
4. 更新左区间
5. 更新右区间
6. 将当前节点值更新为他的两个孩子的值之和。
代码易得
单点更新
这里不细讲，具体实现和区间更新函数类似。如果不想写可以在调用区间更新函数时将左右区间设为你想更新的那个点。具体代码如下。
完整代码
将上述函数封装，可得如下代码：
当然，线段树的模板需要根据实际情况进行填改或删改。
例题1：P3372
这是线段树的基础模板，将上述代码原模原样打上去即可。
例题2：P4513
（贴主也是半独立做的
题意：
现在有两种操作
1. 输出区间 [a,b][a,b][a,b] 的最大子段和
2. 将第 ppp 个值更改为 sss
思路：
本题需要我们在维护区间和线段树的情况下输出每一次查询的最大子段和。我们发现，某区间的最大子段和有如下三种情况：
1. 全部位于该区间的左孩子
2. 全部位于右孩子
3. 两边都有
所以我么可以额外开三个变量，分别维护从左边开始的最大子段和，从右边开始的最大子段和，整个区间的最大子段和。这里分别用 l,r,maxx 表示。把懒标记扔进垃圾桶，并在先前代码基础上那个修改可以得到如下代码：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
拓展——动态开点线段树
由于是拓展，这里讲的简略一点。
我们发现普通的线段树并不是所有节点都用到的，只有当经过该节点时才需要获取当前节点的值。所以我们可以等到需要这个节点在开。
因为这种实现方法，我们不能用堆式建树的方式来取左右孩子，我们会使用类似链表的方式，摒弃指针。在线段树结构体中储存当前节点的左右孩子，也就是在线段树结构体中再开两个成员变量 l,rl,rl,r。
区间更新
与普通线段树类似，只不过我们需要判断当前节点是否存在，不存在开一个点即可。代码易得：
区间查询：
一样的，判断该点是否存在即可。代码：
懒标记的下发
差不多，只不过需要提前开好左右孩子节点即可，代码：
例题：P13825
诶这不就是普通线段树模版吗，和模版 111 一模一样看我复制直接提交
诶我去怎么只有 50pts50pts50pts，不是这个 nnn 的上界怎么有 10910^9109 啊，吓哭了
这个时候我们把动态开点直接用上即可。由于原数列是等差数列，我们可以用等差数列公式进行求解，不需要建树代码。代码如下：
完结撒花
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
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。 ↩︎
