Segment Tree with Lazy Propagation

Quick Revisit: Point-update segment trees break down when the problem wants to update an entire range in one shot. Lazy propagation defers those updates: each node carries a pending "tag," and we only push it down when we actually need to recurse into a child. Both range update and range query stay $O(\log n)$. The classic trap: forgetting to push() before touching children—stale tags give wrong answers silently. (Practice problems)

Difficulty: CF 1700–2100 · Prerequisites: Segment Tree

---

Why This Exists

A plain segment tree is fine when the update touches one point. It starts to crack when the update itself becomes a range, because "touch every affected leaf" quickly turns into a full traversal.

You have an array of 8 elements and must support two operations:

1. Range update: add $X$ to every element in $[l,r]$.
2. Range query: return the sum of elements in $[l,r]$.

With a plain segment tree you can query in $O(\log n)$, but an update to $[l,r]$ decomposes into up to $n$ point updates, each costing $O(\log n)$.

Count the cost on a concrete workload—$n=8$, array [2, 1, 5, 3, 7, 4, 6, 8]:

  Operation                    Naive cost         Running total
  ---------------------------------------------------------------
  add +10 to [0..7]            8 point updates     8
  query sum  [2..5]            1 query              9
  add +3  to [1..4]            4 point updates     13
  query sum  [0..3]            1 query             14
  add +7  to [0..7]            8 point updates     22
  query sum  [6..7]            1 query             23
  ---------------------------------------------------------------
  Total element-level touches: 23

Three range updates already cost 20 element-level touches. With $q={10}^5$ operations on $n={10}^5$ elements, the worst case is $O(nq)={10}^{10}$—far too slow. We need a way to "stamp" an entire range in one shot without visiting every leaf.

The Manager's Memo

The fix is to stop pushing updates down until we actually need the answer: store a pending tag at each node and propagate only on demand. Think of a department manager who receives a company-wide memo saying everyone gets a $10 raise. The manager does not walk to every employee's desk immediately. Instead, she pins the memo to her office door. Only when someone asks "what is Alice's salary?" does the manager open the relevant sub-folder and apply the memo—and even then, only to the sub-folder she actually opens.

This is lazy propagation (also called deferred propagation). Each internal node carries a lazy tag: a pending operation that has already been reflected in this node's value but has not been forwarded to the children yet. Before we recurse into a child for an update or a query, we push the tag down one level.

Where the analogy breaks: the manager only has two direct reports (left child, right child), and the memo must be a simple composable operation such as add, assign, or flip. If the pending operation cannot be composed cheaply—for example, "sort the sub-array"—lazy propagation does not apply.

Walkthrough

Array of 8 elements, all zeros: [0, 0, 0, 0, 0, 0, 0, 0]. Range-sum tree.

Step 1—Initial tree (no lazy tags).

                         [0..7]=0
                       /          \
               [0..3]=0            [4..7]=0
              /        \          /        \
         [0..1]=0  [2..3]=0  [4..5]=0  [6..7]=0
         /    \    /    \    /    \    /    \
       [0]=0 [1]=0 [2]=0 [3]=0 [4]=0 [5]=0 [6]=0 [7]=0

Operations touched: 0.

Step 2—Range update: add +5 to $[0..7]$.

Node $[0..7]$ fully covers $[0..7]$. Tag it and stop. No recursion needed.

                         [0..7]=40         <-- sum += 5 * 8
                         lazy=+5
                       /          \
               [0..3]=0            [4..7]=0    <-- untouched
              /        \          /        \
         [0..1]=0  [2..3]=0  [4..5]=0  [6..7]=0
         /    \    /    \    /    \    /    \
       [0]=0 [1]=0 [2]=0 [3]=0 [4]=0 [5]=0 [6]=0 [7]=0

Nodes visited: 1 (the root). Compare naive: 8.

Step 3—Range update: add +3 to $[2..5]$.

$[2..5]$ partially overlaps root $[0..7]$, so we must recurse. First, push the root's lazy tag (+5) down to its children:

  push(root):
    [0..3].sum += 5 * 4 = 20,  [0..3].lazy = +5
    [4..7].sum += 5 * 4 = 20,  [4..7].lazy = +5
    [0..7].lazy = 0   (cleared)

