Push down transfers lazy value to children:
def pushDown(node, start, end):
if lazy[node] != 0:
mid = (start + end) // 2
# Update children's values
tree[2*node] += lazy[node] * (mid - start + 1)
tree[2*node+1] += lazy[node] * (end - mid)
# Transfer lazy to children
lazy[2*node] += lazy[node]
lazy[2*node+1] += lazy[node]
# Clear this node's lazy
lazy[node] = 0
For range sum with range add:
- Node's value increases by
- Children inherit the lazy value
Always call pushDown before recursing to children in both query and update.