Range Update with Lazy

Range update adds value to all elements in $[l, r]$:

def rangeUpdate(node, start, end, l, r, val):
    if r < start or end < l:
        return
    if l <= start and end <= r:
        # Completely inside: apply lazy
        tree[node] += val * (end - start + 1)
        lazy[node] += val
        return
    pushDown(node, start, end)
    mid = (start + end) // 2
    rangeUpdate(2*node, start, mid, l, r, val)
    rangeUpdate(2*node+1, mid+1, end, l, r, val)
    tree[node] = tree[2*node] + tree[2*node+1]

When completely inside the update range, mark as lazy and return immediately. Don't recurse. That's why it's $O(\log n)$.