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.