Log inSign up
hardGeeksforGeeksNot Started

Lazy Propagation in Segment Tree

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Advanced DSA
Solve on GeeksforGeeks
Lesson

Problem Statement

A standard Segment Tree handles range queries and point updates in O(log n) time. However, updating a whole range of elements [L, R] naively requires O(n log n) operations.

Lazy Propagation solves this by deferring (lazily storing) updates until that segment's information is strictly needed by a future query or update.

Implement a Segment Tree supporting: 1. updateRange(L, R, val): Adds val to every element in the range nums[L...R] (0-indexed, inclusive). 2. queryRange(L, R): Computes the sum of elements in nums[L...R] (0-indexed, inclusive).

Both operations must run in O(log n) time.

Example 1 · Example 1:

Input: nums = [1, 2, 3, 4, 5] operations: [queryRange(0, 4), updateRange(1, 3, 10), queryRange(0, 4), queryRange(1, 2)]
Output: [15, null, 45, 27]
Explanation: Initial sum nums[0..4] = 1 + 2 + 3 + 4 + 5 = 15. After updateRange(1, 3, 10), array becomes [1, 12, 13, 14, 5]. New total sum nums[0..4] = 1 + 12 + 13 + 14 + 5 = 45. Range sum nums[1..2] = 12 + 13 = 27.

Example 2 · Example 2:

Input: nums = [0, 0, 0, 0] operations: [updateRange(0, 1, 5), updateRange(1, 2, 3), queryRange(0, 3)]
Output: [null, null, 16]
Explanation: Array starts [0, 0, 0, 0] -> [5, 5, 0, 0] -> [5, 8, 3, 0]. Sum = 5 + 8 + 3 + 0 = 16.

Constraints:

  • 1 <= nums.length <= 105
  • -104 <= nums[i], val <= 104
  • 0 <= L <= R < nums.length
  • At most 105 calls to updateRange and queryRange will be made.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the 3 distinct approaches for Lazy Propagation in Segment Tree.
  • Implement fully runnable solutions in C++, Java, Python, and JavaScript.
  • Analyze algorithmic trade-offs across data structure designs.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Lazy Propagation in Segment Tree
  • Advanced Data Structures & Algorithmic Paradigm
  • Fast Range Queries or Amortized Dynamic Operations

Algorithmic Decision Tree:

  • BRUTE_FORCE: Basic prototyping when N, Q <= 1000.
  • BETTER: When range updates are rare or range lengths are very short.
  • OPTIMAL: The standard algorithm for general range updates and range queries on associative operations.

Connected Patterns:

Segment TreeFenwick TreeDisjoint Set UnionDesign Data Structures

1. Direct Array Loops

Intuition

Store nums in a basic array. - updateRange(L, R, val): For i from L to R, add val to nums[i]. Runs in O(n) time. - queryRange(L, R): For i from L to R, sum elements nums[i]. Runs in O(n) time. For Q operations, total time is O(Q \cdot n), which times out for large N and Q.

When to apply: Basic prototyping when N, Q <= 1000.

