9
本篇只讲简单的线段树，仅建树、求区间最大/最小值。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
其他大佬的模版都比较长，不易理解，读起来也比较费劲，今天分享一款比较简短的蒟蒻式模版
废话不多说，有点二叉树基础的狗友都知道：
（仅节点编码）
那么我们的模版也会根据这个小知识点进行扩张
1.建树
这就是建树，其中思路与归并排序类似，递归从根节点开始分别向其左子树与其右子树遍历建树
tree[i]tree[i]tree[i]表示节点编号为iii的线段树节点的存值
橙色为原数组区间，红色为节点存值，黑色为节点编号。
本图以最大值建树为例
即节点存的值是其左子树与右子树中的最大值
举个栗子：节点1存的就是区间[1,2][1,2][1,2]与区间[3,4][3,4][3,4]合并所得的最大值
模拟过程
1.递归区间[1,4][1,4][1,4]
条件不成立，递归结果max([1,2],[3,4])max([1,2],[3,4])max([1,2],[3,4])
2.递归区间[1,2][1,2][1,2]
条件不成立，递归结果max([1,1],[2,2])max([1,1],[2,2])max([1,1],[2,2])
3.两个子区间条件成立，回溯至2
4.结果为[2,2][2,2][2,2]，回溯至1
5.递归区间[3,4][3,4][3,4]
条件不成立，递归结果max([3,3],[4,4])max([3,3],[4,4])max([3,3],[4,4])
6.两个子区间条件成立，回溯至5
7.结果为[4,4][4,4][4,4]，回溯至1
8.结果为[1,2][1,2][1,2]，递归结束，建树成功
好了，咱们已经获得了一棵优美的维护最大值的线段树了，接下来就是查询了
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2.查询
有帮助，赞一个