前言
线段树用来解决区间问题。
包括并不限于：\(RMQ\)，整数区间求和等问题。
通常的：可用来求下标连续区间二元运算后结果（比如群\(（\mathbb{G}，*）\)） 。
而线段树的题一般用来选择合适的集合（比如矩阵，线性基等） 。
并在合适的时间复杂度内维护二元运算 \(*\) 。
同时可以理解为分治的一种。
维护二元运算符的过程可以理解为分治中答案合并的过程。
同时因为群满足结合律，所以可以用懒标记表示这个点被修改过。
对于有多种二元运算的需要考虑多种不同运算之间的影响。
免责声明：（没学过抽象代数，可能理解比较浅显）
定义
每个节点维护一个区间的信息。
把区间分成两个区间且满足左右区间相差不超过一。
易得：线段树的深度不会超过\(logn\)级别（保证时间复杂度正确）。
算法流程
建一颗线段树：
- 开一个新节点，并清空。
- 递归边界：到达叶子节点。
- 建左右子树。
查询 \((\) 修改 \()\)：
- 递归边界：
当前区间不合法，返回单位元。
当前区间完全在查询区间内返回区间维护值 \((\) 更新 \()\) 。
- 下传。
- 修改左右子树。
- 上传。
[ZJOI2017] 树状数组
[HEOI2016/TJOI2016] 排序