线段树是一种比较全能的区间维护算法
将一段区间的数据保留在一维数组中，根据需要递归查询
首先规定有这样一种二叉树形结构：
左右两个子节点分别保存父节点的区间从中点分割而成的左右两个区间的价值
左右两个子节点的编号分别为父节点的编号 pos * 2 和 pos * 2 + 1
这样就可以将一段区间的价值保存在一维数组中，但需要用到结构体保存树形结构的各项数据

1
2
3
4
struct Tree{
    int l, r; // 区间的左右端点
    int val; // 区间的价值
}T[N];

建树过程如下：

1
2
3
4
5
6
7
8
9
10
11
void build(int pos, int l, int r){
    T[pos].l = l, T[pos].r = r;
    if(l == r){
        T[pos].val = a[l]; // 说明到达叶节点，等于原本该点的数值
        return ;
    }
    int mid = (l + r) >> 1;
    build(pos << 1, l, mid);
    build(pos << 1 | 1, mid + 1, r);
    T[pos].val = T[pos << 1].val + T[pos << 1 | 1].val; // 父节点的价值等于左右两个孩子的价值之和
}