Untitled

ll merge(ll x,ll y)
{
    return x+y;
}

struct segment_tree
{

    vector<ll>tree;
    vector<ll>lazy;
    void build(vector<ll>&a,int ns=0,int ne=n1-1,int id=0)
    {
        if (ns==ne)
        {
            tree[id]=a[ns];
            return ;
        }
        ll l=2*id+1,r=l+1;
        ll mid=(ns+ne)/2 ;
        build(a,ns,mid,l);
        build(a,mid+1,ne,r);
        tree[id]=merge(tree[l],tree[r]);
    }
    void init(vector<ll>&a,int ne)
    {
        n1=ne;
        tree.assign(4*ne,0ll);
        lazy.assign(4*ne,0ll);
        build(a);
    }
    ll query(ll qs,ll qe,ll id=0,ll ns=0,ll ne=n1-1)
    {
        update_lazy(id,ns,ne);
        if (ns>qe || qs>ne)
        {
            return 0;
        }
        if (ns>=qs && ne<=qe)
            return tree[id];
        ll l=2*id+1;
        ll r=l+1;
        ll mid=(ns+ne)/2;
        ll a1= query(qs,qe,l,ns,mid);
        ll b1= query(qs,qe,r,mid+1,ne);
        return merge(a1,b1);
    }
    void update_lazy(int id,int ns,int ne=n1-1)
    {
        if (lazy[id])
            tree[id]=lazy[id]*(ne-ns+1);
        if (ns!=ne)
        {
            ll l=2*id+1;
            ll r=l+1;
            lazy[l]+=lazy[id];
            lazy[r]+=lazy[id];
        }
        lazy[id]=0;
    }
    void upd(int qs,int qe,ll value,ll id=0,int ns=0,int ne=n1-1)
    {
        update_lazy(id,ns,ne);
        if (qs>ne || ns>qe)
            return ;
        if (qs<=ns && qe>=ne)
        {
            lazy[id]=value;
            update_lazy(id,ns,ne);
            return ;
        }
        ll l=2*id+1,r=l+1;
        ll mid=(ns+ne)/2;
        upd(qs,qe,value,l,ns,mid);
        upd(qs,qe,value,r,mid+1,ne);
        tree[id]=merge(tree[l],tree[r]);
    }
};