Algorithm

  1. Step 1: Store elements in array nums.
  2. Step 2: On updateRange(L, R, val), loop i from L to R adding val.
  3. Step 3: On queryRange(L, R), loop i from L to R adding nums[i] to a sum variable and return.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class LazyBrute {
5 std::vector<long long> arr;
6public:
7 LazyBrute(const std::vector<int>& nums) : arr(nums.begin(), nums.end()) {}
8
9 void updateRange(int l, int r, int val) {
10 for (int i = l; i <= r; ++i) arr[i] += val;
11 }
12
13 long long queryRange(int l, int r) {
14 long long sum = 0;
15 for (int i = l; i <= r; ++i) sum += arr[i];
16 return sum;
17 }
18};
19
20int main() {
21 std::vector<int> nums = {1, 2, 3, 4, 5};
22 LazyBrute st(nums);
23 std::cout << st.queryRange(0, 4) << std::endl;
24 st.updateRange(1, 3, 10);
25 std::cout << st.queryRange(0, 4) << std::endl;
26 std::cout << st.queryRange(1, 2) << std::endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(n) per updateRange and queryRange
  • Space complexity: O(n) space for array storage

2. Point-Update Segment Tree

Intuition

In a standard Segment Tree without lazy propagation, updates are executed at individual leaves: - queryRange(L, R): Runs in O(log n) by combining segment sums. - updateRange(L, R, val): Must call point update R - L + 1 times. Each point update costs O(log n), meaning the range update costs O((R - L + 1) log n) = O(n log n) in the worst case. While queries are fast, large range updates remain bottlenecks.

When to apply: When range updates are rare or range lengths are very short.

Algorithm

  1. Step 1: Construct standard segment tree of size 4 * n.
  2. Step 2: On queryRange(L, R), return sum using segment tree in O(log n).
  3. Step 3: On updateRange(L, R, val), execute point update(i, val) for each index i from L to R in O(k log n).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class SegTreePoint {
5 int n;
6 std::vector<long long> tree;
7
8 void build(int node, int start, int end, const std::vector<int>& arr) {
9 if (start == end) {
10 tree[node] = arr[start];
11 return;
12 }
13 int mid = (start + end) / 2;
14 build(2 * node, start, mid, arr);
15 build(2 * node + 1, mid + 1, end, arr);
16 tree[node] = tree[2 * node] + tree[2 * node + 1];
17 }
18
19 void pointUpdate(int node, int start, int end, int idx, int val) {
20 if (start == end) {
21 tree[node] += val;
22 return;
23 }
24 int mid = (start + end) / 2;
25 if (idx <= mid) pointUpdate(2 * node, start, mid, idx, val);
26 else pointUpdate(2 * node + 1, mid + 1, end, idx, val);
27 tree[node] = tree[2 * node] + tree[2 * node + 1];
28 }
29
30 long long query(int node, int start, int end, int l, int r) {
31 if (r < start || end < l) return 0;
32 if (l <= start && end <= r) return tree[node];
33 int mid = (start + end) / 2;
34 return query(2 * node, start, mid, l, r) + query(2 * node + 1, mid + 1, end, l, r);
35 }
36
37public:
38 SegTreePoint(const std::vector<int>& nums) : n(nums.size()), tree(4 * nums.size(), 0) {
39 build(1, 0, n - 1, nums);
40 }
41
42 void updateRange(int l, int r, int val) {
43 for (int i = l; i <= r; ++i) pointUpdate(1, 0, n - 1, i, val);
44 }
45
46 long long queryRange(int l, int r) {
47 return query(1, 0, n - 1, l, r);
48 }
49};
50
51int main() {
52 std::vector<int> nums = {1, 2, 3, 4, 5};
53 SegTreePoint st(nums);
54 std::cout << st.queryRange(0, 4) << std::endl;
55 st.updateRange(1, 3, 10);
56 std::cout << st.queryRange(0, 4) << std::endl;
57 std::cout << st.queryRange(1, 2) << std::endl;
58 return 0;
59}

Time & Space Complexity

  • Time complexity: O((R - L + 1) log n) for updateRange, O(log n) for queryRange
  • Space complexity: O(n) auxiliary space for tree array

3. Segment Tree with Lazy Propagation

Intuition

Lazy Propagation eliminates updating every child node eagerly: 1. Maintain two arrays: - tree[node]: Stores the current segment sum. - lazy[node]: Stores pending additions that have updated tree[node] but have not yet been pushed to its children. 2. Push Down Operation (`pushDown`): - If lazy[node] != 0 and the node is not a leaf: - Child ranges receive pending delta: lazy[2*node] += lazy[node], lazy[2*node+1] += lazy[node]. - Update child sums: \text{tree}[child] += (\text{childEnd} - \text{childStart} + 1) × \text{lazy}[node]. - Clear lazy[node] = 0. 3. Range Update (`updateRange`): - If current segment [start, end] is entirely within [L, R]: - Update current segment sum: \text{tree}[node] += (end - start + 1) × val. - Record in lazy[node] += val. Return immediately! (O(1) at this node). - Otherwise, push down pending updates, recurse on overlapping children, and recalculate \text{tree}[node] = \text{tree}[left] + \text{tree}[right]. 4. Range Query (`queryRange`): - Push down pending updates, then sum overlapping children. 5. Both operations visit at most O(log n) nodes, achieving O(log n) per range update and query.

When to apply: The standard algorithm for general range updates and range queries on associative operations.

Algorithm

  1. Step 1: Allocate tree and lazy arrays of size 4 * n initialized to 0.
  2. Step 2: Build tree from input array in O(n) time.
  3. Step 3: Define pushDown(node, start, end): if lazy[node] != 0, apply lazy delta to left and right children and reset lazy[node] = 0.
  4. Step 4: updateRange(node, start, end, l, r, val): if within [l, r], update tree[node] and accumulate lazy[node], return. Else pushDown, recurse children, and pull up.
  5. Step 5: queryRange(node, start, end, l, r): if disjoint return 0; if covered return tree[node]; else pushDown, sum children, and return.

Interactive trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Build Segment Tree on nums = [1, 2, 3, 4, 5]
Visual state
Values and pointers at this exact step
pointers
S
1
2
3
4
5
0
1
2
3
4
Check / comparison
Initial root sum = 15
Decision / next transition
queryRange(0, 4) returns 15
Why this step matters

Build Segment Tree on nums = [1, 2, 3, 4, 5]. Root node 1 covers [0, 4] with sum 15.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class LazySegmentTree {
5 int n;
6 std::vector<long long> tree;
7 std::vector<long long> lazy;
8
9 void build(int node, int start, int end, const std::vector<int>& arr) {
10 if (start == end) {
11 tree[node] = arr[start];
12 return;
13 }
14 int mid = (start + end) / 2;
15 build(2 * node, start, mid, arr);
16 build(2 * node + 1, mid + 1, end, arr);
17 tree[node] = tree[2 * node] + tree[2 * node + 1];
18 }
19
20 void pushDown(int node, int start, int end) {
21 if (lazy[node] != 0 && start != end) {
22 int mid = (start + end) / 2;
23 lazy[2 * node] += lazy[node];
24 tree[2 * node] += lazy[node] * (mid - start + 1);
25
26 lazy[2 * node + 1] += lazy[node];
27 tree[2 * node + 1] += lazy[node] * (end - mid);
28
29 lazy[node] = 0;
30 }
31 }
32
33 void update(int node, int start, int end, int l, int r, long long val) {
34 if (r < start || end < l) return;
35 if (l <= start && end <= r) {
36 tree[node] += val * (end - start + 1);
37 lazy[node] += val;
38 return;
39 }
40 pushDown(node, start, end);
41 int mid = (start + end) / 2;
42 update(2 * node, start, mid, l, r, val);
43 update(2 * node + 1, mid + 1, end, l, r, val);
44 tree[node] = tree[2 * node] + tree[2 * node + 1];
45 }
46
47 long long query(int node, int start, int end, int l, int r) {
48 if (r < start || end < l) return 0;
49 if (l <= start && end <= r) return tree[node];
50 pushDown(node, start, end);
51 int mid = (start + end) / 2;
52 return query(2 * node, start, mid, l, r) + query(2 * node + 1, mid + 1, end, l, r);
53 }
54
55public:
56 LazySegmentTree(const std::vector<int>& nums) : n(nums.size()), tree(4 * nums.size(), 0), lazy(4 * nums.size(), 0) {
57 build(1, 0, n - 1, nums);
58 }
59
60 void updateRange(int l, int r, long long val) {
61 update(1, 0, n - 1, l, r, val);
62 }
63
64 long long queryRange(int l, int r) {
65 return query(1, 0, n - 1, l, r);
66 }
67};
68
69int main() {
70 std::vector<int> nums = {1, 2, 3, 4, 5};
71 LazySegmentTree st(nums);
72 std::cout << st.queryRange(0, 4) << std::endl;
73 st.updateRange(1, 3, 10);
74 std::cout << st.queryRange(0, 4) << std::endl;
75 std::cout << st.queryRange(1, 2) << std::endl;
76 return 0;
77}

Time & Space Complexity

  • Time complexity: O(log n) for both updateRange and queryRange
  • Space complexity: O(n) auxiliary space for tree and lazy arrays

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Direct Array LoopsO(n) per updateRange and queryRangeO(n) space for array storageApply range additions and range sums with straightforward loops over the array.O(n) per updateRange and queryRange
2.Point-Update Segment TreeO((R - L + 1) log n) for updateRange, O(log n) for queryRangeO(n) auxiliary space for tree arrayUse a standard Segment Tree without lazy propagation. A range update is broken into R - L + 1 point updates.O((R - L + 1) log n) for updateRange, O(log n) for queryRange
3.Segment Tree with Lazy PropagationOptimalO(log n) for both updateRange and queryRangeO(n) auxiliary space for tree and lazy arraysStore pending updates in a lazy array. Push updates down to children only when visited, achieving O(log n) for both range updates and range queries.O(log n) for both updateRange and queryRange

Common Pitfalls & Crucial Edge Cases

Forgetting to clear the lazy tag after pushing down

lazy[node] = 0 must be set after updating children, otherwise the tag will be pushed repeatedly.

Forgetting to multiply delta by interval length

Adding lazy[node] instead of lazy[node] * (end - start + 1) to the segment sum.

Not calling `pushDown` during range queries

If queries don't push down pending updates, they read stale data from child nodes.

Crucial Edge Cases to Validate:

  • Range update on a single leaf (L == R) — Handled seamlessly without pushing to non-existent children.
  • Multiple consecutive updates on overlapping ranges — Lazy tags must accumulate (e.g. lazy[child] += lazy[parent]).
  • Range update spanning the entire array [0, N - 1] — Root node is updated and tagged in O(1) time.
  • Integer overflow on range sums — Sums of 105 elements can exceed 32-bit signed ints; use 64-bit integer types.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the core philosophy: 'Do work only when necessary.'
  2. Walk through the tree traversal: (1) Total overlap -> apply tag and return, (2) Partial overlap -> pushDown, recurse children, recalculate parent (pushUp).
  3. Highlight that lazy propagation is essential for range assignments, range additions, and range flips.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What problem does Lazy Propagation solve in Segment Trees?

2.When is a lazy tag pushed down to its children (pushDown)?

3.How does a lazy addition tag affect the range sum of a node covering [start, end]?

Back to DSA Sheet