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

__SSY__ · 2025-12-15 21:25:59 · 题解

题目传送门

题目大意：

题目描述很清晰，不过多赘述。

思路：

很明显的线段树板子，维护一个线段树即可。
因为题目较为模板，所以简单讲解一下线段树。
前面的神犇已经把线段树讲的差不多了，所以蒟蒻斗胆讲一讲代码。

1.建树：

通过递归，将数列二分，直到叶子节点为单独一个数，直接存区间和。

void build(int i,int l,int r){
    t[i].l=l;//标记每个叶子节点的范围
    t[i].r=r;
    t[i].lazy=0;//初始化懒标记，下面会用到
    if(l==r){
        t[i].sum+=a[l];//当只有叶子节点只有一个数，可以直接求出区间的和，就是当前数的值
        return;
    }
    int mid=(l+r)>>1;//本层不能直接求解，向下二分让儿子求解，类似于归并中的归
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    pushup(i);//向上传递，类似于归并中的并，后面会讲
}

2.向上传递：

通过左右儿子的值更新父亲，类似于归并中的并。

void pushup(int i){
    t[i].sum=t[i<<1].sum+t[i<<1|1].sum;//父亲的值就相当于左右儿子的和
}

3.懒标记下传：

具体为什么需要下传后面会讲。

void pushdown(int i){
    t[i<<1].sum+=(t[i<<1].r-t[i<<1].l+1)*t[i].lazy;//左儿子的更新
    t[i<<1|1].sum+=(t[i<<1|1].r-t[i<<1|1].l+1)*t[i].lazy;//右儿子的更新
    t[i<<1].lazy+=t[i].lazy;//注意：虽然已经更新了儿子，但儿子的儿子、儿子的儿子的儿子……还没更新，所以懒标记还需要传给儿子，用来继续下传
    t[i<<1|1].lazy+=t[i].lazy;
    t[i].lazy=0;//下传完成，清空懒标记
}

4.修改：

void change(int i,int l,int r,int x){
    if(t[i].l>r||t[i].r<l)//如果当前区间完全不被所求区间包含，直接返回（可以直接解决）
        return;
    if(t[i].l>=l&&t[i].r<=r){//如果当前区间完全被所求区间包含（可以直接解决）
        t[i].sum+=(t[i].r-t[i].l+1)*x;//直接修改
        t[i].lazy+=x;//懒标记增加 --> 这里不理解的看其他神犇的思路讲解，这个蒟蒻只能讲代码
        return;
    }
    pushdown(i);//这里我们会发现我们的更新只更新了完全被覆盖的父亲，儿子只是表面更新，并没有更新实际值，所以我们需要下传懒标记更新儿子
    change(i<<1,l,r,x);//本层无法解决，让儿子解决
    change(i<<1|1,l,r,x);
    pushup(i);//向上传递
}

5.查询区间和：

没什么可说的，直接放代码。

int query(int i,int l,int r){
    if(t[i].l>r||t[i].r<l)//完全不包含（直接解决）
        return 0;
    if(t[i].l>=l&&t[i].r<=r)//完全包含（直接解决）
        return t[i].sum;
    pushdown(i);//在统计区间和时，可能还有积累的懒标记没有下传，这会影响结果，所以需要再次下传懒标记
    return query(i<<1,l,r)+query(i<<1|1,l,r);//无法解决，给儿子解决
}

以上就是线段树的模板以及讲解，下面是完整的本题代码。

代码：

#include <bits/stdc++.h>
#define int long long//不是好习惯，不要学！！！
using namespace std;
const int N=1e5+10;
struct Node{
    int l,r,lazy,sum;
}t[N<<2];
int a[N];
int n,m;
void pushup(int i){
    t[i].sum=t[i<<1].sum+t[i<<1|1].sum;
}
void pushdown(int i){
    t[i<<1].sum+=(t[i<<1].r-t[i<<1].l+1)*t[i].lazy;
    t[i<<1|1].sum+=(t[i<<1|1].r-t[i<<1|1].l+1)*t[i].lazy;
    t[i<<1].lazy+=t[i].lazy;
    t[i<<1|1].lazy+=t[i].lazy;
    t[i].lazy=0;
}
void build(int i,int l,int r){
    t[i].l=l;
    t[i].r=r;
    t[i].lazy=0;
    if(l==r){
        t[i].sum+=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    pushup(i);
}
void change(int i,int l,int r,int x){
    if(t[i].l>r||t[i].r<l)
        return;
    if(t[i].l>=l&&t[i].r<=r){
        t[i].sum+=(t[i].r-t[i].l+1)*x;
        t[i].lazy+=x;
        return;
    }
    pushdown(i);
    change(i<<1,l,r,x);
    change(i<<1|1,l,r,x);
    pushup(i);
}
int query(int i,int l,int r){
    if(t[i].l>r||t[i].r<l)
        return 0;
    if(t[i].l>=l&&t[i].r<=r)
        return t[i].sum;
    pushdown(i);
    return query(i<<1,l,r)+query(i<<1|1,l,r);
}
main(){//不是好习惯，不要学！！！
    ios::sync_with_stdio(0);//好习惯，可以学
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int op,x,y,k;
        cin>>op>>x>>y;
        if(op==1){
            cin>>k;
            change(1,x,y,k);
        }
        else
            cout<<query(1,x,y)<<"\n";
    }
    return 0;
}

AC 记录