Now recurse left into $[0..3]$ with update $[2..5]$. Partial overlap again, so push $[0..3]$'s lazy (+5) to its children, then recurse:

  push([0..3]):
    [0..1].sum += 5 * 2 = 10,  [0..1].lazy = +5
    [2..3].sum += 5 * 2 = 10,  [2..3].lazy = +5
    [0..3].lazy = 0

$[2..3]$ is fully inside $[2..5]$: tag it with +3 and stop. $[0..1]$ is fully outside $[2..5]$: skip.

Recurse right into $[4..7]$. Push its lazy (+5) to children:

  push([4..7]):
    [4..5].sum += 5 * 2 = 10,  [4..5].lazy = +5
    [6..7].sum += 5 * 2 = 10,  [6..7].lazy = +5
    [4..7].lazy = 0

$[4..5]$ is fully inside $[2..5]$: tag it with +3 and stop. $[6..7]$ is fully outside $[2..5]$: skip.

Recalculate parents on the way up:

                         [0..7]=52
                       /          \
               [0..3]=26           [4..7]=26
              /        \          /        \
         [0..1]=10 [2..3]=16 [4..5]=16 [6..7]=10
         lazy=+5   lazy=+8   lazy=+8   lazy=+5
         /    \    /    \    /    \    /    \
       [0]=0 [1]=0 [2]=0 [3]=0 [4]=0 [5]=0 [6]=0 [7]=0

Nodes visited: 7. Compare naive: 4 point updates × $O(\log 8)=12$.

Step 4—Range query: sum of $[4..7]$.

$[4..7]$ exactly matches node $[4..7]$. Its value already accounts for all lazy above (those were pushed in Step 3). Return 26 immediately.

  query([4..7]) = 26.  Nodes visited: 3 (root, right child, match).

No pushdown needed because we hit a full-cover node before touching children.

Step 5—Range query: sum of $[1..2]$.

Path: root → $[0..3]$ (partial) → push is not needed (lazy is 0) → recurse into $[0..1]$ (partial, push lazy +5 to leaves):

  push([0..1]):
    [0].sum = 5,  [1].sum = 5,  [0..1].lazy = 0

  [1] = 5  (inside [1..2])

Recurse into $[2..3]$ (partial, push lazy +8 to leaves):

  push([2..3]):
    [2].sum = 8,  [3].sum = 8,  [2..3].lazy = 0

  [2] = 8  (inside [1..2])

Answer: $5+8=13$. Nodes visited: 7.

Operation tally (lazy vs. naive):

  Operation                Lazy nodes visited   Naive touches
  -----------------------------------------------------------
  add +5  to [0..7]                1                  8
  add +3  to [2..5]                7                 12
  query sum  [4..7]                3                  4
  query sum  [1..2]                7                  2
  -----------------------------------------------------------
  Total:                          18                 26

The gap widens dramatically with larger $n$: every operation stays $O(\log n)$.

The Lazy Invariant

+------------------------------------------------------------------+
|  LAZY INVARIANT                                                  |
|                                                                  |
|  t[v] is the CORRECT aggregate for node v's range, assuming      |
|  all lazy tags ABOVE v have already been pushed down to v.       |
|                                                                  |
|  Equivalently: t[v] already reflects lz[v], but lz[v] has NOT   |
|  yet been applied to v's children.                               |
|                                                                  |
|  push(v) restores the invariant for v's children by:             |
|    1. Applying lz[v] to each child's value and lazy tag.         |
|    2. Clearing lz[v] to zero.                                    |
+------------------------------------------------------------------+

Connect this back to the walkthrough: in Step 2, after tagging the root with +5, $t[\text{root}]=40$ is correct (it reflects the +5). But $t[0..3]$ is still 0—the invariant says that is fine because the lazy tag above it (at root) has not been pushed yet. In Step 3, the moment we need to recurse into $[0..3]$, we push first, making $t[0..3]=20$ correct before we touch its children.

Every call to push(v) is a local repair: it makes the children correct without needing to visit the rest of the tree. That locality is what keeps each operation $O(\log n)$.

