Part0：前言

如果你在考提高组前一天还在问这个问题，那么你会与一等奖失之交臂；如果你还在冲击普及组一等奖，那么这篇博客会浪费你人生中宝贵的5~20分钟。

Part1：概念引入+建树（以区间求和为例）

Part1.1：概念引入

线段树，顾名思义，用线性的方式保存一颗二叉树。

举个例子：

有一串数1 2 3 4 5 6 7 8 9

那么构造出的线段树就为：

                     1(123456789)
          2(1234)                    3(56789)
   4(12)       5(34)          6(56)           7(789)
8(1) 9(2)     10(3) 11(4)   12(5) 13(6)      14(7) 15(89)
                                                  16(8) 17(9)

其中括号内的数表示当前这个下标维护的范围。

Part1.2：建树

用递归的方法建树。void build(int p,int l,int r)

其中p表示下标，l r表示区间的范围。

如果 $l=r$ ，说明此时为叶子节点，直接赋值。

否则将区间分为两个，分别建树，下标为*2和*2+1。

最后维护各节点的信息，为它的两个子节点的和。

void build(int p,int l,int r){
    if(l==r){tree[p]=a[l];return ;}
    int mid=(l+r)>>1;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    push_up(p);//维护信息
}

Part2：区间查询+修改（以区间求和为例）

Part2.1：区间查询

递归法查询。

如果查询区间在当前区间中，返回线段树数组中当前下标所对应的值。

不然将查询分成两部分。

如果有一部分在左区间，就将左区间的查询结果加上。右区间同理。

最终返回左区间和右区间的查询结果之和即可。

int search(int i,int l,int r){
    if(tree[i].l>=l && tree[i].r<=r)//如果这个区间被完全包括在目标区间里面，直接返回这个区间的值
        return tree[i].sum;
    if(tree[i].r<l || tree[i].l>r)  return 0;//如果这个区间和目标区间毫不相干，返回0
    int s=0;
    if(tree[i*2].r>=l)  s+=search(i*2,l,r);//如果这个区间的左儿子和目标区间又交集，那么搜索左儿子
    if(tree[i*2+1].l<=r)  s+=search(i*2+1,l,r);//如果这个区间的右儿子和目标区间又交集，那么搜索右儿子
    return s;
}

Part2.2：区间修改

和区间查询类似。

void add(int i,int dis,int k){
    if(tree[i].l==tree[i].r){//如果是叶子节点，那么说明找到了
        tree[i].sum+=k;
        return ;
    }
    if(dis<=tree[i*2].r)  add(i*2,dis,k);//在哪往哪跑
    else  add(i*2+1,dis,k);
    tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;//返回更新
    return ;
}

线段树，从入门到退坑