Pattern Guide
Segment Tree: Lazy Propagation
"Range update in O(log n). Defer the work until you actually need it."
Lazy propagation extends Segment Trees to support range updates (add/set all elements in [l..r]) in O(log n). Without lazy, range updates are O(n). The insight: defer updates by storing a "pending" tag at each node, propagating it only when you need to visit children.
20 min readadvanced tree problems →
Problems you can solve with this pattern
4 problems · click any to start solving
Range add + range sum with lazy propagation
class LazySegTree {
constructor(n) {
this.n = n;
this.tree = new Array(4 * n).fill(0); // sum at each node
this.lazy = new Array(4 * n).fill(0); // pending add for whole subtree
}
// Push down pending update to children
_push(node, start, end) {
if (this.lazy[node] === 0) return;
const mid = (start + end) >> 1;
const left = 2*node+1, right = 2*node+2;
// Apply lazy to children
this.tree[left] += this.lazy[node] * (mid - start + 1);
this.tree[right] += this.lazy[node] * (end - mid);
this.lazy[left] += this.lazy[node];
this.lazy[right] += this.lazy[node];
this.lazy[node] = 0; // clear pending
}
// Range update: add val to all elements in [l, r]
update(node, start, end, l, r, val) {
if (r < start || end < l) return; // out of range
if (l <= start && end <= r) { // fully covered
this.tree[node] += val * (end - start + 1);
this.lazy[node] += val;
return;
}
this._push(node, start, end);
const mid = (start + end) >> 1;
this.update(2*node+1, start, mid, l, r, val);
this.update(2*node+2, mid+1, end, l, r, val);
this.tree[node] = this.tree[2*node+1] + this.tree[2*node+2];
}
// Range query: sum of [l, r]
query(node, start, end, l, r) {
if (r < start || end < l) return 0;
if (l <= start && end <= r) return this.tree[node];
this._push(node, start, end);
const mid = (start + end) >> 1;
return this.query(2*node+1, start, mid, l, r)
+ this.query(2*node+2, mid+1, end, l, r);
}
// Public API
rangeAdd(l, r, val) { this.update(0, 0, this.n-1, l, r, val); }
rangeSum(l, r) { return this.query(0, 0, this.n-1, l, r); }
}Basic segment tree handles point updates + range queries in O(log n). But if you need range updates (add 5 to all elements in [l,r]), the naive approach visits all O(n) elements. Lazy propagation fixes this by storing a pending update at a node and only pushing it down when you need to visit the children. The subtree root always has the correct answer; the pending tag ensures children will be updated when visited.
| Operation | Without Lazy | With Lazy |
|---|---|---|
| Point update | O(log n) | O(log n) |
| Range update (add to all in [l,r]) | O(n) | O(log n) |
| Range query (sum/min/max of [l,r]) | O(log n) | O(log n) |
| Build | O(n) | O(n) |
Lazy Segment Tree Template
Range add + range sum with lazy propagation
class LazySegTree {
constructor(n) {
this.n = n;
this.tree = new Array(4 * n).fill(0); // sum at each node
this.lazy = new Array(4 * n).fill(0); // pending add for whole subtree
}
// Push down pending update to children
_push(node, start, end) {
if (this.lazy[node] === 0) return;
const mid = (start + end) >> 1;
const left = 2*node+1, right = 2*node+2;
// Apply lazy to children
this.tree[left] += this.lazy[node] * (mid - start + 1);
this.tree[right] += this.lazy[node] * (end - mid);
this.lazy[left] += this.lazy[node];
this.lazy[right] += this.lazy[node];
this.lazy[node] = 0; // clear pending
}
// Range update: add val to all elements in [l, r]
update(node, start, end, l, r, val) {
if (r < start || end < l) return; // out of range
if (l <= start && end <= r) { // fully covered
this.tree[node] += val * (end - start + 1);
this.lazy[node] += val;
return;
}
this._push(node, start, end);
const mid = (start + end) >> 1;
this.update(2*node+1, start, mid, l, r, val);
this.update(2*node+2, mid+1, end, l, r, val);
this.tree[node] = this.tree[2*node+1] + this.tree[2*node+2];
}
// Range query: sum of [l, r]
query(node, start, end, l, r) {
if (r < start || end < l) return 0;
if (l <= start && end <= r) return this.tree[node];
this._push(node, start, end);
const mid = (start + end) >> 1;
return this.query(2*node+1, start, mid, l, r)
+ this.query(2*node+2, mid+1, end, l, r);
}
// Public API
rangeAdd(l, r, val) { this.update(0, 0, this.n-1, l, r, val); }
rangeSum(l, r) { return this.query(0, 0, this.n-1, l, r); }
}Range Set Variant
Range set (assign all to val) instead of range add
// For "set all elements in [l,r] to val" operations:
// Use a different lazy encoding: lazy[node] = -1 means "no pending",
// any other value means "set all to this value"
class LazySetSegTree {
constructor(n) {
this.n = n;
this.tree = new Array(4*n).fill(0);
this.lazy = new Array(4*n).fill(-1); // -1 = no pending
}
_push(node, start, end) {
if (this.lazy[node] === -1) return;
const mid = (start+end)>>1, val = this.lazy[node];
const l=2*node+1, r=2*node+2;
this.tree[l] = val * (mid-start+1);
this.tree[r] = val * (end-mid);
this.lazy[l] = this.lazy[r] = val;
this.lazy[node] = -1;
}
rangeSet(node, start, end, l, r, val) {
if(r<start||end<l) return;
if(l<=start&&end<=r){this.tree[node]=val*(end-start+1);this.lazy[node]=val;return;}
this._push(node,start,end);
const mid=(start+end)>>1;
this.rangeSet(2*node+1,start,mid,l,r,val);
this.rangeSet(2*node+2,mid+1,end,l,r,val);
this.tree[node]=this.tree[2*node+1]+this.tree[2*node+2];
}
}Lazy propagation rules:
1. When a node is FULLY covered by the update range: update tree[node] and lazy[node], STOP (don't recurse)
2. When a node is PARTIALLY covered: push down first (_push), then recurse to children, then pull up (tree[node] = combine children)
3. In _push: apply lazy to children's tree and lazy values, then clear parent's lazy
The lazy value accumulates: multiple range-adds stack up in lazy[node]. When you push down, you pass the accumulated value to children.
Range set vs range add: Need different "no-op" sentinel (-1 for set, 0 for add). They can be combined but gets complex.
1. When a node is FULLY covered by the update range: update tree[node] and lazy[node], STOP (don't recurse)
2. When a node is PARTIALLY covered: push down first (_push), then recurse to children, then pull up (tree[node] = combine children)
3. In _push: apply lazy to children's tree and lazy values, then clear parent's lazy
The lazy value accumulates: multiple range-adds stack up in lazy[node]. When you push down, you pass the accumulated value to children.
Range set vs range add: Need different "no-op" sentinel (-1 for set, 0 for add). They can be combined but gets complex.