Under the Hood

The real question is: what does the lazy tag mean for the node?

The vague mental model says "it's the update I haven't done yet," which leaves you wondering when to apply it and to what. The sharp mental model is that the lazy tag is a transformation waiting to be applied to this node's children; the node itself already reflects it.

    State of node v with tag T:
    +---------------------+
    | t[v] = CORRECT      |  <-- already incorporates T
    | lazy[v] = T         |  <-- pending for children only
    +---------------------+
         /          \
    +---------+  +---------+
    | t[2v]   |  | t[2v+1] |  <-- do NOT yet reflect T
    | (stale) |  | (stale) |
    +---------+  +---------+

    Before accessing children --> call pushdown(v)

The push-down function is the hardest part and the part most templates hide. For range-add it's t[child] += tag * len_child; lazy[child] += tag. For range-set it's lazy[child] = tag (replace, not add). When you mix operations such as add + set, tag composition becomes algebraic—write the formula as math before coding.

The mental leap is that deferred work is still correct. A node's subtree can be in a pending state where updates have not reached the leaves, yet queries still return correct answers because the node's value is already updated. If this makes you nervous, you do not trust the invariant yet.

    Why deferred work is safe:

    Query [0..7]?  Just read root --> already correct
    Query [0..3]?  Push root, read left child --> now correct
    Query [2..3]?  Push root, push left child --> now correct

    You only push along the PATH you need.
    Untouched subtrees stay lazy --> O(log n) per operation.

Reach for this when you see "add $v$ to all elements in $[l,r]$, then query the sum/min/max of $[l,r]$" (range add + range query), "set all elements in $[l,r]$ to $x$" (range assign), "flip all bits in $[l,r]$" (XOR tag), or any HLD setup that needs "update a path, query a subtree." Don't reach for it when only one side is a range: point update + range query is just a plain segment tree, and range update + point query is a difference array on a Fenwick tree. A static array with range queries only wants a prefix-sum array or sparse table. And operations that don't compose cheaply (e.g., "sort the sub-array") cannot be stored as a simple tag at all—sqrt decomposition or heavier machinery is required.

How This Evolved

The story of range queries is a sequence of tools, each created to fix the limitation of the previous one. It starts with prefix sums: precompute cumulative totals and answer any range sum in $O(1)$. That is perfect for static arrays, but a single point update forces an $O(n)$ rebuild. The Binary Indexed Tree (Fenwick tree) fixes that by supporting point updates and prefix queries in $O(\log n)$, though it still only speaks prefix-style arithmetic.

The segment tree generalizes the idea: build a complete binary tree over the array where each node stores the aggregate for its range. Now any associative query—sum, min, max, GCD—and point updates both run in $O(\log n)$. But range updates still decompose into too many leaf changes. Lazy propagation closes that gap by deferring the update: stamp a pending tag on fully covered nodes and push it down only when necessary, keeping both range updates and range queries at $O(\log n)$.

The evolution does not stop there. Persistent segment trees add the ability to keep every historical version of the tree, enabling queries on past states without extra space blowup because each update creates only $O(\log n)$ new nodes. From prefix sums to persistence, each step trades a bit more implementation complexity for a strictly larger class of solvable problems, and knowing the chain helps you choose the simplest tool that actually fits.

---

C++ STL Reference

No STL containers apply—segment tree with lazy propagation is a manual data structure. Useful STL bits:

Utility	Header	Usage
fill(begin, end, val)	<algorithm>	Initialize arrays
__lg(n)	GCC built-in	Floor of ${\log }_{2}n$, handy for tree height

---

Implementation

+------------------------------------------------------------+
| INVARIANT: Before reading or modifying ANY node's children,|
| push down that node's lazy tag first. Every query() and    |
| update() call must push() before recursing into children.  |
| Forgetting this is the #1 lazy propagation bug.            |
+------------------------------------------------------------+

Minimal template (range add + range sum).

#include <bits/stdc++.h>
using namespace std;

struct LazySegTree {
    int n;
    vector<long long> t, lz;

