A segment tree answers a range-sum query in O(log n) by combining a few precomputed nodes. But a range update — “add 10 to every element in [2, 5]” — would be O(n) if you dutifully walked down and changed every leaf. Lazy propagation is the trick that keeps updates O(log n) too: mark the handful of nodes that exactly cover the range with a pending lazy tag, update their aggregate, and defer pushing the change to their children until a later query actually descends through them. Do the range-add and watch just a few nodes get tagged instead of every leaf.
O(log n) range update & range query · lazy tag defers work · push down only when needed
segment tree
A binary tree over the array; each node stores an aggregate of its range.
covering nodes
The O(log n) nodes whose ranges exactly tile the query/update range.
lazy tag
A pending update stored on a node, not yet applied to its children.
push down
Apply a node’s lazy tag to its two children — done only when a query descends.
lazy.js — tag now, push down later
Ready
A segment tree over 8 values. Each node holds the sum of its range. A range +v update tags only the few nodes that exactly cover the range (a lazy value), instead of updating all the leaves. Range +v to try.
–
nodes tagged
–
leaves naive
–
last query
How it works
The idea is to be honest about a node’s aggregate immediately, but lazy about its descendants. When a range update fully covers a node, you can update that node’s stored sum right away — adding v × (size of its range) — because you know exactly how many elements it spans. What you postpone is telling its children. You stash v in the node’s lazy tag. Later, if a query or update needs to go below that node, you first “push down”: apply the tag to both children (updating their sums and their own lazy tags) and clear it. Because every update and query only ever visits O(log n) nodes and pushes down along one root-to-leaf path, both stay O(log n).
1
Find the covering nodes
For a range update, recurse from the root and stop at each node whose range lies entirely inside the update range. There are only O(log n) such nodes.
2
Update aggregate, defer the rest
At each covering node, add v × (its range size) to its stored sum immediately, and add v to its lazy tag — a promise to update its children later. Do not descend further.
3
Push down on demand
When a later operation needs to go below a tagged node, first push the tag to both children (updating their sums and lazy tags) and clear it. This keeps stored sums correct without ever touching untouched subtrees.
✓
Both operations stay O(log n)
Updates tag O(log n) covering nodes; queries combine O(log n) covering nodes, pushing down along one path. Range updates and range queries are both logarithmic.
Range update
O(log n)
Range query
O(log n)
Space
O(n)
Key trick
lazy tag
The code
# lazy propagation: range add, range sumdef push_down(nd, l, r):
if lazy[nd]:
m = (l + r) // 2
for c, cl, cr in ((2*nd, l, m), (2*nd+1, m+1, r)):
tree[c] += lazy[nd] * (cr - cl + 1) # apply to child sum
lazy[c] += lazy[nd] # pass tag down
lazy[nd] = 0
def update(nd, l, r, ql, qr, v):
if qr < l or r < ql: returnif ql <= l and r <= qr: # node fully covered
tree[nd] += v * (r - l + 1); lazy[nd] += v # tag, don't descendreturn
push_down(nd, l, r); m = (l + r) // 2
update(2*nd, l, m, ql, qr, v); update(2*nd+1, m+1, r, ql, qr, v)
tree[nd] = tree[2*nd] + tree[2*nd+1]
Quick check
1. Why would a range update without lazy propagation be O(n)?
A range can contain up to n elements. Updating each leaf individually is O(n). Lazy propagation avoids this by tagging O(log n) covering nodes instead of descending to every leaf.
2. What does a lazy tag on a node represent?
The lazy tag is a deferred update: the node’s own stored sum already reflects it, but its children haven’t been told. The tag is pushed down only when an operation needs to descend below the node.
3. When is a lazy tag pushed down to the children?
Push-down is done on demand: right before an operation goes below a tagged node, its tag is applied to both children and cleared. Subtrees no operation visits are never touched, which is what keeps everything O(log n).
FAQ
What is a lazy segment tree?
A segment tree with lazy propagation, enabling range updates (e.g. add v to a whole range) in O(log n) instead of O(n). It stores a pending "lazy" tag on the O(log n) covering nodes — updating their aggregate now but deferring the push to children until an operation descends through them.
What is lazy propagation?
Deferring updates in a segment tree: apply a range update only to the few covering nodes and store a pending tag there, then push that tag down to a node’s children only when a later operation needs to look below it. Work is done lazily, on demand.
How does a lazy segment tree compare to a Fenwick tree?
A Fenwick tree is simpler and smaller, great for prefix sums with point (and, with a trick, range) updates, but hard to extend. A lazy segment tree is more general — range updates and queries for sum, min, max, assignment, etc. — at the cost of more code and memory. Fenwick for simple sums; lazy segment tree for flexible range ops.
What operations can lazy segment trees support?
Many range-update/range-query combos: range-add with range-sum, range-add with range-min/max, range-assign with range-sum/min/max, and more. The requirement is that lazy tags compose and can be applied to a node’s aggregate from its range size alone — making them a versatile tool for interval problems.
SOLVE IT YOURSELF
Solve it: update a whole range in O(log n)
A plain segment tree updates one element at a time — adding 5 to a million cells costs a million operations. Lazy propagation writes the update on a node and defers it until someone actually looks. Python or TypeScript.
YOUR TASK
Implement range_add(lo, hi, val) and range_sum(lo, hi) on a segment tree with lazy propagation. Both inclusive, both O(log n).
HINTS — 7 IDEAS
Every node carries a lazy value: "everything below me still owes this much, and does not know it yet".
Push before you read or descend: apply lazy × segment_length to this node’s sum, hand the value to both children, then clear it.
Multiplying by the segment length is the step people miss — a pending +5 over 8 elements adds 40 to that node’s sum, not 5.
On update: if the node’s range is fully inside the target, record the lazy value and push immediately, then return without touching any descendant. That early return is where the speed comes from.
If it only partly overlaps, recurse into both children and recompute this node’s sum from theirs.
On query, push before descending, or you read a sum that has not absorbed its pending update yet.
Every node is either fully covered (stop) or partly (recurse), and only O(log n) nodes are ever partly covered.