Data Structures19 sections · 729 units
Open in Course

Push Down Operation

Propagating lazy values

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 lazy×range_size\text{lazy} \times \text{range\_size}
  • Children inherit the lazy value

Always call pushDown before recursing to children in both query and update.