There is an array of n elements, initially filled with zeros. You need to write a data structure that processes two types of queries:

add v to the segment from l to r-1, find the sum on the segment from l to r−1.

Input The first line contains two numbers n and m (1≤n,m≤100000), the size of the array and the number of operations. The following lines contain the description of the operations. The description of each operation is as follows:

1 l r v: add v to the segment from l to r−1 (0≤l<r≤n, 0≤v≤105). 2 l r: find the sum on the segment from l to r−1 (0≤l<r≤n).

Output For each operation of the second type, print the corresponding value.

My Code:

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD=1e9+7;

const int N = 1e5;
ll seg_tree[4*N];
ll lazy[4*N];

void push(int l, int r, int node){
    if(l!=r&&lazy[node]!=0){
        int m = l + (r-l)/2;
        seg_tree[2*node]+=(m-l+1)*lazy[node];
        seg_tree[2*node+1]+=(r-m)*lazy[node];
        lazy[2*node+1]+=lazy[node];
        lazy[2*node]+=lazy[node];
        lazy[node]=0;
    }
}

void update(int l, int r, int i, int j, int val, int node){
    if(i>r||j<l) return;                    // OR l>r
    if(i<=l&&j>=r){
        seg_tree[node]+=(r-l+1)*val;
        lazy[node]+=val;
        return;
    }
    push(l,r,node);
    int m = (l+r)/2;
    update(l,m,i,min(j,m),val,2*node); update(m+1,r,max(i,m+1),j,val,2*node+1);
    seg_tree[node]=seg_tree[2*node]+seg_tree[2*node+1];
}

ll query(int l, int r, int i, int j, int node){
    if(i>r||j<l) return 0;
    if(l>=i&&r<=j){             // OR if(l>=i&&r<=j) returns seg_tree[node];    -> both are correct.
        return seg_tree[node];
    }
    push(l,r,node);
    int m = (l+r)/2;
    return query(l,m,i,min(j,m),2*node) + query(m+1,r,max(i,m+1),j,2*node+1);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m; cin>>n>>m;
    while(m--){
        int t; cin>>t;
        if(t==1){
            int i,j,v; cin>>i>>j>>v;
            update(0,n-1,i,j-1,v,1);
        }
        else{
            int i,j; cin>>i>>j;
            cout<<query(0,n-1,i,j-1,1)<<'\n';
        }
    }
}

24 hours and couldn't figure out what's wrong in my code. Can anyone help me decode what's wrong with my solution ? I'm getting wrong answer on test case 61 with '!' symbol.