本来是想先写树状数组的，但想到要在树状数组里面用到这篇文章，就先写这个了。
线段树的思想
线段树是在用一颗树存一个数组中的所有数以及他们所有的2的次方数长度的区间，具体样子如下：
[1~8]
/ \
/ \
[1~4] [5~8]
/ \ / \
[1~2] [3~4] [5~6] [7~8]
/ \ / \ / \ / \
[1] [2] [3] [4] [5] [6][7] [8]
而其中，每个节点可以维护数列的区间最大值、最小值和区间和。
线段树分层讲解
第一步：建树
树虽然是一个二维的图形，但是肯定要存到一个数组中去对不对？
所以我们肯定需要给每个点表上一个唯一的编号
建设一棵子树，它的根的编号是i，则我们设它的左儿子的编号是2*i+1，它的右儿子的编号是2*i+2
于是我们就要递归建树，每次把区间分成两半，分开递归，然后遇到叶子结点就直接把输入数组的值赋值到叶子结点中，代码很简单：
//这是维护区间和的代码
void build(int id,int st,int en){ //建树
if (st==en){ //遇到了叶子结点
tree[id]=a[st]; //把输入的值赋值给叶子
return ;
}