    LazySegTree(int n) : n(n), t(4 * n), lz(4 * n) {}

    void build(vector<int>& a, int v, int tl, int tr) {
        if (tl == tr) { t[v] = a[tl]; return; }
        int tm = (tl + tr) / 2;
        build(a, 2*v, tl, tm);
        build(a, 2*v+1, tm+1, tr);
        t[v] = t[2*v] + t[2*v+1];
    }

    void push(int v, int tl, int tr) {
        if (lz[v]) {
            int tm = (tl + tr) / 2;
            apply(2*v, tl, tm, lz[v]);
            apply(2*v+1, tm+1, tr, lz[v]);
            lz[v] = 0;
        }
    }

    void apply(int v, int tl, int tr, long long val) {
        t[v] += val * (tr - tl + 1);
        lz[v] += val;
    }

    void update(int v, int tl, int tr, int l, int r, long long val) {
        if (l > tr || r < tl) return;
        if (l <= tl && tr <= r) { apply(v, tl, tr, val); return; }
        push(v, tl, tr);
        int tm = (tl + tr) / 2;
        update(2*v, tl, tm, l, r, val);
        update(2*v+1, tm+1, tr, l, r, val);
        t[v] = t[2*v] + t[2*v+1];
    }

    long long query(int v, int tl, int tr, int l, int r) {
        if (l > tr || r < tl) return 0;
        if (l <= tl && tr <= r) return t[v];
        push(v, tl, tr);
        int tm = (tl + tr) / 2;
        return query(2*v, tl, tm, l, r) + query(2*v+1, tm+1, tr, l, r);
    }

    void build(vector<int>& a) { build(a, 1, 0, n-1); }
    void update(int l, int r, long long val) { update(1, 0, n-1, l, r, val); }
    long long query(int l, int r) { return query(1, 0, n-1, l, r); }
};

int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    vector<int> a(n);
    for (auto& x : a) scanf("%d", &x);

    LazySegTree seg(n);
    seg.build(a);

    while (q--) {
        int type; scanf("%d", &type);
        if (type == 1) {
            int l, r; long long v;
            scanf("%d%d%lld", &l, &r, &v);
            seg.update(l - 1, r - 1, v);
        } else {
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%lld\n", seg.query(l - 1, r - 1));
        }
    }
}

Explained version (range add + range sum).

#include <bits/stdc++.h>
using namespace std;

struct LazySegTree {
    int n;
    vector<long long> t, lz;
    // t[v]  = correct aggregate for node v's range (includes all pending lazy above it)
    // lz[v] = pending add that has NOT yet been pushed to v's children

    LazySegTree(int n) : n(n), t(4 * n, 0), lz(4 * n, 0) {}

    void build(vector<int>& a, int v, int tl, int tr) {
        if (tl == tr) {
            t[v] = a[tl];
            return;
        }
        int tm = (tl + tr) / 2;
        build(a, 2*v, tl, tm);
        build(a, 2*v+1, tm+1, tr);
        t[v] = t[2*v] + t[2*v+1];
    }

    // apply a pending value to node v which covers [tl..tr].
    // Key invariant: after apply(), t[v] is correct for its range.
    // The lazy is accumulated (+=) because "add" composes by addition.
    void apply(int v, int tl, int tr, long long val) {
        t[v] += val * (tr - tl + 1);  // each of (tr-tl+1) elements gets +val
        lz[v] += val;                  // remember to pass this to children later
    }

    // Push pending lazy from v down to its two children.
    // MUST be called before accessing children in update() or query().
    // Without this, children would return stale answers.
    void push(int v, int tl, int tr) {
        if (lz[v] != 0) {
            int tm = (tl + tr) / 2;
            apply(2*v,   tl,   tm, lz[v]);
            apply(2*v+1, tm+1, tr, lz[v]);
            lz[v] = 0;  // v's obligation is now transferred to children
        }
    }

