Lazy Segment Tree
The standard extension of a segment tree when range updates must stay logarithmic too.
Lazy Segment Tree
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Lazy propagation is what turns a plain segment tree into a practical range-update structure. Instead of pushing every update all the way to the leaves immediately, the tree delays work until that work is actually needed.
This is the standard contest upgrade when the problem asks for range updates together with range queries, such as ``add \(x\) to every value on \([l, r]\)'' and ``report the sum on \([l, r]\)''.
When to Use It
Use it when:
updates affect whole intervals rather than single points,
queries still ask for segment aggregates,
the update can be composed compactly as a lazy tag,
doing the update naively would touch too many leaves.
If the operation is static, a difference array might be enough. If the update logic is too complicated to summarize in one tag, a plain lazy tree may stop being the right tool.
Core Idea
Each node still represents a segment and stores its aggregate. The new ingredient is a lazy tag: pending work that conceptually applies to the whole segment but has not yet been pushed to the children.
For range add / range sum, if I add \(x\) to a segment of length \(\ell\), then:
the node sum increases by \(x \cdot \ell\),
the children do not need to be updated immediately,
I only record that both children should eventually receive \(x\) as well.
That deferred record is the lazy value.
Key Insight
Lazy propagation works because a query or update never needs the children to be exact until it descends below the current node. As long as the whole current segment is either fully covered or fully skipped, it is enough that the current node summary is correct.
So the tree can postpone detailed child work without losing correctness. The delayed work is pushed only when a later operation partially overlaps the segment and needs to see finer structure.
Operations / Main Technique
The three core routines are:
apply(node, tag): update the node summary and combine the lazy tag,
push(node): send the pending tag to the children before going deeper,
pull(node): recompute the parent from the children after a recursive change.
Worked example.
Suppose the tree stores sums and I apply ``add \(5\)'' on \([1, 8]\). The root sum increases by \(5 \cdot 8\), and the root lazy tag becomes \(+5\). If the next query asks only about \([1, 4]\), then the root must first push the tag so the left and right children both learn about that pending \(+5\).
Correctness Intuition
The invariant is that every node's stored summary already reflects all updates that fully covered that node's segment, even if some of those updates have not been propagated to descendants yet.
When we descend, push preserves that invariant by transferring the pending effect to the children. When we return from recursion, pull restores the parent summary from the now-correct child summaries.
So lazy propagation does not skip work forever. It only postpones work until the tree actually needs lower-level detail.
Complexity Analysis
range update: \(O(\log n)\),
range query: \(O(\log n)\),
memory: \(O(n)\).
Each operation visits only \(O(\log n)\) nodes on the recursion frontier, and each visited node does only constant extra work for tag handling.
Implementation
The reference code implements the most common teaching version:
range add,
range sum,
recursive tree,
one lazy tag per node.
That version is useful because the meaning of every field is easy to state. Once this shape is stable, it is much easier to adapt it to range assign, range min/max, or tree-path problems.
Common Pitfalls
Updating the node sum but forgetting to store the lazy tag.
Pushing too late, so a partial-overlap recursion reads stale child data.
Pulling from children that have not yet received the pushed tag.
Mixing segment length formulas, especially with inclusive endpoints.
Treating range assign and range add as if they compose the same way.
Most wrong answers come from violating the meaning of ``what is already reflected in this node''.
Variants / Extensions
range assign + range sum,
range min/max with range add,
lazy segment tree over custom monoids,
tree-path queries after heavy-light decomposition,
segment tree beats when one lazy tag is no longer expressive enough.
AtCoder Library's
lazysegtreeis a good reference for the ``generic algebraic'' viewpoint, but in contest practice I still like understanding one concrete hand-written version first.
Practice Problems
Range add and range sum on one array.
Range assign and range minimum.
Heavy-light decomposition problems that need path updates instead of only path queries.
Problems where you must define the node summary and lazy tag yourself.
References
Code
Contest-ready reference implementation for the idea explained above.
struct LazySegTree {
int n;
vector<long long> sum, lazy;
LazySegTree() : n(0) {}
explicit LazySegTree(const vector<long long>& values) { build(values); }
void build(const vector<long long>& values) {
n = (int)values.size();
sum.assign(4 * n, 0);
lazy.assign(4 * n, 0);
build(1, 0, n - 1, values);
}
void build(int node, int left, int right, const vector<long long>& values) {
if (left == right) {
sum[node] = values[left];
return;
}
int mid = (left + right) >> 1;
build(node << 1, left, mid, values);
build(node << 1 | 1, mid + 1, right, values);
pull(node);
}
void apply(int node, int left, int right, long long delta) {
sum[node] += delta * (right - left + 1);
lazy[node] += delta;
}
void push(int node, int left, int right) {
if (lazy[node] == 0 || left == right) return;
int mid = (left + right) >> 1;
apply(node << 1, left, mid, lazy[node]);
apply(node << 1 | 1, mid + 1, right, lazy[node]);
lazy[node] = 0;
}
void pull(int node) {
sum[node] = sum[node << 1] + sum[node << 1 | 1];
}
void range_add(int ql, int qr, long long delta) {
range_add(1, 0, n - 1, ql, qr, delta);
}
void range_add(int node, int left, int right, int ql, int qr, long long delta) {
if (qr < left || right < ql) return;
if (ql <= left && right <= qr) {
apply(node, left, right, delta);
return;
}
push(node, left, right);
int mid = (left + right) >> 1;
range_add(node << 1, left, mid, ql, qr, delta);
range_add(node << 1 | 1, mid + 1, right, ql, qr, delta);
pull(node);
}
long long range_sum(int ql, int qr) {
return range_sum(1, 0, n - 1, ql, qr);
}
long long range_sum(int node, int left, int right, int ql, int qr) {
if (qr < left || right < ql) return 0;
if (ql <= left && right <= qr) return sum[node];
push(node, left, right);
int mid = (left + right) >> 1;
return range_sum(node << 1, left, mid, ql, qr) +
range_sum(node << 1 | 1, mid + 1, right, ql, qr);
}
};
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.