用线段树十分简单

C++ 代码

//维护一个辣鸡线段树，支持单点查询和区间修改（加法） 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
long long a[100010],tag[400010];
struct node{
    int l,r;
    long long val;//val维护区间和 
}tree[400010];
void build(int p,int l,int r)//建树 
{
    tree[p].l=l;
    tree[p].r=r;
    if(l==r)
    {
        tree[p].val=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    tree[p].val=tree[p*2].val+tree[p*2+1].val;
}
void pushdown(int p)//下传懒惰标记 
{
    int mid=(tree[p].l+tree[p].r)>>1;
    tree[p*2].val+=(mid-tree[p].l+1)*tag[p];
    tree[p*2+1].val+=(tree[p].r-mid)*tag[p];
    tag[p*2]+=tag[p];
    tag[p*2+1]+=tag[p];
    tag[p]=0;
    return ;
}
void update(int p,int l,int r,int d)//区间修改，[l,r]加一个数 
{
    if(l<=tree[p].l&&tree[p].r<=r)
    {
        tree[p].val+=(tree[p].r-tree[p].l+1)*d;
        tag[p]+=d;
        return ;
    }
    int mid=(tree[p].l+tree[p].r)>>1;
    if(tag[p])
    pushdown(p);
    if(l<=mid)
    update(p*2,l,r,d);
    if(r>mid)
    update(p*2+1,l,r,d);
    tree[p].val=tree[p*2].val+tree[p*2+1].val; 
}
long long getsum(int p,int l,int r)
{
    if(l<=tree[p].l&&tree[p].r<=r)
    {
        return tree[p].val;
    }
    int mid=(tree[p].l+tree[p].r)>>1;
    if(tag[p])
    pushdown(p);
    long long ans=0;
    if(l<=mid)
    ans+=getsum(p*2,l,r);
    if(r>mid)
    ans+=getsum(p*2+1,l,r);
    return ans;
}
long long getval(int p,int x)//单点查询 
{
    if(tree[p].l==x&&tree[p].r==x)
    {
        return tree[p].val;
    }
    int mid=(tree[p].l+tree[p].r)>>1;
    if(tag[p])
    pushdown(p);
    if(x<=mid)
    return getval(p*2,x);
    else return getval(p*2+1,x);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        char op;
        scanf(" %c",&op);
        if(op=='Q')
        {
            long long res;
            int x,y;
            scanf("%d%d",&x,&y);
            res=getsum(1,x,y);
            printf("%lld\n",res);
        }
        else 
        {
            int x,y,d;
            scanf("%d%d%d",&x,&y,&d);
            update(1,x,y,d);
        }
    }
    return 0;
}