segTree with lazy.txt

//segment tree for summation with lazy prop

void build(ll tree[],ll a[],ll node, ll start, ll end)
{
    if(start == end)
    {
        tree[node] = a[start];
    }
    else
    {
        ll mid = (start + end) / 2;
        
        build(tree,a,(2*node)+1, start, mid);
        
        build(tree,a,(2*node)+2, mid+1, end);
        
        tree[node] = tree[(2*node)+1] + tree[(2*node)+2];
    }
}

void updateRange(ll tree[],ll lazy[],ll node, ll start, ll end, ll l, ll r, ll val)
{
    if(lazy[node] != 0)
    { 
        // This node needs to be updated
        tree[node] += (end - start + 1) * lazy[node];    // Update it

        if(start != end)
        {
            lazy[(2*node)+1] += lazy[node];                  // Mark child as lazy
            lazy[(2*node)+2] += lazy[node];                // Mark child as lazy
        }

        lazy[node] = 0;                                  // Reset it
    }

    if(start > end or start > r or end < l)              // Current segment is not within range [l, r]
        return;

    if(start >= l and end <= r)
    {
        // Segment is fully within range
        
        tree[node] += (end - start + 1) * val;
        
        if(start != end)
        {
            // Not leaf node
            lazy[(2*node)+1] += val;
            lazy[(2*node)+2] += val;
        }
        return;
    }

    ll mid = (start + end) / 2;
    
    updateRange(tree,lazy,(2*node)+1, start, mid, l, r, val);        
    updateRange(tree,lazy,(2*node)+2, mid + 1, end, l, r, val);  
    
    tree[node] = tree[(2*node)+1] + tree[(2*node)+2];         
}

ll queryRange(ll tree[],ll lazy[],ll node, ll start, ll end, ll l, ll r)
{
    if(start > end or start > r or end < l)
        return 0;         // Out of range
    
    if(lazy[node] != 0)
    {
        // This node needs to be updated
        tree[node] += (end - start + 1) * lazy[node];            // Update it
        
        if(start != end)
        {
            lazy[(2*node)+1] += lazy[node];         // Mark child as lazy
            lazy[(2*node)+2] += lazy[node];    // Mark child as lazy
        }
        
        lazy[node] = 0;                 // Reset it
    }

    if(start >= l and end <= r)             // Current segment is totally within range [l, r]
        return tree[node];
    
    ll mid = (start + end) / 2;
    ll p1 = queryRange(tree,lazy,(2*node)+1, start, mid, l, r);         
    ll p2 = queryRange(tree,lazy,(2*node)+2, mid + 1, end, l, r); 
    return (p1 + p2);
}