Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Lazy Propagation
DSA

Lazy Propagation

Understand lazy propagation for efficiently handling range updates and range queries.

Lazy propagation defers range-update work: a node stores a pending tag saying “everything below me still needs this delta applied”.

Why it matters:

Without lazy, adding to [l..r] touches every leaf — O(n). With lazy, you stop at the first fully covered node: O(log n).

The contract:

A node with an unresolved tag still reports correct aggregates — children are only fixed when someone actually descends into them.

Core Template (Range Add + Range Sum)

Watch add(+10, [0..1]) stop at one node with a tag, then watch sum([0..3]) push the tag down only when needed. Press ▶ to animate.

Segment Tree with Lazy Propagation

Range add and range sum in O(log n) using deferred lazy tags.

An update stops at the first fully-covered node and stores its delta as a lazy tag instead of touching every leaf. The tag is pushed to children only when a query or update actually needs those values. Each tag is applied once per level, so both operations stay O(log n).

SEGMENT TREE VISUALIZER
Steps –
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        update: stop at the first fully covered node — store delta as a lazy tag
                      
                        2
                        query:  if a node holds a pending tag → push it down to children first
                      
                        3
                                then combine answers from children
                      
                        4
                        each tag is applied once per level → O(log n) per operation
                      
class LazySegTree {
    int n;
    long[] tree, lazy;

    public LazySegTree(int[] arr) {
        n = arr.length;
        tree = new long[4 * n];
        lazy = new long[4 * n];
        build(arr, 1, 0, n - 1);
    }

    private void build(int[] arr, int node, int lo, int hi) {
        if (lo == hi) { tree[node] = arr[lo]; return; }
        int mid = (lo + hi) / 2;
        build(arr, node * 2, lo, mid);
        build(arr, node * 2 + 1, mid + 1, hi);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }

    private void apply(int node, int lo, int hi, long d) {
        tree[node] += d * (hi - lo + 1);
        lazy[node] += d;
    }

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

    public void add(int l, int r, long d) {
        update(1, 0, n - 1, l, r, d);
    }

    private void update(int node, int lo, int hi, int l, int r, long d) {
        if (r < lo || hi < l) return;
        if (l <= lo && hi <= r) { apply(node, lo, hi, d); return; }

        push(node, lo, hi);
        int mid = (lo + hi) / 2;
        update(node * 2, lo, mid, l, r, d);
        update(node * 2 + 1, mid + 1, hi, l, r, d);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }

    public long sum(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }

    private long query(int node, int lo, int hi, int l, int r) {
        if (r < lo || hi < l) return 0;
        if (l <= lo && hi <= r) return tree[node];

        push(node, lo, hi);
        int mid = (lo + hi) / 2;
        return query(node * 2, lo, mid, l, r)
             + query(node * 2 + 1, mid + 1, hi, l, r);
    }
}
class LazySegTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        self.lazy = [0] * (4 * self.n)
        self._build(arr, 1, 0, self.n - 1)

    def _build(self, arr, node, lo, hi):
        if lo == hi:
            self.tree[node] = arr[lo]
            return
        mid = (lo + hi) // 2
        self._build(arr, node * 2, lo, mid)
        self._build(arr, node * 2 + 1, mid + 1, hi)
        self.tree[node] = self.tree[node*2] + self.tree[node*2+1]

    def _apply(self, node, lo, hi, d):
        self.tree[node] += d * (hi - lo + 1)
        self.lazy[node] += d

    def _push(self, node, lo, hi):
        if self.lazy[node]:
            mid = (lo + hi) // 2
            self._apply(node * 2, lo, mid, self.lazy[node])
            self._apply(node * 2 + 1, mid + 1, hi, self.lazy[node])
            self.lazy[node] = 0

    def add(self, l, r, d):
        self._update(1, 0, self.n - 1, l, r, d)

    def _update(self, node, lo, hi, l, r, d):
        if r < lo or hi < l:
            return
        if l <= lo and hi <= r:
            self._apply(node, lo, hi, d)
            return

        self._push(node, lo, hi)
        mid = (lo + hi) // 2
        self._update(node * 2, lo, mid, l, r, d)
        self._update(node * 2 + 1, mid + 1, hi, l, r, d)
        self.tree[node] = self.tree[node*2] + self.tree[node*2+1]

    def sum(self, l, r):
        return self._query(1, 0, self.n - 1, l, r)

    def _query(self, node, lo, hi, l, r):
        if r < lo or hi < l:
            return 0
        if l <= lo and hi <= r:
            return self.tree[node]

        self._push(node, lo, hi)
        mid = (lo + hi) // 2
        return (self._query(node * 2, lo, mid, l, r)
                + self._query(node * 2 + 1, mid + 1, hi, l, r))
class LazySegTree {
    int n;
    vector<long long> tree, lz;

    void build(vector<int>& arr, int node, int lo, int hi) {
        if (lo == hi) { tree[node] = arr[lo]; return; }
        int mid = (lo + hi) / 2;
        build(arr, node * 2, lo, mid);
        build(arr, node * 2 + 1, mid + 1, hi);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }

    void apply(int node, int lo, int hi, long long d) {
        tree[node] += d * (hi - lo + 1);
        lz[node] += d;
    }

