Lazy Propagation
Sometimes we need to update a range of elements (e.g., add a value to all elements in [L, R]). Without lazy propagation, updating each element would take O(n log n). Lazy propagation allows range updates in O(log n) by postponing updates to children until necessary.
Idea: Each node stores a "lazy" value representing pending updates to its entire segment. When updating a range, if the node's segment is fully inside the range, we update its value and accumulate the lazy value. When querying, we push lazy values to children before descending.
Example: Range increment and range sum query. We maintain an array `lazy` of same size as tree. For range add update:
int[] tree, lazy;
public void updateRange(int node, int start, int end, int L, int R, int val) {
if (lazy[node] != 0) {
tree[node] += (end - start + 1) * lazy[node];
if (start != end) {
lazy[2*node] += lazy[node];
lazy[2*node+1] += lazy[node];
}
lazy[node] = 0;
}
if (R < start || L > end) return;
if (L <= start && end <= R) {
tree[node] += (end - start + 1) * val;
if (start != end) {
lazy[2*node] += val;
lazy[2*node+1] += val;
}
return;
}
int mid = (start + end) / 2;
updateRange(2*node, start, mid, L, R, val);
updateRange(2*node+1, mid+1, end, L, R, val);
tree[node] = tree[2*node] + tree[2*node+1];
}
public int queryRange(int node, int start, int end, int L, int R) {
if (lazy[node] != 0) {
tree[node] += (end - start + 1) * lazy[node];
if (start != end) {
lazy[2*node] += lazy[node];
lazy[2*node+1] += lazy[node];
}
lazy[node] = 0;
}
if (R < start || L > end) return 0;
if (L <= start && end <= R) return tree[node];
int mid = (start + end) / 2;
return queryRange(2*node, start, mid, L, R) + queryRange(2*node+1, mid+1, end, L, R);
}
Two Minute Drill
- Lazy propagation defers updates to children until needed.
- Each node has a lazy value to be applied to its entire segment.
- Range updates become O(log n).
- Push lazy values before descending.
- Essential for efficient range updates and queries.
Need more clarification?
Drop us an email at career@quipoinfotech.com