    // Add val to every element in [l..r].
    void update(int v, int tl, int tr, int l, int r, long long val) {
        if (l > tr || r < tl) return;          // no overlap
        if (l <= tl && tr <= r) {              // full overlap: stop here, set lazy
            apply(v, tl, tr, val);
            return;
        }
        // partial overlap: must go deeper
        push(v, tl, tr);                       // <--- push BEFORE recursing!
        int tm = (tl + tr) / 2;
        update(2*v,   tl,   tm, l, r, val);
        update(2*v+1, tm+1, tr, l, r, val);
        t[v] = t[2*v] + t[2*v+1];             // recalc from children
    }

    // Query sum of [l..r].
    long long query(int v, int tl, int tr, int l, int r) {
        if (l > tr || r < tl) return 0;        // no overlap: identity for sum
        if (l <= tl && tr <= r) return t[v];   // full overlap
        push(v, tl, tr);                       // <--- push BEFORE recursing!
        int tm = (tl + tr) / 2;
        return query(2*v, tl, tm, l, r)
             + query(2*v+1, tm+1, tr, l, r);
    }

    // Convenience wrappers (0-indexed)
    void build(vector<int>& a) { build(a, 1, 0, n - 1); }
    void update(int l, int r, long long val) { update(1, 0, n - 1, l, r, val); }
    long long query(int l, int r) { return query(1, 0, n - 1, l, r); }
};

int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    vector<int> a(n);
    for (auto& x : a) scanf("%d", &x);

    LazySegTree seg(n);
    seg.build(a);

    while (q--) {
        int type;
        scanf("%d", &type);
        if (type == 1) {
            int l, r;
            long long v;
            scanf("%d%d%lld", &l, &r, &v);
            seg.update(l - 1, r - 1, v);  // convert 1-indexed input to 0-indexed
        } else {
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%lld\n", seg.query(l - 1, r - 1));
        }
    }
}

---

ASCII Diagram: Lazy Propagation — Range Update and Pushdown

Initial tree (sum, array [1,1,1,1,1,1,1,1]):

                         [0,7]=8  lz=0
                        /          \
                 [0,3]=4 lz=0        [4,7]=4 lz=0
                /       \            /        \
          [0,1]=2      [2,3]=2   [4,5]=2    [6,7]=2
          lz=0          lz=0      lz=0       lz=0

STEP 1: Range update -- add +5 to [2, 5]
  Descend to cover [2,5].  Nodes [2,3] and [4,5] are fully covered.
  Mark lazy instead of going deeper:

                         [0,7]=28 lz=0       <- updated sum (+20)
                        /          \
                 [0,3]=14 lz=0       [4,7]=14 lz=0
                /       \            /        \
          [0,1]=2      [2,3]=12  [4,5]=12   [6,7]=2
          lz=0          lz=+5     lz=+5      lz=0
                       ↑ LAZY    ↑ LAZY
  Children of [2,3] and [4,5] are NOT updated yet!

STEP 2: Query sum [3, 4] -- triggers pushdown
  Descend into [0,3]: need child [2,3], which has lz=+5.

  PUSHDOWN [2,3] -> children:
    [2]=1+5=6 lz=+5,  [3]=1+5=6 lz=+5,  then [2,3].lz=0

  Descend into [4,7]: need child [4,5], which has lz=+5.

  PUSHDOWN [4,5] -> children:
    [4]=1+5=6 lz=+5,  [5]=1+5=6 lz=+5,  then [4,5].lz=0

  Answer: [3]+[4] = 6+6 = 12

  After pushdown:
                         [0,7]=28 lz=0
                        /          \
                [0,3]=14 lz=0       [4,7]=14 lz=0
                /       \            /        \
          [0,1]=2      [2,3]=12  [4,5]=12   [6,7]=2
          lz=0          lz=0      lz=0       lz=0
           / \          / \        / \        / \
         1   1        6   6      6   6      1   1
                     lz=0       lz=0

Key insight: lazy values are only pushed down when a query or update
needs to access children. This keeps range updates O(log n).

Pre-Code Sanity Check

Before you start typing: can you compose two pending lazy tags into one? (add+add = add; set then add = needs two tags composed algebraically.) Does every update() and query() call push(node) before recursing into children? Does your "no pending update" sentinel conflict with a valid update value? Did you build() the tree before the first operation? Is your array sized $4n$, not $2n$?

