Complete lazy segment tree implementation:
class LazySegTree:
def __init__(self, n):
self.n = n
self.tree = [0] * (4 * n)
self.lazy = [0] * (4 * n)
def _push(self, node, start, end):
if self.lazy[node]:
mid = (start + end) // 2
self.tree[2*node] += self.lazy[node] * (mid - start + 1)
self.tree[2*node+1] += self.lazy[node] * (end - mid)
self.lazy[2*node] += self.lazy[node]
self.lazy[2*node+1] += self.lazy[node]
self.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.