萌新线段树求调，悬一关

TLE on #8,9,10

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=100005;
struct node{
    long long val;
    int lc,rc,l,r;
    bool cover;
}tr[N*3];
int n,m,id=1;
ll sum[N];

void build(int l,int r)
{
    //cout<<l<<' '<<r<<endl;
    int x=id;
    tr[id].l=l,tr[id].r=r,tr[id].val=0,tr[id].cover=1;
    if(l!=r)
    {
        int mid=(l+r)/2;
        tr[x].lc=++id;
        build(l,mid);
        tr[x].rc=++id;
        build(mid+1,r);
    }
    return ;
}

void update(int pos,int x,int y,ll val)
{
    if(tr[pos].cover)
    {
        if(tr[pos].l==x and tr[pos].r==y)
        {
            tr[pos].val+=val;
            return ;
        }
        tr[pos].cover=0;
        tr[ tr[pos].lc ].cover=tr[ tr[pos].rc ].cover=1;
        tr[ tr[pos].lc ].val=tr[pos].val;
        tr[ tr[pos].rc ].val=tr[pos].val;
    }
    int mid=(tr[pos].l+tr[pos].r)/2;
    if(y<=mid) update(tr[pos].lc,x,y,val);
    else if(x>mid) update(tr[pos].rc,x,y,val);
    else
    {
        update(tr[pos].lc,x,mid,val);
        update(tr[pos].rc,mid+1,y,val);
    }
    return ;
}

ll query(int pos,int x,int y)
{
    //cout<<pos<<' '<<x<<' '<<y<<endl;
    if(tr[pos].cover==1)
        return tr[pos].val*(y-x+1);
    int mid=(tr[pos].l+tr[pos].r)/2;
    if(y<=mid) return query(tr[pos].lc,x,y);
    if(x>mid) return query(tr[pos].rc,x,y);
    return query(tr[pos].lc,x,mid)+query(tr[pos].rc,mid+1,y);
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        ll x;
        scanf("%lld",&x);
        sum[i]=sum[i-1]+x;
    }
    build(1,n);
    while(m--)
    {
        int opt,x,y;
        ll k;
        scanf("%d",&opt);
        if(opt==1)
        {
            scanf("%d%d%lld",&x,&y,&k);
            update(1,x,y,k);
        }
        else
        {
            scanf("%d%d",&x,&y);
            printf("%lld\n",query(1,x,y)+sum[y]-sum[x-1]);
        }
    }
    return 0;
}