The whole thing sits on one line: don't deliver the mail until someone opens the mailbox.

---

Operations Reference

All operations stay logarithmic thanks to lazy deferral—here are the exact costs.

Operation	Time	Space
Build	$O(n)$	$O(n)$
Range update (add/assign)	$O(\log n)$	—
Range query (sum/min/max)	$O(\log n)$	—
Point query	$O(\log n)$	—
Total space	—	$O(4n)$

All complexities are worst-case per operation. The constant factor is roughly $2\times$ a plain segment tree due to the push-down step. fill() and __lg() from <algorithm> are the only STL bits you'll reach for—everything else is manual.

Problem Patterns

The most common lazy segment-tree pattern: add $v$ to all elements in $[l,r]$, query sum of $[l,r]$.

Lazy composition: lz[v] += val. Node value: t[v] += val * len.

Problems: CF 52C—Circular RMQ, CSES—Range Update Queries

Range Assign + Range Query

"Set all elements in $[l,r]$ to $x$." The lazy tag overwrites rather than accumulates. Use a sentinel (e.g., LLONG_MIN) to denote "no pending assign."

Key difference from add: apply sets lz[v] = val (not +=), and t[v] = val * len for sum.

void apply(int v, int tl, int tr, long long val) {
    t[v] = val * (tr - tl + 1);
    lz[v] = val;  // overwrite, not accumulate
}

Problems: CF 580E—Kefa and Watch, CF 292E—Copying Data

Range Add + Range Min/Max

Lazy add, but the aggregate is min/max instead of sum. Apply changes t[v] += val (min/max shifts uniformly). Composition is still lz[v] += val.

void apply(int v, int tl, int tr, long long val) {
    t[v] += val;   // min shifts by val
    lz[v] += val;
}
// query returns min, identity = LLONG_MAX

Problems: CF 52C—Circular RMQ, CF 1114F—Please, another Queries on Array?

Combined Assign + Add (Two Lazy Tags)

Some problems need both "assign range to $x$" and "add $v$ to range." You need two lazy fields. Order matters: an assign wipes out any pending add.

struct Node {
    long long sum;
    long long lz_assign;  // LLONG_MIN = no pending assign
    long long lz_add;
};
// When pushing: if assign is pending, apply assign first, then add.
// When a new assign arrives, it clears lz_add.

Problems: CF 145E—Lucky Queries, CF 877E—Danil and a Part-time Job

Range Flip (XOR Toggle)

"Flip all bits in $[l,r]$." Lazy tag is a boolean (0 or 1). Two flips cancel: lz[v] ^= 1. For sum queries: t[v] = len - t[v] on flip.

void apply(int v, int tl, int tr, int flip) {
    if (flip) {
        t[v] = (tr - tl + 1) - t[v];
        lz[v] ^= 1;
    }
}

Problems: CF 877E—Danil and a Part-time Job, CF 242E—XOR on Segment

Lazy on Tree (HLD + Lazy Segment Tree)

Heavy-Light Decomposition maps tree paths to contiguous array segments. Pair with a lazy segment tree for "add $v$ to path $u\to v$" + "query sum of subtree."

Build the segment tree on the HLD-order array. Each path query becomes $O({\log }^{2}n)$.

Problems: CF 343D—Water Tree, CF 838B—Prefix Sum Primes

Coordinate Compression + Lazy Segment Tree

When the range is huge ($[1,{10}^9]$) but only $O(n)$ distinct points matter, compress coordinates first, then use a lazy segment tree on the compressed array. Alternative: use a dynamic (pointer-based) segment tree.

Problems: CF 915E—Physical Education Lessons

Gotchas & Debugging

Forgetting to Push Before Recursing

The #1 bug. Both update() and query() must call push() before touching children. Symptoms: correct on small tests, wrong on larger ones.

If you query a range without pushing lazy tags down, you read stale values. The fix is mechanical: at the start of both query() and update(), before the if (l <= mid) / if (r > mid) branching, call push(node). Always.

Not Recalculating the Parent After Recursion

After update() recurses into children, you must do t[v] = t[2*v] + t[2*v+1] (or whatever your merge is). Forgetting this means the parent holds a stale value.

