Range Addition Solution

Complete lazy segment tree implementation:

class LazySegTree:
    function init(n):
        this.n = n
        this.tree = array of 4*n zeros
        this.lazy = array of 4*n zeros

    function push(node, start, end):
        if this.lazy[node]:
            mid = floor((start + end) / 2)
            this.tree[2*node] += this.lazy[node] * (mid - start + 1)
            this.tree[2*node+1] += this.lazy[node] * (end - mid)
            this.lazy[2*node] += this.lazy[node]
            this.lazy[2*node+1] += this.lazy[node]
            this.lazy[node] = 0

Notice: lazy propagation is "pay later." We defer work until you must have the accurate value.

Test with: overlapping range updates, query after multiple updates, query entire array.