题目描述

一道很简单的线段树模板题

话不多说，直接上代码，有问题可以留言

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,m;
int a[N];
struct node{
    int l,r;
    long long sum,add;//注意要用long long

    //sum:如果考虑当前节点及其子节点上的所有标记，当前区间和是多少
    //add:给当前区间的所有儿子，加上add

}tr[N*4];//线段树的区间需要开4倍的N

void pushup(int u){//用左右子节点的信息，更新父节点的信息
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}

void pushdown(int u){
    auto &root=tr[u],&left=tr[u<<1],&right=tr[u<<1|1];
    if(root.add){//判断当前节点上有没有标记
        left.add+=root.add,left.sum+=(long long)(left.r-left.l+1)*root.add;//当前区间*add
        right.add+=root.add,right.sum+=(long long)(right.r-right.l+1)*root.add;

        root.add=0;//注意 根节点要清空
    }   
}

void build(int u,int l,int r){//建树
    tr[u].l=l;
    tr[u].r=r;
    if(l==r){
        tr[u].sum=a[l];
        return ;
    }

    int mid=(l+r)>>1;
    build(u<<1,l,mid),build(u<<1|1,mid+1,r);//递归，初始化左右节点
    pushup(u);
}

void modify(int u,int l,int r,int d){//修改操作
    if(tr[u].l>=l&&tr[u].r<=r){
        tr[u].sum+=(long long)(tr[u].r-tr[u].l+1)*d;
        tr[u].add+=d;//更新add
    }
    else{//注意要分裂
        pushdown(u);
        int mid=(tr[u].l+tr[u].r)>>1;
        if(l<=mid) modify(u<<1,l,r,d);//如果跟左边有交集
        if(r>mid) modify(u<<1|1,l,r,d);//如果跟右边有交集
        pushup(u);
    } 
}

long long query(int u,int l,int r){//查询
    if(l<=tr[u].l&&r>=tr[u].r) return tr[u].sum;

    pushdown(u);
    int mid=(tr[u].l+tr[u].r)>>1;
    long long sum=0;//sum表示总和
    if(l<=mid) sum=query(u<<1,l,r);
    if(r>mid) sum+=query(u<<1|1,l,r);
    return sum;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    while(m--){
        string op;
        cin>>op;
        if(op=="C"){
            int x,y,v;
            cin>>x>>y>>v;
            modify(1,x,y,v);
        }
        else{
            int x,y;
            cin>>x>>y;
            cout<<query(1,x,y)<<endl;

        }
    }
    return 0;
}

当然这道题用树状数组也能做
这里就不过多讲了