线段树

线段树是一种二叉搜索树，首先它满足二叉树，每个结点最多有两个子树，其次，我们知道线段树的每个结点都存储了一段区间，也可以理解为线段，搜索就是在这些线段上进行搜索操作找到我们想要的答案。

现在我们来看这张图，我们会发现，区间 [ 1 , 13 ] [1,13] [1,13]的和=区间 [ 1 , 7 ] [1,7] [1,7]的和+区间 [ 8 , 13 ] [8,13] [8,13]的和。以此类推，我们可以总结出一个性质：结点 i i i的权值=它的左儿子的权值+它的右儿子权值，即得到公式 t r e e [ i ] = t r e e [ i × 2 ] + t r e e [ i × 2 + 1 ] tree[i]=tree[itimes2]+tree[itimes2+1] tree[i]=tree[i×2]+tree[i×2+1]。建树

struct Tree{//存储val维护结点的值，l，r维护区间范围，add涉及一个懒标记
    int l, r;
    ll val, add;
}seg[N << 2 + 2];

void BuildTree(int rt, int l, int r){//建树
    seg[rt].l = l;
    seg[rt].r = r;
    if(l == r){
        cin >> seg[rt].val;
        return;
    }
    int mid = l + (r - l) >> 1;
    BuildTree(rt << 1, l, mid);
    BuildTree(rt << 1 | 1, mid + 1, r);
    seg[rt].val = seg[rt << 1].val + seg[rt << 1 | 1].val;
}

懒标记：精髓就是打标记和下传操作，由于我们要做的操作时区间加上一个数，所以我们就在区间进行修改时给该区间打上一个懒标记，这样我们就不用在修改它的左右儿子所维护的区间，等到要使用该结点索要维护的值时，再将懒标记下传即可，这样我们就可以节省很多时间，对于每次区间修改和查询，将懒标记下传，就可以节省很多时间。

void spread(int rt){//懒标记
    if(seg[rt].add){//如果懒标记不为0，就将其传下去，并维护左右儿子的值
        seg[rt << 1].val = seg[rt].add * (seg[rt >> 1].r - seg[rt >> 1].l + 1);
        seg[rt << 1 | 1].val = seg[rt].add * (seg[rt << 1 | 1].r - seg[rt << 1 | 1].l + 1);
        seg[rt << 1].add += seg[rt].add;
        seg[rt << 1 | 1].add += seg[rt].add;
        seg[rt].add = 0;//传下去之后将该结点的懒标记清零
    }
}

区间修改

考虑到，我们是将一个区间加上一个数，我们可以从根结点开始不断向下查找，当我们要修改的区间覆盖当前结点覆盖时，我们就把这个区间进行修改并打上懒标记，否则就将懒标记下传，继续进行查找。

void chang(int rt, int l, int r, int k){//修改
    if(seg[rt].l >= l && seg[rt].r <= r){//如果区间被覆盖，就对其进行修改
        seg[rt].val += k * (seg[rt].r - seg[rt].l + 1);
        seg[rt].add += k;//打上懒标记
        return;
    }
    spread(rt);//如果没有被覆盖，既需要哦继续向下查找，考虑儿子所需要维护的区间可能因为上面的懒标记而没有修改
    int mid = (seg[rt].r + seg[rt].l) >> 1;
    if(l <= mid) chang(rt << 1, l, r, k);//如果区间覆盖左儿子，及修改左儿子
    if(r > mid) chang(rt << 1 | 1, l, r, k);//右儿子同理
    seg[rt].val = seg[rt << 1].val + seg[rt << 1 | 1].val;//最终维护的值=做儿子的值+右儿子的值
}

区间查询

查询和修改的操作几乎一样，依旧是从根结点开始查找，当我们要查找的区间被覆盖时，就返回维护的值，否则就将懒标记下传，继续进行查找。

int ask(int rt, int l, int r){//查找
    if(seg[rt].l >= l && seg[rt].r <= r)return seg[rt].val;//如果期间被覆盖，就直接返回其值
    spread(rt);//下传懒标记，并查询左右儿子
    int mid = seg[rt].r + seg[rt].l >> 1;
    ll res = 0;
    if(l <= mid) res += ask(rt << 1, l, r);
    if(r > mid) res += ask(rt << 1 | 1, l, r);//累加答案，返回左右儿子的和
    return res;
}