Wrong Lazy Composition for Assign

For range-assign, a new assign overwrites the old lazy (does not add to it). If you also have an add lazy, the assign must clear it:

// Wrong:  lz[v] += val;
// Right:  lz[v] = val; lz_add[v] = 0;

Identity element mismatch.

• Sum query identity: 0
• Min query identity: LLONG_MAX (or INF)
• Max query identity: LLONG_MIN (or -INF)

Using 0 as identity for min queries silently returns wrong answers.

Integer overflow. Range sum with $n={10}^5$ elements each up to ${10}^9$, after ${10}^5$ add operations of ${10}^9$ each: values reach $\sim {10}^{14}$. Use long long for both t[] and lz[].

Off-by-one on push for leaves. push() should only propagate to children when tl < tr (non-leaf). The implementations above handle this implicitly because leaves never recurse. But if you call push() on a leaf in a different style, you'll write to out-of-bounds array indices (2*v, 2*v+1 for a leaf node).

Array size must be $4n$ (not $2n$) for the recursive implementation. Undersized arrays give runtime errors on edge cases.

Pushing unconditionally. Only push when lazy != neutral, otherwise you waste a logarithmic constant factor and risk TLE.

Debugging tip—brute-force checker. Write an $O(n\cdot q)$ brute force and stress-test:

// In the same file, alongside your seg tree:
struct Brute {
    vector<long long> a;
    Brute(vector<int>& v) : a(v.begin(), v.end()) {}
    void update(int l, int r, long long val) {
        for (int i = l; i <= r; i++) a[i] += val;
    }
    long long query(int l, int r) {
        long long s = 0;
        for (int i = l; i <= r; i++) s += a[i];
        return s;
    }
};
// Stress: random ops, compare seg.query() vs brute.query()

Trap—"I can just add lazy tags to any segment tree." Lazy propagation works only when updates compose: applying update A then update B must be expressible as a single update C. Ask yourself: "if two updates hit the same node before a push, can I merge them into one tag?"

    Composable:
      add(3) then add(5) = add(8)             OK
      set(3) then set(5) = set(5)             OK
      add(3) then set(5) = set(5)             OK (set overwrites)
      set(3) then add(5) = set(3), then add 5 NEEDS TWO TAGS

    NOT composable (simply):
      "sort the range"    --> no tag representation
      "add x, then GCD"  --> combined effect not a simple tag

Trap—"The lazy tag and node value are independent."

They are NOT. When you set a lazy tag, you MUST also update the node's stored value immediately—queries may read the node without descending.

    WRONG (node stale):         CORRECT (node updated):

    +----------+                +----------+
    | t[v]=10  |  lazy=+5      | t[v]=30  |  lazy=+5
    | (STALE!) |  (pending)    | (correct)|  (pending for children)
    +----------+                +----------+

    Query on [tl..tr] reads t[v] directly.
    If t[v] is stale, the query returns garbage.

Trap—"Range update + point query needs full lazy." It doesn't. For range update + point query only, use a Fenwick tree on a difference array—simpler and faster. Full lazy is needed only for range update + range query.

A real story. Sam implemented a range-add, range-sum lazy segment tree. The query function dutifully called push(node) before recursing. But the update function didn't—after all, "I'm just writing, not reading." Samples passed (they were small). On the first large test: WA. The reason: when update recurses into the left child without pushing, the left child still carries a stale lazy tag from a previous update. The new update overwrites that tag instead of composing with it (because the old tag was never pushed down). The fix was a single line—push(node) at the top of update—but it took 45 minutes and two penalty attempts to find. Rule of thumb: if you recurse into children, you push first. No exceptions. Not in query, not in update.

Pushdown missing the length multiplier. A classic bug in push:

void push(int node, int lo, int hi) {
    if (lazy[node] != 0) {
        int mid = (lo + hi) / 2;
        tree[2*node] += lazy[node];          // ← bug
        tree[2*node+1] += lazy[node];        // ← bug
        lazy[2*node] += lazy[node];
        lazy[2*node+1] += lazy[node];
        lazy[node] = 0;
    }
}

When Your Solution Is Wrong

