一、什么是线段树？
-
线段树是怎样的树形结构?
线段树是一种二叉搜索树，每个结点都存储了一个区间，也可以理解成一个线段，你要从这些线段上进行搜索操作得到你想要的答案。
-
线段树能够解决什么样的问题？
线段树的适用范围很广，可以在线维护修改以及查询区间上的最值，求和。
需要注意的是，线段树只可以维护满足结合律的信息。
对于线段树来说，每次更新以及查询的时间复杂度为 \(O(\log n)\)。
-
线段树和其他 \(\texttt{RMQ}\) 算法的区别
常用的解决 \(\texttt{RMQ}\) 问题有 \(\texttt{ST}\) 表，二者预处理时间都是 \(O(n\log n)\)。
但二者的区别在于线段树支持在线更新值，而 \(\texttt{ST}\) 表不支持在线操作。
二、线段树的原理
线段树之所以称为“线段”树，是因为它的节点维护的信息是一个线段（即一个区间）的信息，而一个节点的两个儿子维护的信息是将当前节点维护线段（区间）分成两个线段，分别维护两个分成的线段（即子区间）的信息。
而线段树的精髓在于：根据结合律，通过儿子节点（子区间）的信息合并得到更大区间的信息。
二、线段树的基本操作
1. 建树
建树包括三个要点：结点存什么，结点下标是什么，如何建树。
上图是关于 \(a[1\cdots6] = \{1,8,6,4,3,5\}\) 的区间最大值线段树，其中红色数字代表区间，蓝色数字代表当前区间最值。
- 节点存什么
可以发现，每个叶子结点的值就是数组的值，每个非叶子结点的度都为二，且左右两个孩子分别存储父亲一半的区间。每个父亲的存储的值也就是两个孩子存储的值的最大值。
- 结点下标是什么
接着，我们采用完全二叉树的存储方法。即对于一个父节点 \(i\) 来说，它的左右儿子分别为 \(2i,2i+1\)。
- 如何建树
故此，在建树的时候，空间要开到 \(4n\) 以防止 RE。
建树时每次递归就要先判断 \(l\) 是否等于 \(r\),等于就说明是叶子节点,也就是区间是 \([l,l]\),直接赋值成 \(a[l]\)，再返回。
否则就递归构造左儿子结点和递归构造右儿子结点,最后更新父节点。
inline void PushUp(int x) {
sum[x] = sum[x << 1] + sum[x << 1 | 1];
}//由于结合律，所以根据两儿子的信息可以合并成父亲的信息
inline void Build(int l, int r, int x) {
if(l == r) {
sum[x] = a[l];
return ;
}
int mid = l + r >> 1;
Build(l, mid, x << 1);
Build(mid + 1, r, x << 1 | 1);
PushUp(x);
}
（注意，示例代码均为线段树 1 代码）
2、区间查询
我们继续观察这棵线段树。
现在我要查询 \([2,5]\) 区间的最值，如何处理呢？
显然，此区间无法直接通过某一个节点的值直接求出；那么我们来看看有哪些区间被此区间包含。
共有 \(5\) 个区间（黄色部分），而且我们可以发现 \([4,5]\) 这个区间已经包含了两个子树的信息(\([4,4],[5,5]\))，所以我们需要查询的区间只有三个，分别是 \([2,2],[3,3],[4,5]\)。
我们还是从根节点开始往下递归，如果当前结点是被要查询的区间包含了的，则返回这个结点的信息，这样从根节点往下递归，时间复杂度也是 \(O(\log n)\)。
inline int Query(int L, int R, int l, int r, int x) {
if(L <= l && r <= R) return sum[x];
int mid = l + r >> 1;
int ans = 0;
if(L <= mid) ans += Query(L, R, l, mid, x << 1);
if(R > mid) ans += Query(L, R, mid + 1, r, x << 1 | 1);
return ans;
}