Dynamic Segment tree

int n,q;

struct node{
    node *left,*right;
    ll lazy,sum;
    node(){
        left = right = NULL;
        lazy = sum = 0;
    }
}*root;

ll Sum(ll l,ll r){
    return (r*(r+1))/2 - (l*(l-1))/2;
}

void checkLazy(node *curr,ll b,ll e){
        if(curr->lazy!=0){
        if(b!=e){
            int mid = (b+e)>>1;
            if(!curr->left)curr->left = new node();
            if(!curr->right)curr->right = new node();
            curr->left->sum-=(curr->lazy*(ll)(mid-b+1));
            curr->right->sum-=(curr->lazy*(ll)(e-mid));
            curr->left->lazy+=curr->lazy;
            curr->right->lazy+=curr->lazy;
        }
        curr->lazy = 0;
    }
}

void update(node *curr,ll b,ll e,ll l,ll r,ll val){
    checkLazy(curr,b,e);
    if(l>e||b>r)return ;
    if(b>=l&&e<=r){
        curr->sum-=(val*(ll)(e-b+1));
        curr->lazy+=val;
        return ;
    }
    if(!curr->left)curr->left = new node();
    if(!curr->right)curr->right = new node();
    int mid = (b+e)>>1;
    update(curr->left,b,mid,l,r,val);
    update(curr->right,mid+1,e,l,r,val);
    curr->sum = curr->left->sum + curr->right->sum;
}

ll query(node *curr,ll b,ll e,ll l,ll r){
    checkLazy(curr,b,e);
    if(b>r||l>e)return 0;
    if(b>=l&&e<=r)return curr->sum;
    if(!curr->left)curr->left = new node();
    if(!curr->right)curr->right = new node();
    int mid = (b+e)>>1;
    ll p1 = query(curr->left,b,mid,l,r);
    ll p2 = query(curr->right,mid+1,e,l,r);
    return p1 + p2;
}


int main()
{
    ///booster()
    ///read("input.txt");
    scani2(n,q);
    root = new node();
    while(q--){
        int c,l,r;
        scani3(c,l,r);
        if(c==1){
            int v;
            scani(v);
            update(root,1,MAX,l,r,v);
        }
        else printf("%lld\n",Sum(l,r) + query(root,1,MAX,l,r));
    }

    return 0;
}