2020-08-06线段树

https://www.luogu.com.cn/problem/P3372 线段树区间求和和区间修改模板

#include<bits/stdc++.h>
#define MAXN 1000001
#define ll long long
using namespace std;
unsigned ll num[MAXN],sum[MAXN<<2],lazy[MAXN<<2];
ll pushup(ll t)
{
    sum[t]=sum[2*t]+sum[2*t+1];
}
ll pushlazy(ll t,ll lz,ll len)
{
    sum[t]+=lz*len;
    lazy[t]+=lz;
}
ll pushdown(ll l,ll r,ll t)
{
    if(lazy[t]!=0)
    {
        ll mid=(l+r)/2;
        pushlazy(2*t,lazy[t],mid-l+1);
        pushlazy(2*t+1,lazy[t],r-mid);
        lazy[t]=0;
    }
}
ll build(ll l,ll r,ll t)
{
    lazy[t]=0;
    if(l==r)
    {
        sum[t]=num[l];
        return 0;
    }
    ll mid=(l+r)/2;
    build(l,mid,t*2);
    build(mid+1,r,2*t+1);
    pushup(t);
}
ll add(ll x,ll l,ll r,ll L,ll R,ll t)
{
    if(l>=L&&r<=R)
    {
        lazy[t]+=x;
        sum[t]+=(r-l+1)*x;
        return 0;
    }
    pushdown(l,r,t);
    ll mid=(l+r)/2;
    if(L<=mid)
        add(x,l,mid,L,R,2*t);
    if(R>mid)
        add(x,mid+1,r,L,R,2*t+1);
    pushup(t);
}
ll querysum(ll l,ll r,ll L,ll R,ll t)
{
    if(l>=L&&r<=R)
        return sum[t];
    pushdown(l,r,t);
    ll mid=(l+r)/2;
    ll ans=0;
    if(L<=mid)
        ans+=querysum(l,mid,L,R,2*t);
    if(R>mid)
        ans+=querysum(mid+1,r,L,R,2*t+1);
    return ans;
}
int main()
{
    ll n,m,a,b,c,d;
    scanf("%lld",&n);
    scanf("%lld",&m);
    for(ll i=1;i<=n;i++)
        scanf("%lld",&num[i]);
    build(1,n,1);
    for(ll i=1;i<=m;i++)
    {
        scanf("%lld",&a);
        if(a==1)
        {
            scanf("%lld%lld%lld",&b,&c,&d);
            add(d,1,n,b,c,1);
        }
        else if(a==2)
        {
            scanf("%lld%lld",&b,&c);
            printf("%lld\n",querysum(1,n,b,c,1));
        }
    }
}