线段树（$\tt Segment\ Tree$）

最好用的数据结构，没有之一。

可以以 $\log_2{n}$ 的复杂度处理区间和，区间最值，单点修改，区间修改等操作，也是非常的好用，有一些题目你可以直接上一个线段树，然后以比正解略劣的解法过掉。

建树

从上图，我们可以看出，其实就是一个二叉搜索树。
叶子节点都是原序列，父亲会综合儿子的信息。

这时当一个数组长度是 $2$ 的不知多少次方的时候。他是一个完全树。如果他不是 $2$ 的整数次方，那么其实就是比那个完全树再多上一层，树的深度是 $\log N$ 的。我们可以使用父子两倍的方法建树（设父亲是 $p$ ，则左儿子是 $p2$ ，右儿子是 $p2+1$）。

1
2
3
4
5
6
7
8
9
10
11
void Bulid(int p, int l, int r, int *val){
    node[p].l=l, node[p].r=r; //区间赋值
    if(l==r){ //确定了一个叶子
        node[p].mi=val[l];//赋值
        return ;
    }
    int mid=(node[p].l+node[p].r)/2;//寻找中点
    Bulid(p*2, l, mid, val);//继续建树
    Bulid(p*2+1, mid+1, r, val);
    node[p].mi=min(node[p*2].mi, node[p*2+1].mi);//统计结果
}

单点修改

单点更新时，我们只需递归搜索那一个点的位置，之后跟新那个点以及他的祖先就可以了。

1
2
3
4
5
6
7
8
9
10
void Addvalue(int p, int x, int v){//参数：当前在那个点，要找到数在那个点，要加多少/要改成多少
    if(node[p].l==x&&node[p].r==x){//刚好是要找的点
        node[p].mi+=v;//加值（如果是该值写成 node[p].mi=v;）
        return ;
    }
    int mid=(node[p].l+node[p].r)/2;//取中点二分
    if(x<=mid) Addvalue(p*2, x, v);//在左子树上
    else Addvalue(p*2+1, x, v);//在右子树上
    node[p].mi=min(node[p*2].mi, node[p*2+1].mi);//更新路径上的点
}

区间查询

区间查询的时候，我们发现