• WA (Wrong Answer):
  • Pushdown order wrong—must push lazy to children before recursing into them
  • Lazy values not composed correctly (e.g., "add then set" vs. "set then add"—the order of operations matters when combining multiple pending updates)
  • Forgetting to pushdown in the query function (not just update)
• TLE (Time Limit Exceeded):
  • Pushing down at every node unconditionally instead of only when lazy != neutral
  • Not returning early when the current range is fully inside the update range
• RE: Array size must be $4n$ (not $2n$) for recursive implementation.

Spot the Bug

Bug 1—Missing push in update:

void update(int node, int lo, int hi, int l, int r, long long val) {
    if (r < lo || hi < l) return;
    if (l <= lo && hi <= r) { tree[node] += val * (hi - lo + 1); lazy[node] += val; return; }
    // push(node, lo, hi);  <- missing!
    int mid = (lo + hi) / 2;
    update(2*node, lo, mid, l, r, val);
    update(2*node+1, mid+1, hi, l, r, val);
    tree[node] = tree[2*node] + tree[2*node+1];
}

Fix

Without push(node), children carry stale tags from prior updates. New tags compose incorrectly. Uncomment push(node, lo, hi); before recursing.

Bug 2—Wrong tag application (forgot ×len):

void push(int node, int lo, int hi) {
    if (lazy[node] != 0) {
        int mid = (lo + hi) / 2;
        tree[2*node] += lazy[node];      // should be lazy[node] * (mid - lo + 1)
        tree[2*node+1] += lazy[node];    // should be lazy[node] * (hi - mid)
        lazy[2*node] += lazy[node];
        lazy[2*node+1] += lazy[node];
        lazy[node] = 0;
    }
}

Fix

The child's sum must increase by v × len, not just v.

Bug 3—Set-lazy identity conflict:

if (lazy[node] != 0) {  // sentinel is 0, but 0 is a valid set-value!

Fix

After "set range to 0", push sees lazy == 0 and skips. Use a separate has_lazy flag or a sentinel that can't be a valid value.

Can You...

Before moving on: write pushdown() for range-add lazy from memory—updating the child values, propagating tags, and clearing the parent tag. State the invariant in your own words (the node value already reflects all pending updates; the lazy tag is pending for children only). Name two operations that compose cleanly as lazy tags and one that does not. Point to the two places in query() and update() where pushdown() must be called. Write the formula for how the stored aggregate changes under a range add: t[v] += x * len. Explain why range update + point query does not need lazy propagation at all. And if you want to actually verify correctness, implement a brute-force checker and stress-test your implementation.

---

Practice Problems

#	Problem	Source	Difficulty	Key Idea
1	Range Update Queries	CSES	Easy	Range add + point query (warm-up)
2	Range Updates and Sums	CSES	Medium	Range add + range assign + range sum
3	Circular RMQ	CF 52C	Medium	Range add + range min, circular array
4	Copying Data	CF 292E	Medium	Range assign variant
5	Danil and a Part-time Job	CF 877E	Medium	Flip (XOR) on tree + seg tree
6	Kefa and Watch	CF 580E	Medium-Hard	Range assign + hash queries
7	XOR on Segment	CF 242E	Medium-Hard	Bitwise XOR range update, per-bit seg trees
8	Water Tree	CF 343D	Hard	Euler tour + range assign on tree
9	Physical Education Lessons	CF 915E	Hard	Coordinate compression + range operations
10	Sereja and Brackets	CF 380C	Hard	Merge non-trivial node info (bracket sequences)

Further Reading

• cp-algorithms: Segment Tree—includes lazy propagation section.
• Codeforces Blog: Efficient and Easy Segment Trees (Al.Cash)—iterative approach.
• Codeforces Blog: Segment Tree Beats—advanced extension for "update $a_i=min(a_i,v)$" range operations.
• Sparse Table for static RMQ: see Sparse Table & RMQ.
• Fenwick tree (simpler, less general): see Binary Indexed Tree (Fenwick).

---

Next Up: Cartesian Tree (Treap)—when you need structural mutations (split, merge, insert, reverse) alongside range queries.