    void push(int node, int lo, int hi) {
        if (lz[node]) {
            int mid = (lo + hi) / 2;
            apply(node * 2, lo, mid, lz[node]);
            apply(node * 2 + 1, mid + 1, hi, lz[node]);
            lz[node] = 0;
        }
    }

    void update(int node, int lo, int hi, int l, int r, long long d) {
        if (r < lo || hi < l) return;
        if (l <= lo && hi <= r) { apply(node, lo, hi, d); return; }

        push(node, lo, hi);
        int mid = (lo + hi) / 2;
        update(node * 2, lo, mid, l, r, d);
        update(node * 2 + 1, mid + 1, hi, l, r, d);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }

    long long query(int node, int lo, int hi, int l, int r) {
        if (r < lo || hi < l) return 0;
        if (l <= lo && hi <= r) return tree[node];

        push(node, lo, hi);
        int mid = (lo + hi) / 2;
        return query(node * 2, lo, mid, l, r) +
               query(node * 2 + 1, mid + 1, hi, l, r);
    }

public:
    LazySegTree(vector<int>& arr)
        : n(arr.size()), tree(4 * arr.size()), lz(4 * arr.size()) {
        build(arr, 1, 0, n - 1);
    }

    void add(int l, int r, long long d) { update(1, 0, n - 1, l, r, d); }
    long long sum(int l, int r)         { return query(1, 0, n - 1, l, r); }
};
class LazySegTree {
  constructor(arr) {
    this.n = arr.length;
    this.tree = Array(4 * this.n).fill(0n);
    this.lazy = Array(4 * this.n).fill(0n);
    this.#build(arr.map(BigInt), 1, 0, this.n - 1);
  }

  #build(arr, node, lo, hi) {
    if (lo === hi) {
      this.tree[node] = arr[lo];
      return;
    }
    const mid = (lo + hi) >> 1;
    this.#build(arr, node * 2, lo, mid);
    this.#build(arr, node * 2 + 1, mid + 1, hi);
    this.tree[node] = this.tree[node * 2] + this.tree[node * 2 + 1];
  }

  #apply(node, segLen, d) {
    this.tree[node] += d * BigInt(segLen);
    this.lazy[node] += d;
  }

  #push(node, lo, hi) {
    if (this.lazy[node]) {
      const mid = (lo + hi) >> 1;
      this.#apply(node * 2, mid - lo + 1, this.lazy[node]);
      this.#apply(node * 2 + 1, hi - mid, this.lazy[node]);
      this.lazy[node] = 0n;
    }
  }

  add(l, r, d) {
    this.#update(1, 0, this.n - 1, l, r, BigInt(d));
  }

  #update(node, lo, hi, l, r, d) {
    if (r < lo || hi < l) return;
    if (l <= lo && hi <= r) {
      this.#apply(node, hi - lo + 1, d);
      return;
    }

    this.#push(node, lo, hi);
    const mid = (lo + hi) >> 1;
    this.#update(node * 2, lo, mid, l, r, d);
    this.#update(node * 2 + 1, mid + 1, hi, l, r, d);
    this.tree[node] = this.tree[node * 2] + this.tree[node * 2 + 1];
  }

  sum(l, r) {
    return Number(this.#query(1, 0, this.n - 1, l, r));
  }

  #query(node, lo, hi, l, r) {
    if (r < lo || hi < l) return 0n;
    if (l <= lo && hi <= r) return this.tree[node];

    this.#push(node, lo, hi);
    const mid = (lo + hi) >> 1;
    return (
      this.#query(node * 2, lo, mid, l, r) +
      this.#query(node * 2 + 1, mid + 1, hi, l, r)
    );
  }
}

apply + push are the only new pieces — everything else is the basic tree.

What Changed from the Basic Tree?

The tag pair

Added:

apply(node, lo, hi, d):  tree[node] += d*(hi-lo+1);  lazy[node] += d;
push(node, lo, hi):      hand tag to children, clear it
_apply(...):  self.tree[node] += d * seg_len;  self.lazy[node] += d
_push(...):   hand tag to children, clear it
apply(...):  tree[node] += d * segLen;  lz[node] += d;
push(...):   hand tag to children, clear it
#apply(...):  this.tree[node] += d * segLen;  this.lazy[node] += d;
#push(...):   hand tag to children, clear it

because the delta applies to a whole segment at once — d × segment length for sums.

push() before descending

Every path that goes below a node (update split case and query split case) calls push first. Miss one call site and queries read stale values.

Lazy = basic tree + apply/push + push-before-descend discipline.

Common Mistakes

Forgetting d × segmentLength.

A tag of +10 on a 3-element segment adds 30 to its sum, not 10.

Pushing only in query but not update (or vice versa).

Both recursions descend — both must push. Audit every recursive call site.

Composing tags wrongly for non-commutative ops.

Addition composes freely (+a then +b = +(a+b)), so tags just sum. Range assign needs “later assignment wins” logic — different tag merge.

Complexity

OperationTime
Range addO(log n)
Range sumO(log n)
SpaceO(n) — two arrays of 4n

My Private Notes

Notes are auto-saved locally to this device.