线段树（Segment Tree）
线段树是主要用于维护区间信息（要求满足结合律）的数据结构。与树状数组相比，线段树可以在\(O(\log N)\) 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。
引入：
问题1：
有 \(n(n \leq 50000)\) 个数， \(m(m\leq50000)\) 次询问，每次询问区间 \(l_i\) 到 \(r_i\) 的数的和，要求输出每一次询问的结果。
分析：
这个问题很明显要用前缀和来维护区间和
问题2：RMQ(Range Minimum/Maximum Query)
有 \(n(n \leq 50000)\) 个数， \(m(m\leq50000)\) 次询问，每次询问区间 \(l_i\) 到 \(r_i\) 的数的最大值。
问题3：带修改的区间和查询
有 \(n(n \leq 50000)\) 个数， \(m(m\leq50000)\) 次操作，1.询问区间\(l_i\)到\(r_i\)的数的和2.将第\(i\)个数的值修改为\(x\),要求输出每一次询问的结果。
分析：
问题2和问题3就不好用前缀和来维护了，这是就需要改用线段树来维护。
线段树的几点性质
- 线段树是平衡二叉树，最大深度\(logN\)(N为线段树所表示区间的长度)
- 树中的每一个节点代表对应一个区间（叶子节点是一个点）
- 每个节点（所代表的区间）完全包含它的所有子孙节点
- 对于任意两个节点（所代表的区间）：要么完全包含，要么互不相交
- 在进行区间操作和统计时把区间等价转换成若干个子区间（\(logN\)个)的相同操作
- 任意的线段[a,b]在线段树的查询或查找过程中把这个线段最多分成%log(b-a)%份（显然每一层最多两个区间）
- 所以，线段树除建树外的操作都是$logN%级别的复杂度。
线段树的运用
- 线段树的每个节点上往往都增加了一些其他的域，在这些域中保存了某种动态维护的信息，视不同情况而定。这些域使得线段树具有极大的灵活性，可以适应不同的需求。
线段树的建立
线段树是一颗平衡二叉树。根节点代表整个区间的和，越往下区间越小。注意，线段树的每个节点都对应一条线段（区间），但并不保证所有的线段（区间）都是线段树的节点。
例如：有一个数组[1,2,3,4,5],那么它对应的线段树如下：
每个节点 \(p\) 的左右子节点的编号分别为 \(2p\) 和 \(2p+1\) ，假如节点 \(p\) 储存区间[a,b]的和，设mid=[(l+r)/2],那么两个子节点分别储存[l,mid]和[mid+1, r]的和。可以发现左节点对应的区间长度，与右节点相同或者比之恰好多\(1\).
如何用数组建立一颗线段树？ 考虑用递归实现。