Segment Tree

Lazy Propagation

For RANGE updates (update all elements from L to R), don't push changes to every leaf immediately. Store a 'lazy' tag at internal nodes. Push the tag down only when you need to access children. This makes range updates O(log n).

O(log n) per op

O(n)

How It Works

Lazy propagation makes range updates as cheap as range queries. Updating every leaf in [L, R] individually would cost O(n log n) per update; instead, when an update fully covers a node's range, apply it to that node's aggregate and record a pending tag — the promise that the node's children still owe this update — then stop descending. Only O(log n) nodes get touched, mirroring the query decomposition.

Before any later operation descends into a tagged node's children, the tag is pushed down: each child's aggregate is adjusted, tags are composed onto the children, and the parent's tag clears. Correctness holds because every node's stored value is always accurate for its own range; only descendants are stale, and they are refreshed exactly when visited. Both range update and range query stay O(log n), which is what makes problems with millions of interleaved range additions and range sums tractable.

Step-by-Step Visualization

Lazy propagation: range update without touching all leaves

UpdateAdd 10 to range [1,3]

1/3

Code

Java

// Extension of segment tree with lazy propagation
void update(int node, int start, int end, int l, int r, int val) {
  if (lazy[node] != 0) pushDown(node, start, end);
  if (r < start || end < l) return;
  if (l <= start && end <= r) {
    tree[node] += (end - start + 1) * val;
    if (start != end) {
      lazy[2*node] += val;
      lazy[2*node+1] += val;
    }
    return;
  }
  int mid = (start + end) / 2;
  update(2*node, start, mid, l, r, val);
  update(2*node+1, mid+1, end, l, r, val);
  tree[node] = tree[2*node] + tree[2*node+1];
}

Tips & Gotchas

1For range updates, don't push changes to every leaf immediately

2Store pending updates in a 'lazy' array

3Push down lazy values only when needed (during queries)

Practice Problems

1Range Sum Query - Mutable
2My Calendar III
3Corporate Flight Bookings
4Falling Squares

About the Segment Tree Pattern

A binary tree where each node represents a range of the array. Leaves are individual elements. Internal nodes store the aggregate (sum, min, max) of their children's ranges. Supports both queries and updates in O(log n).

Key insight

If you only need prefix queries with point updates, use a BIT (simpler). If you need arbitrary range queries + range updates, use a segment tree with lazy propagation. Sparse table is O(1) query but static.

Common Range Structures Interview Problems

Range Sum Query - Mutable
Count of Smaller Numbers After Self
Range Minimum Query
Longest Increasing Subsequence (BIT approach)

Frequently Asked Questions

When do I actually need lazy propagation versus a plain segment tree?

Only when updates cover ranges rather than single points. Point updates already cost O(log n) in a plain segment tree; it is a range update — add 5 to every element in [L, R] — that would force O(n) leaf writes without laziness. If your problem has point updates only, skip the added complexity.

How are two pending updates on the same node combined?

Tags must compose: for range-add, tags simply sum; for range-assign, the newer assignment overwrites the older tag entirely; for mixed add-and-assign trees, an assignment clears any pending add beneath it while an add on top of an assignment folds into the assigned value. Getting this composition order wrong is the most common lazy-propagation bug.

Is a Fenwick tree ever enough for range updates?

Yes — the difference-array trick gives a BIT range-update with point-query, and two BITs together support range-update with range-sum, all in less code than a lazy segment tree. The segment tree becomes necessary for non-invertible aggregates like range min/max or for complicated composed updates.