一、什么是线段树？
-
线段树是怎样的树形结构?
线段树是一种二叉搜索树，每个结点都存储了一个区间，也可以理解成一个线段，你要从这些线段上进行搜索操作得到你想要的答案。
-
线段树能够解决什么样的问题？
线段树的适用范围很广，可以在线维护修改以及查询区间上的最值，求和。
需要注意的是，线段树只可以维护满足结合律的信息。
对于线段树来说，每次更新以及查询的时间复杂度为 \(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]\)，再返回。
否则就递归构造左儿子结点和递归构造右儿子结点,最后更新父节点。
void PushUp(int x) {
sum[x] = sum[x << 1] + sum[x << 1 | 1];
}
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);
}