萌新刚学 OI 一毫秒，树剖板子求调

#include<bits/stdc++.h>
using namespace std;

#define lid (id<<1)//左儿子 
#define rid (id<<1|1)//右儿子
#define ll long long

ll n,m,k,x,y,l,a[1000005];

struct tree{
    ll r,l,lazy;//l左端点 r右端点 lazy未下放标记
    ll sum;//r到l的总和  
}t[4000005];

void build(ll id,ll l,ll r)
{
    t[id].l=l;
    t[id].r=r;  //记录左右端点 
    if(l==r)   //到叶子节点时 
    {
        t[id].sum=a[l];
        return;
    }
    ll mid=(l+r)>>1;
    build(lid,l,mid);//建左儿子 
    build(rid,mid+1,r);//建右儿子
    t[id].sum=t[lid].sum+t[rid].sum;//update 
}

void pushdown(ll id) //下放标记 
{
    if(t[id].lazy&&t[id].l!=t[id].r){
        t[lid].lazy+=t[id].lazy;
        t[rid].lazy+=t[id].lazy;
        t[lid].sum+=t[id].lazy*(t[lid].r-t[lid].l+1); 
        t[rid].sum+=t[id].lazy*(t[rid].r-t[rid].l+1);
        t[id].lazy=0;
    } 
    return ; 
}

void change(ll id,ll val,ll l,ll r){//区间修改 
    pushdown(id);
    if(t[id].r==r&&t[id].l==l)//找到对应区间 
    {

        t[id].lazy+=val;
        t[id].sum+=val*(t[id].r-t[id].l+1);
        return ;
    }
    ll mid=(r+l)>>1;
    if(r<=mid)//都在左边 
    change(lid,val,l,r);
    else if(l>mid)//都在右边 
    change(rid,val,l,r);
    else {//两边都有 
        change(lid,val,l,mid);
        change(rid,val,mid+1,r);
    }
    t[id].sum=t[lid].sum+t[rid].sum;
}

ll query(ll id,ll l,ll r)
{
    pushdown(id);
    if(t[id].l==l&&t[id].r==r)
    {
        return t[id].sum;
    }
    ll mid=(t[id].r+t[id].l)>>1;
    if(r<=mid)//都在左边 
    return query(lid,l,r);
    else if(l>mid)//都在右边 
    return query(rid,l,r);
    else {//两边都有 
        return query(lid,l,mid)+query(rid,mid+1,r);
    }
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld ",&a[i]);
    }
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        cin>>l;
        if(l==1)
        {
            scanf("%lld %lld %lld",&x,&y,&k);
            change(1,k,x,y);
        }
        else
        {
            scanf("%lld %lld",&x,&y);
            cout<<query(1,x,y)<<endl;
        }
    }
    return 0;
    }