The segment tree already answers arbitrary
range queries in O(log n), but its update only ever touches one index at a
time. Adding 10 to every element in [2, 5] the way that page's update
is written means four separate point updates — four separate root-to-leaf walks, each fixing
O(log n) nodes, for O(k log n) total on a k-element range.
Lazy propagation gets a whole-range update down to O(log n) too: when
a range update's target range exactly covers a node's range, stop right there — record the pending
change as a tag on that one node instead of walking into its subtree — and only pay to push that
tag down into the children later, if and when some other operation actually needs to look inside.
Whole subtrees stay "correct in aggregate, stale underneath" for as long as nothing asks to see
underneath.
Same 8-value array as the segment tree page
([5, 2, 8, 1, 9, 3, 7, 4], sum 39), same node numbering (node 1 is the root, nodes
8-15 are the leaves) — but each node now tracks a running sum of its range instead
of a minimum, and carries a small orange lazy badge whenever it's holding a pending
tag not yet pushed to its children. Pick a range and a value and press Range Add to
add that value to every element in the range, or pick a range and press Range Sum to
query it, then step through to see exactly which nodes get touched, which get short-circuited with a
tag, and which force a push-down.
A range update's recursive walk classifies every node it visits into one of three cases.
Outside the target range: skip immediately, no cost at all. Fully inside
the target range: this is the short-circuit — apply the update to the node's own stored sum right
here (tree[node] += val × (length of the node's range)), record val as a
pending tag on the node (lazy[node] += val), and stop, never recursing
into its children. Partially overlapping the target range: if this node has a
pending tag of its own, push it down to both children first (give each child
tag × (that child's range length) added to its own sum, and hand each child the same
tag to accumulate into its own lazy slot), then recurse into both children and recompute this node's
sum as their total on the way back up. The default Range Add of +10 over
[2, 5] visits the root (partial, recurse), node 2 (partial, recurse), node 5 — range
[2,3], fully inside — absorbs the tag directly (29, was 9,
lazy[5] = 10) and stops, node 3 (partial, recurse), node 6 — range [4,5],
fully inside — absorbs the tag directly (32, was 12, lazy[6] = 10)
and stops. Only 7 nodes touched, not the 4 separate root-to-leaf walks a point-update segment tree
would need — and the root sum is now 79, exactly 39 + 4 × 10.
A later query answers the same three-way question, but instead of applying a change it accumulates
a sum, and it must push down before descending into any node with a pending tag rather than only when
told to update — a query has to see accurate values too. The default Range Sum over [1, 5]
after that update reaches node 9 (leaf, index 1, value 2), then node 5 — fully inside
[1,5] — which returns its own stored sum 29 directly, tag and all,
with no push-down needed at all: a fully-covered node's own stored value is already correct, only its
children are the ones left stale. Then node 6, also fully inside, returns 32 the same
way. Total: 2 + 29 + 32 = 63. Two of the query's three contributing nodes were still
carrying an un-pushed tag the whole time, and it never mattered — the tag only has to be pushed down
before something looks underneath the node that's holding it, and neither query here needed
to.
This is the recursive, top-down form the segment
tree page's own pitfalls note mentioned as the alternative to its iterative array trick — lazy
propagation needs explicit node ranges and a real push-down step before descending, which the flat
bottom-up array doesn't have a clean place for. Because this demo's 8-element input is already a
power of two, the same compact 2n-sized arrays and 2i/2i+1
child indexing work unchanged; a general-size input needs the same padding the segment tree page already covers:
class LazySegmentTreeSum {
constructor(values) {
let size = 1;
while (size < values.length) size *= 2;
this.n = size;
this.tree = new Array(2 * size).fill(0);
this.lazy = new Array(2 * size).fill(0);
this._build(1, 0, size - 1, values);
}
_build(node, l, r, values) {
if (l === r) { this.tree[node] = values[l] || 0; return; }
const mid = (l + r) >> 1;
this._build(2 * node, l, mid, values);
this._build(2 * node + 1, mid + 1, r, values);
this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
}
_pushDown(node, l, r) {
if (this.lazy[node] === 0) return;
const mid = (l + r) >> 1;
const lc = 2 * node, rc = 2 * node + 1;
this.tree[lc] += this.lazy[node] * (mid - l + 1);
this.lazy[lc] += this.lazy[node];
this.tree[rc] += this.lazy[node] * (r - mid);
this.lazy[rc] += this.lazy[node];
this.lazy[node] = 0;
}
rangeAdd(node, l, r, ql, qr, val) {
if (qr < l || r < ql) return;
if (ql <= l && r <= qr) {
this.tree[node] += val * (r - l + 1);
this.lazy[node] += val;
return;
}
this._pushDown(node, l, r);
const mid = (l + r) >> 1;
this.rangeAdd(2 * node, l, mid, ql, qr, val);
this.rangeAdd(2 * node + 1, mid + 1, r, ql, qr, val);
this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
}
rangeSum(node, l, r, ql, qr) {
if (qr < l || r < ql) return 0;
if (ql <= l && r <= qr) return this.tree[node];
this._pushDown(node, l, r);
const mid = (l + r) >> 1;
return this.rangeSum(2 * node, l, mid, ql, qr)
+ this.rangeSum(2 * node + 1, mid + 1, r, ql, qr);
}
}Skip the push-down and a query into a tagged node silently reads stale data.
After the default Range Add (+10 over [2, 5]), nodes 5 and 6 are each
holding a pending tag that was never pushed to their leaves — index 3 (leaf node 11, under node 5)
and index 4 (leaf node 12, under node 6) are still physically storing their old values,
1 and 9, even though the tree's aggregate sums are already correct. Query
Range Sum [3, 4]: this range only partially overlaps both node 5 and node 6, so a
correct query must push both tags down first before it can descend — giving tree[11] = 11,
tree[12] = 19, and a correct total of 30 (checked: 1+10=11,
9+10=19, matches the naive recomputation from scratch). Dropping the push-down step
before recursing into a partially-overlapped node — an easy edit to get away with for a while, since
most queries land on already-fully-covered or already-fully-pushed nodes without ever exposing it —
makes this same query read the stale leaves directly: 1 + 9 = 10, three times too small
and eleven off from the second query defaults above, no crash, no error, just silently wrong by
exactly the un-applied tag's contribution.
Forgetting to scale a pending tag by how many elements it covers. When a node
fully absorbs a range update, the update has to land on every element the node represents,
not just once — tree[node] += val × (r - l + 1), not tree[node] += val.
Nodes 5 and 6 above each cover 2 elements, so the correct absorption adds 10 × 2 = 20 to
each, for a correct root sum of 79 (39 + 4 × 10). Add val
alone instead of val × length and each of those two nodes under-adds by exactly
10 — a root sum of 59, twenty short, growing worse the larger the
fully-covered nodes a given update happens to land on. This is specific to sum (and
any other size-sensitive aggregate, like average or count) — a min-tracking node's pending tag needs no length factor
at all, since adding a constant to every element in a range shifts that range's minimum by the exact
same constant regardless of how many elements are in it. The same lazy-propagation mechanism, applied
to a different combining operation, needs a different rule for what "apply the tag" even means.
Time: O(log n) for both rangeAdd and
rangeSum — the same argument as the plain
segment tree's point update and range query: a range decomposes into at most
O(log n) fully-covered nodes, reached via at most O(log n) partially-covered
nodes on the way down, and each visited node does O(1) work (including the push-down
check) rather than recursing further once it's fully covered or fully outside. Building from an
existing array is O(n), same as the plain segment tree.
Space: O(n), but doubled over the plain segment tree — a
lazy array the same size as tree, tracking one pending value per node
instead of zero.
This site's guide, Choosing a Range Query Structure, compares this entry against the other five Array-Backed Trees structures that answer the same kind of question side by side.