DSA Lazy Propagation
Lazy propagation stores a pending tag on a node instead of pushing a range update down to every leaf. The tag means the node's stored sum is current but its children are not.
A tag parked at the root
Adding five to the whole range stops at the root. The root sum rises by forty, while both children keep their old stored sums.
class LazySegTree:
def __init__(self, values):
self.n = len(values)
self.tree = [0] * (4 * self.n)
self.lazy = [0] * (4 * self.n)
self.pushes = 0
self.build(1, 0, self.n - 1, values)
def build(self, node, left, right, values):
if left == right:
self.tree[node] = values[left]
return
mid = (left + right) // 2
self.build(node * 2, left, mid, values)
self.build(node * 2 + 1, mid + 1, right, values)
self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]
def apply(self, node, left, right, delta):
self.tree[node] += delta * (right - left + 1)
self.lazy[node] += delta
def push(self, node, left, right):
if self.lazy[node] != 0 and left != right:
self.pushes += 1
mid = (left + right) // 2
self.apply(node * 2, left, mid, self.lazy[node])
self.apply(node * 2 + 1, mid + 1, right, self.lazy[node])
self.lazy[node] = 0
def add(self, node, left, right, ql, qr, delta):
if ql <= left and right <= qr:
self.apply(node, left, right, delta)
return
self.push(node, left, right)
mid = (left + right) // 2
if ql <= mid:
self.add(node * 2, left, mid, ql, qr, delta)
if qr > mid:
self.add(node * 2 + 1, mid + 1, right, ql, qr, delta)
self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]
def range_add(self, ql, qr, delta):
self.add(1, 0, self.n - 1, ql, qr, delta)
def query(self, node, left, right, ql, qr):
if ql <= left and right <= qr:
return self.tree[node]
self.push(node, left, right)
mid = (left + right) // 2
total = 0
if ql <= mid:
total += self.query(node * 2, left, mid, ql, qr)
if qr > mid:
total += self.query(node * 2 + 1, mid + 1, right, ql, qr)
return total
def sum(self, ql, qr):
return self.query(1, 0, self.n - 1, ql, qr)
def tags(self):
return {i: t for i, t in enumerate(self.lazy) if t != 0}
seg = LazySegTree([1, 2, 3, 4, 5, 6, 7, 8])
seg.range_add(0, 7, 5)
print("root sum:", seg.tree[1])
print("tags:", seg.tags())
print("left child sum stored:", seg.tree[2])
print("right child sum stored:", seg.tree[3])A partial query forces a push
Asking for the left half must descend past the tagged root. The push hands the tag to both children, and the count of pushes rises to one.
class LazySegTree:
def __init__(self, values):
self.n = len(values)
self.tree = [0] * (4 * self.n)
self.lazy = [0] * (4 * self.n)
self.pushes = 0
self.build(1, 0, self.n - 1, values)
def build(self, node, left, right, values):
if left == right:
self.tree[node] = values[left]
return
mid = (left + right) // 2
self.build(node * 2, left, mid, values)
self.build(node * 2 + 1, mid + 1, right, values)
self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]
def apply(self, node, left, right, delta):
self.tree[node] += delta * (right - left + 1)
self.lazy[node] += delta
def push(self, node, left, right):
if self.lazy[node] != 0 and left != right:
self.pushes += 1
mid = (left + right) // 2
self.apply(node * 2, left, mid, self.lazy[node])
self.apply(node * 2 + 1, mid + 1, right, self.lazy[node])
self.lazy[node] = 0
def add(self, node, left, right, ql, qr, delta):
if ql <= left and right <= qr:
self.apply(node, left, right, delta)
return
self.push(node, left, right)
mid = (left + right) // 2
if ql <= mid:
self.add(node * 2, left, mid, ql, qr, delta)
if qr > mid:
self.add(node * 2 + 1, mid + 1, right, ql, qr, delta)
self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]
def range_add(self, ql, qr, delta):
self.add(1, 0, self.n - 1, ql, qr, delta)
def query(self, node, left, right, ql, qr):
if ql <= left and right <= qr:
return self.tree[node]
self.push(node, left, right)
mid = (left + right) // 2
total = 0
if ql <= mid:
total += self.query(node * 2, left, mid, ql, qr)
if qr > mid:
total += self.query(node * 2 + 1, mid + 1, right, ql, qr)
return total
def sum(self, ql, qr):
return self.query(1, 0, self.n - 1, ql, qr)
def tags(self):
return {i: t for i, t in enumerate(self.lazy) if t != 0}
seg = LazySegTree([1, 2, 3, 4, 5, 6, 7, 8])
seg.range_add(0, 7, 5)
print("sum 0..3:", seg.sum(0, 3))
print("pushes so far:", seg.pushes)
print("tags now:", seg.tags())
print("sum 4..7:", seg.sum(4, 7))A partial update tags two nodes
Adding ten to indices 2 to 5 stops at the two nodes that cover that range. The root sum still rises by the full forty.
class LazySegTree:
def __init__(self, values):
self.n = len(values)
self.tree = [0] * (4 * self.n)
self.lazy = [0] * (4 * self.n)
self.pushes = 0
self.build(1, 0, self.n - 1, values)
def build(self, node, left, right, values):
if left == right:
self.tree[node] = values[left]
return
mid = (left + right) // 2
self.build(node * 2, left, mid, values)
self.build(node * 2 + 1, mid + 1, right, values)
self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]
def apply(self, node, left, right, delta):
self.tree[node] += delta * (right - left + 1)
self.lazy[node] += delta
def push(self, node, left, right):
if self.lazy[node] != 0 and left != right:
self.pushes += 1
mid = (left + right) // 2
self.apply(node * 2, left, mid, self.lazy[node])
self.apply(node * 2 + 1, mid + 1, right, self.lazy[node])
self.lazy[node] = 0
def add(self, node, left, right, ql, qr, delta):
if ql <= left and right <= qr:
self.apply(node, left, right, delta)
return
self.push(node, left, right)
mid = (left + right) // 2
if ql <= mid:
self.add(node * 2, left, mid, ql, qr, delta)
if qr > mid:
self.add(node * 2 + 1, mid + 1, right, ql, qr, delta)
self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]
def range_add(self, ql, qr, delta):
self.add(1, 0, self.n - 1, ql, qr, delta)
def query(self, node, left, right, ql, qr):
if ql <= left and right <= qr:
return self.tree[node]
self.push(node, left, right)
mid = (left + right) // 2
total = 0
if ql <= mid:
total += self.query(node * 2, left, mid, ql, qr)
if qr > mid:
total += self.query(node * 2 + 1, mid + 1, right, ql, qr)
return total
def sum(self, ql, qr):
return self.query(1, 0, self.n - 1, ql, qr)
def tags(self):
return {i: t for i, t in enumerate(self.lazy) if t != 0}
seg = LazySegTree([1, 2, 3, 4, 5, 6, 7, 8])
seg.range_add(2, 5, 10)
print("root sum:", seg.tree[1])
print("tags:", seg.tags())
print("sum 2..5:", seg.sum(2, 5))
print("sum 0..7:", seg.sum(0, 7))Example
class LazySegTree:
def __init__(self, values):
self.n = len(values)
self.tree = [0] * (4 * self.n)
self.lazy = [0] * (4 * self.n)
self.pushes = 0
self.build(1, 0, self.n - 1, values)
def build(self, node, left, right, values):
if left == right:
self.tree[node] = values[left]
return
mid = (left + right) // 2
self.build(node * 2, left, mid, values)
self.build(node * 2 + 1, mid + 1, right, values)
self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]
def apply(self, node, left, right, delta):
self.tree[node] += delta * (right - left + 1)
self.lazy[node] += delta
def push(self, node, left, right):
if self.lazy[node] != 0 and left != right:
self.pushes += 1
mid = (left + right) // 2
self.apply(node * 2, left, mid, self.lazy[node])
self.apply(node * 2 + 1, mid + 1, right, self.lazy[node])
self.lazy[node] = 0
def add(self, node, left, right, ql, qr, delta):
if ql <= left and right <= qr:
self.apply(node, left, right, delta)
return
self.push(node, left, right)
mid = (left + right) // 2
if ql <= mid:
self.add(node * 2, left, mid, ql, qr, delta)
if qr > mid:
self.add(node * 2 + 1, mid + 1, right, ql, qr, delta)
self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]
def range_add(self, ql, qr, delta):
self.add(1, 0, self.n - 1, ql, qr, delta)
def query(self, node, left, right, ql, qr):
if ql <= left and right <= qr:
return self.tree[node]
self.push(node, left, right)
mid = (left + right) // 2
total = 0
if ql <= mid:
total += self.query(node * 2, left, mid, ql, qr)
if qr > mid:
total += self.query(node * 2 + 1, mid + 1, right, ql, qr)
return total
def sum(self, ql, qr):
return self.query(1, 0, self.n - 1, ql, qr)
def tags(self):
return {i: t for i, t in enumerate(self.lazy) if t != 0}
values = [2, 4, 1, 3, 5, 2, 6, 1]
seg = LazySegTree(values)
print("start total:", seg.tree[1], "tags:", seg.tags())
seg.range_add(0, 7, 3)
for i in range(8):
values[i] += 3
print("after add 3 to 0..7, total:", seg.tree[1], "tags:", seg.tags())
seg.range_add(2, 4, 10)
for i in range(2, 5):
values[i] += 10
print("after add 10 to 2..4, total:", seg.tree[1], "tags:", seg.tags())
print("sum 0..3:", seg.sum(0, 3), "plain check:", sum(values[0:4]))
print("pushes so far:", seg.pushes, "tags:", seg.tags())
print("sum 4..7:", seg.sum(4, 7), "plain check:", sum(values[4:8]))
seg.range_add(5, 5, 100)
values[5] += 100
print("sum 0..7:", seg.sum(0, 7), "plain check:", sum(values))
print("total pushes:", seg.pushes)Key points
- A pending tag is a recorded update a node has applied to itself but not yet to its children
- Applying a tag adds the delta times the range length to the node's sum
- A push copies the parent's tag into both children and clears the parent
- Pushes happen only when an operation must descend past a tagged node
- A fully covered node takes the tag and stops the descent at once
In this example, range adds and range sums interleave on eight values, with a plain list tracking the truth. A whole-range add parks one tag at the root, shown in the first snapshot. Later operations push tags down only along the paths they must descend. Every query answer matches the plain list value printed beside it, and four pushes happen across the whole run.
Note
the tags here are pending adds, the simplest lazy tag to trace.
Try it Yourself
Edit the code, then press Run.
Running is simulated · Python Playground
Exercise
What does a push do at a tagged node?