题解：P3372 【模板】线段树 1

· · 题解

这里提供一种最简单的线段树实现方式。

线段树是一种类似于分治的数据结构，这道题让实现的是加减线段树，我一部分一部分的讲，一定要看完并点赞哦。

线段树最开始要建树，我们可以先将根节点的范围定义为从一到序列的长度，然后下面的节点只需要像二分一样定义中间，分成两部分即可递归建树，这里重要的是在回溯的过程中，在非叶子节点处累加他的儿子节点的值，这就是代码中的第一个和第三个函数。

然后是加操作（很显然减是加的逆运算），我们从根节点开始下传累加值和修改范围，当该节点包含在修改范围内的时候就把修改的值加给改节点的懒标记，这是线段树很重要的一个操作，一定不要忘。回溯的过程中依旧在非叶子节点处累加他的儿子节点的值。

查询操作有很多的细节，首先讲一下代码中第二个函数的作用，是将懒标记下传给子节点，这样我们就可以在查询时先下传懒标记再查询，不要忘记下传后清空懒标记（其实还有一种标记持久化线段树，但因为这个好理解就不提了）。从根节点开始下传查询范围，当该节点包含在查询范围内的时候就把该节点的值加给最终的答案即可。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
struct node {
    int l, r, sum, tag;
}tr[N << 2];
int n, m, op, x, y, k;
inline void update(int p){
    tr[p].sum = tr[p << 1].sum + tr[p << 1 | 1].sum;
}
inline void downdate(int p){
    if(!tr[p].tag) return ;
    tr[p << 1].sum += tr[p].tag * (tr[p << 1].r - tr[p << 1].l + 1);
    tr[p << 1].tag += tr[p].tag;
    tr[p << 1 | 1].sum += tr[p].tag * (tr[p << 1 | 1].r - tr[p << 1 | 1].l + 1);
    tr[p << 1 | 1].tag += tr[p].tag;
    tr[p].tag = 0;
    return ;
}
inline void build(int p, int l, int r){
    tr[p].l = l, tr[p].r = r;
    if(l == r){
        cin >> tr[p].sum;
        return ;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    update(p);
    return ;
}
inline void add(int p, int l, int r, int v){
    if(l <= tr[p].l && tr[p].r <= r){
        tr[p].sum += (tr[p].r - tr[p].l + 1) * v;
        tr[p].tag += v;
        return ;
    }
    downdate(p);
    int mid = (tr[p].l + tr[p].r) >> 1;
    if(l <= mid) add(p << 1, l, r, v);
    if(mid < r) add(p << 1 | 1, l, r, v);
    update(p);
    return ;
}
inline int query(int p, int l, int r){
    if(l <= tr[p].l && tr[p].r <= r){
        return tr[p].sum;
    }
    downdate(p);
    int ans = 0, mid = (tr[p].l + tr[p].r) >> 1;
    if(l <= mid) ans += query(p << 1, l, r);
    if(mid < r) ans += query(p << 1 | 1, l, r);
    update(p);
    return ans;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    build(1, 1, n);
    while(m--){
        cin >> op >> x >> y;
        if(op == 1){
            cin >> k;
            add(1, x, y, k);
        } else cout << query(1, x, y) << "\n";
    }
    return 0;
}

最后三个函数没看懂的一定要手画一下，这样才记得深，赛场上模板不打错（富有故事的话语）。