Algorithms · Data Structures

Update Lazily.

Q: What is a lazy segment tree?

A segment tree augmented with lazy propagation, which lets it perform range updates (like adding a value to every element in a range) in O(log n) instead of O(n). It does this by storing a pending "lazy" tag on the O(log n) nodes that cover the update range, updating their aggregate immediately but deferring the update to their children until a later operation descends through them.

Q: What is lazy propagation?

Lazy propagation is the technique of deferring updates in a segment tree. Instead of applying a range update all the way down to the leaves, you apply it to the few nodes that cover the range and store a pending tag there. The pending update is "propagated" (pushed down) to a node’s children only when a subsequent query or update actually needs to look below that node.

Q: How does a lazy segment tree compare to a Fenwick tree?

A Fenwick (binary indexed) tree is simpler and smaller and handles prefix sums with point updates in O(log n), and with a trick, range updates too — but it’s specialized and hard to extend to arbitrary aggregates. A lazy segment tree is more general: it supports range updates and range queries for sums, minimums, maximums, assignments, and combinations, at the cost of more code and memory. Choose Fenwick for simple sum problems, lazy segment tree when you need flexible range operations.

Q: What operations can lazy segment trees support?

Many range-update, range-query combinations: range add with range sum, range add with range min or max, range assignment (set every element in a range to a value) with range sum/min/max, and more. The requirement is that the lazy tag can be composed (multiple pending updates merge) and applied to a node’s aggregate knowing only the node’s range size. This makes them a versatile tool in competitive programming and interval problems.

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).

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.

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.

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 sum def 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: return if ql <= l and r <= qr: # node fully covered tree[nd] += v * (r - l + 1); lazy[nd] += v # tag, don't descend return 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)?

2. What does a lazy tag on a node represent?

3. When is a lazy tag pushed down to the children?

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.

Keep going

Finished this one? 0 / 98 Algorithms done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA

Update Lazily.

How it works

Find the covering nodes

Update aggregate, defer the rest

Push down on demand

Both operations stay O(log n)

The code

Quick check

FAQ

Keep going

Explore the topic

More Algorithms

Explore more from Vibe Engines

How it works

Find the covering nodes

Update aggregate, defer the rest

Push down on demand

Both operations stay O(log n)

The code

Quick check

FAQ

Keep going

Segment Tree →

Fenwick Tree →

Sqrt Decomposition →

The DSA Roadmap →

Explore the topic

More Algorithms

Explore more from Vibe Engines

Get the next one in your inbox.