🗂️Data StructureIntermediate

Segment Tree with Lazy Propagation

Key Points

  • •
    A segment tree with lazy propagation supports fast range updates and range queries in O( n) time.
  • •
    Lazy tags record pending updates so we avoid immediately visiting all elements in an updated range.
  • •
    Before accessing a child, we push its parent's lazy tag down to keep information consistent.
  • •
    Common operations include range add, range assign (set), and range multiply, and they can be composed.
  • •
    Building a segment tree is O(n), and each query or update is O( n), with O(n) memory.
  • •
    Designing correct tag composition rules is crucial; the order of operations matters.
  • •
    For sums, applying an add to a segment of length increases the segment sum by .
  • •
    Affine updates f(x)=a x + b (add/multiply/assign) compose cleanly and are powerful in competitive programming.

Prerequisites

  • →Binary trees and recursion — Segment trees are binary trees explored via recursive functions for build, update, and query.
  • →Big-O notation — Understanding O(n) build and O(log n) per operation clarifies performance guarantees.
  • →Associativity and identity elements — Merging node values and composing lazy tags rely on associative operations with identities.
  • →Array indexing and ranges — Correct handling of inclusive [L, R] intervals avoids off-by-one errors.
  • →Modular arithmetic (optional) — Affine lazy propagation under modulo requires correct modular operations and inverses when applicable.
  • →Basic algebra of functions — Composing updates like f(x)=a x + b and g(x)=c x + d requires understanding function composition.

Detailed Explanation

Tap terms for definitions

01Overview

A segment tree is a binary tree data structure that stores information about intervals of an array, allowing efficient range queries and updates. Lazy propagation is an optimization technique for segment trees that defers updates to children until they are absolutely needed. Instead of immediately descending to update every affected leaf, we store a "lazy" tag at a node to remember a pending operation for its entire segment. When a later operation or query needs to access the node’s children, we "push down" the pending update to the children, update their stored values accordingly, and clear the parent’s lazy tag. This approach keeps the tree shallow in work per operation, ensuring O(\log n) performance even for range updates. Typical use-cases include maintaining range sums, minima/maxima, or other associative aggregates while supporting operations like range addition, range assignment (set to a value), or range multiplication. Competitive programming problems often combine several update types, making lazy propagation an essential technique for sublinear range operations. The segment tree’s design focuses on three core procedures: apply a lazy tag to a node (to update its stored aggregate quickly), push a node’s tag to its children (to keep the tree consistent), and pull from children to recompute a parent’s aggregate.

02Intuition & Analogies

Imagine you manage a long street of houses (an array), and you keep records like total electricity usage (sum) or the minimum temperature recorded among houses (min). When the city issues a policy like "add 5 units to every house’s allowance from house 10 to 100," you could walk to every house and update the record—slow and tedious. Instead, you post a notice on the community board for that block: "pending +5 for all houses here." Later, if a resident of that block asks a question, you first process the notice (apply it to the relevant sub-blocks or houses) and then answer. That notice is your lazy tag: it remembers the deferred update so you can avoid redundant work. A segment tree is like a hierarchy of community boards: the root covers the whole street, each child covers half, and so on. When an update covers an entire board’s region, you just post one notice at that board and do not disturb the smaller groups below. When someone asks about a particular subset (a query), you only push notices down into the smaller groups you need to visit. Because each visit splits the problem in half, you do logarithmic work rather than linear. Multiple notices can stack: e.g., “multiply by 3, then add 2.” The order matters—doing add then multiply is different from multiply then add—so you must carefully define how to combine (compose) notices.

03Formal Definition

Given an array A[0..n-1], a segment tree is a full binary tree where each node v represents an interval [L, R] and stores an aggregate value over A[L..R] (e.g., sum, min). For associative operations with an identity (monoids), parent values are computed from children: value([L, R]) = merge(value([L, M]), value([M+1, R])) for M = (L+R)/2 . Lazy propagation introduces a tag at node v that encodes a pending operation to be applied uniformly to all elements in [L, R]. Applying a tag to a node updates its stored aggregate in O(1) using known formulas, without recursing. Tags must be composable: given two tags and , their composition represents "apply first, then ". When traversing from a node to its children, we push the node’s tag to its children: , update the children’s aggregates in O(1), and clear . For example, for range sums with affine updates f(x) = a x + b, node aggregates (sum) update as sum' = a sum + b , where is the segment length. The tree supports range queries and updates in O( n) time by visiting at most O( n) nodes and doing O(1) work per visited node.

04When to Use

Use a segment tree with lazy propagation when you need both range queries and range updates with near real-time performance: O(\log n) per operation. Typical tasks include: (1) Range addition or multiplication with range sum queries; (2) Range assignment (set all elements in [L, R] to v) combined with range sum queries; (3) Range increment with range min/max queries; (4) Problems requiring multiple updates to stack, such as applying affine transformations f(x) = a x + b under modulo; (5) Dynamic constraints checks, e.g., maintaining prefix minima/maximum while performing bulk updates. It is ideal for competitive programming problems where n can be up to 2e5 or more and both updates and queries are frequent. If only queries or only point updates exist, simpler structures like Fenwick Trees (Binary Indexed Trees) or prefix sums might suffice. If operations are not easily expressible as uniform tags over a segment (e.g., "chmin" with structure-sensitive behavior), consider advanced techniques like Segment Tree Beats. If memory is tight but coordinates are sparse, consider a dynamic (implicit) segment tree that allocates nodes on demand.

⚠️Common Mistakes

Common pitfalls include: (1) Incorrect tag composition order. Remember that if a child already has a pending tag C and you push a new parent tag P, the child’s new tag should represent P after C: P \circ C. (2) Forgetting to scale updates by segment length when updating aggregates like sums; e.g., adding \Delta to each element of a segment of length \ell increases the sum by \Delta \cdot \ell. (3) Not clearing or incorrectly clearing lazy tags after pushing; always reset the parent’s tag to identity after propagation. (4) Mixing 0/1-based indices or off-by-one errors in [L, R] inclusive ranges; be consistent throughout build, update, and query. (5) Using the wrong numeric type and causing overflow; for big sums, use 64-bit integers or apply modulo arithmetic consistently. (6) Failing to maintain invariants when adding new operations; for example, when supporting assignment with addition, ensure assignment overrides previous operations correctly. Modeling all updates as affine maps f(x) = a x + b greatly simplifies correctness. (7) Pushing lazies unnecessarily on non-overlapping branches, which can degrade performance; only push when you are about to visit children. (8) Forgetting that build is O(n) and performing O(n \log n) naive inserts into an initially empty tree.

Key Formulas

Build Time Recurrence

Explanation: Building visits each element a constant number of times across levels, leading to linear time. The recurrence solves to O(n).

Per-Operation Time

Explanation: Each update or query descends along at most one path per level and does O(1) work per visited node, yielding logarithmic time.

Range Add on Sum

Explanation: Adding to each element of a segment of length increases the stored sum by times . This avoids touching each element individually.

Range Add on Min

Explanation: If you add to every element in an interval, the minimum increases by exactly as well. The same holds for maximum.

Affine Composition

Explanation: Affine updates (multiply and add) compose into another affine update. This enables stacking multiple range updates into a single tag.

Apply Affine to Sum

Explanation: When applying f(x)=a x + b to every element in a segment of length , the new sum equals a times the old sum plus b times .

Tree Height

Explanation: The height of a balanced binary segment tree over n elements is the ceiling of log base 2 of n, which bounds recursion depth.

Space Complexity

Explanation: A segment tree allocates a constant number of nodes per array position (commonly about 4n), plus O(n) for lazy tags.

Node Count Bound

Explanation: A full binary tree covering n leaves uses at most about 2·2^{ n} nodes, often implemented with arrays sized near 4n.

Complexity Analysis

Building the segment tree from an array takes O(n) time because every element contributes to O(1) work per level, and the total number of nodes is O(n). For each range update or range query, the algorithm descends the tree, visiting at most a constant number of nodes per level (often two), leading to O(log n) time per operation. Crucially, lazy propagation ensures we do O(1) work at internal nodes on the path: instead of recursing further to update each covered child, we update the node’s aggregate using closed-form formulas and record a lazy tag representing the deferred update. This avoids O(k) work proportional to the number of elements in the updated subarray. Space usage is O(n): the tree typically allocates an array of size about 4n to store node aggregates (e.g., sums, mins) and another array of size about 4n for lazy tags. The recursion depth is O(log n), so the auxiliary stack memory is also O(log n). When implementing affine updates (multiply and add, and even assignment via a=0), both "apply" and "compose" operations are O(1), preserving the same time bounds. Be mindful that constants can vary based on the richness of stored information; for example, tracking both minimum and count of minima adds small constant overhead but not asymptotic changes. Overall, with well-implemented lazy propagation, the performance profile is: build O(n), update O(log n), query O(log n), and memory O(n).

Code Examples

Range Add and Range Sum Query (Lazy Propagation Basics)
1#include <bits/stdc++.h>
2using namespace std;
3
4struct SegTree {
5    int n;
6    vector<long long> st;   // segment sums
7    vector<long long> lazy; // pending range-add values
8
9    SegTree(const vector<long long>& a) { build(a); }
10
11    void build(const vector<long long>& a) {
12        n = (int)a.size();
13        st.assign(4*n, 0);
14        lazy.assign(4*n, 0);
15        build(1, 0, n-1, a);
16    }
17
18    void build(int p, int l, int r, const vector<long long>& a) {
19        if (l == r) { st[p] = a[l]; return; }
20        int m = (l + r) >> 1;
21        build(p<<1, l, m, a);
22        build(p<<1|1, m+1, r, a);
23        st[p] = st[p<<1] + st[p<<1|1];
24    }
25
26    // Apply an add-tag v to node p covering [l, r]
27    void apply(int p, int l, int r, long long v) {
28        st[p] += v * (r - l + 1); // sum increases by v * segment length
29        lazy[p] += v;             // accumulate pending add
30    }
31
32    // Push lazy value at p to its children
33    void push(int p, int l, int r) {
34        if (lazy[p] == 0 || l == r) return; // nothing to push or leaf
35        int m = (l + r) >> 1;
36        apply(p<<1, l, m, lazy[p]);
37        apply(p<<1|1, m+1, r, lazy[p]);
38        lazy[p] = 0; // clear after pushing
39    }
40
41    void range_add(int ql, int qr, long long v) { range_add(1, 0, n-1, ql, qr, v); }
42
43    void range_add(int p, int l, int r, int ql, int qr, long long v) {
44        if (qr < l || r < ql) return;             // no overlap
45        if (ql <= l && r <= qr) { apply(p, l, r, v); return; } // cover
46        push(p, l, r);
47        int m = (l + r) >> 1;
48        range_add(p<<1, l, m, ql, qr, v);
49        range_add(p<<1|1, m+1, r, ql, qr, v);
50        st[p] = st[p<<1] + st[p<<1|1]; // pull
51    }
52
53    long long range_sum(int ql, int qr) { return range_sum(1, 0, n-1, ql, qr); }
54
55    long long range_sum(int p, int l, int r, int ql, int qr) {
56        if (qr < l || r < ql) return 0;          // identity for sum
57        if (ql <= l && r <= qr) return st[p];
58        push(p, l, r);
59        int m = (l + r) >> 1;
60        return range_sum(p<<1, l, m, ql, qr) + range_sum(p<<1|1, m+1, r, ql, qr);
61    }
62};
63
64int main() {
65    ios::sync_with_stdio(false);
66    cin.tie(nullptr);
67
68    vector<long long> a = {1, 2, 3, 4, 5};
69    SegTree st(a);
70
71    cout << st.range_sum(0, 4) << "\n"; // 15
72    st.range_add(1, 3, 10);              // a = [1, 12, 13, 14, 5]
73    cout << st.range_sum(0, 4) << "\n"; // 45
74    cout << st.range_sum(2, 4) << "\n"; // 32
75
76    // Further checks
77    st.range_add(0, 4, -2);              // subtract 2 everywhere
78    cout << st.range_sum(0, 4) << "\n"; // 35
79
80    return 0;
81}
82

This implementation supports range addition and range sum queries. Lazy values store pending additions for a node’s entire segment. We apply updates in O(1) to a node (sum plus v times segment length) and defer touching children until necessary via push().

Time: O(log n)Space: O(n)
Range Add and Range Minimum Query
1#include <bits/stdc++.h>
2using namespace std;
3
4struct SegTreeMin {
5    int n;
6    vector<long long> mn;   // segment minimums
7    vector<long long> lazy; // pending range-add values
8
9    SegTreeMin(const vector<long long>& a) { build(a); }
10
11    void build(const vector<long long>& a) {
12        n = (int)a.size();
13        mn.assign(4*n, (long long)4e18);
14        lazy.assign(4*n, 0);
15        build(1, 0, n-1, a);
16    }
17
18    void build(int p, int l, int r, const vector<long long>& a) {
19        if (l == r) { mn[p] = a[l]; return; }
20        int m = (l + r) >> 1;
21        build(p<<1, l, m, a);
22        build(p<<1|1, m+1, r, a);
23        mn[p] = min(mn[p<<1], mn[p<<1|1]);
24    }
25
26    void apply(int p, long long v) {
27        mn[p] += v;    // shifting all elements by v shifts min by v
28        lazy[p] += v;
29    }
30
31    void push(int p) {
32        if (lazy[p] == 0) return;
33        apply(p<<1, lazy[p]);
34        apply(p<<1|1, lazy[p]);
35        lazy[p] = 0;
36    }
37
38    void range_add(int p, int l, int r, int ql, int qr, long long v) {
39        if (qr < l || r < ql) return;
40        if (ql <= l && r <= qr) { apply(p, v); return; }
41        push(p);
42        int m = (l + r) >> 1;
43        range_add(p<<1, l, m, ql, qr, v);
44        range_add(p<<1|1, m+1, r, ql, qr, v);
45        mn[p] = min(mn[p<<1], mn[p<<1|1]);
46    }
47
48    long long range_min(int p, int l, int r, int ql, int qr) {
49        if (qr < l || r < ql) return (long long)4e18; // identity for min
50        if (ql <= l && r <= qr) return mn[p];
51        push(p);
52        int m = (l + r) >> 1;
53        return min(range_min(p<<1, l, m, ql, qr), range_min(p<<1|1, m+1, r, ql, qr));
54    }
55
56    // public wrappers
57    void range_add(int l, int r, long long v) { range_add(1, 0, n-1, l, r, v); }
58    long long range_min(int l, int r) { return range_min(1, 0, n-1, l, r); }
59};
60
61int main() {
62    ios::sync_with_stdio(false);
63    cin.tie(nullptr);
64
65    vector<long long> a = {7, 3, 5, 9, 1, 4};
66    SegTreeMin st(a);
67
68    cout << st.range_min(0, 5) << "\n"; // 1
69    st.range_add(1, 4, -2);             // a becomes [7,1,3,7,-1,4]
70    cout << st.range_min(0, 5) << "\n"; // -1
71    cout << st.range_min(2, 3) << "\n"; // 3
72
73    return 0;
74}
75

This variant maintains range minima with range addition updates. The lazy tag is a simple shift value: if every element increases by v, the minimum also increases by v. We push only when visiting children, and recompute parent minima by taking min of children.

Time: O(log n)Space: O(n)
Affine Lazy Propagation (Multiply/Add/Assign) with Range Sum under Modulo
1#include <bits/stdc++.h>
2using namespace std;
3
4// Supports updates of the form f(x) = a*x + b (mod MOD) on ranges, and range sum queries.
5// Special cases:
6//  - Add d:      a=1, b=d
7//  - Multiply m: a=m, b=0
8//  - Assign v:   a=0, b=v
9
10struct SegTreeAffine {
11    using int64 = long long;
12    int n;
13    long long MOD;
14
15    struct Tag { long long a, b; }; // f(x) = a*x + b (mod MOD)
16    vector<long long> st; // sums modulo MOD
17    vector<Tag> lazy;     // pending affine tags
18
19    SegTreeAffine(const vector<long long>& a, long long MOD): MOD(MOD) { build(a); }
20
21    Tag id() const { return Tag{1 % MOD, 0}; }
22
23    // Compose tags: new_tag = P \circ C (apply P after C)
24    Tag compose(const Tag& P, const Tag& C) const {
25        Tag R;
26        R.a = (P.a * C.a) % MOD;
27        R.b = ( (P.a * C.b) % MOD + P.b ) % MOD;
28        return R;
29    }
30
31    void build(const vector<long long>& a) {
32        n = (int)a.size();
33        st.assign(4*n, 0);
34        lazy.assign(4*n, id());
35        build(1, 0, n-1, a);
36    }
37
38    void build(int p, int l, int r, const vector<long long>& a) {
39        if (l == r) { st[p] = (a[l] % MOD + MOD) % MOD; return; }
40        int m = (l + r) >> 1;
41        build(p<<1, l, m, a);
42        build(p<<1|1, m+1, r, a);
43        st[p] = (st[p<<1] + st[p<<1|1]) % MOD;
44    }
45
46    void apply(int p, int l, int r, const Tag& t) {
47        long long len = r - l + 1;
48        st[p] = ( (t.a * st[p]) % MOD + (t.b * (len % MOD)) % MOD ) % MOD;
49        lazy[p] = compose(t, lazy[p]); // new lazy = t after existing
50    }
51
52    void push(int p, int l, int r) {
53        Tag &t = lazy[p];
54        if (t.a == 1 % MOD && t.b == 0) return; // identity, nothing to push
55        int m = (l + r) >> 1;
56        apply(p<<1, l, m, t);
57        apply(p<<1|1, m+1, r, t);
58        lazy[p] = id();
59    }
60
61    void range_update(int p, int l, int r, int ql, int qr, const Tag& t) {
62        if (qr < l || r < ql) return;
63        if (ql <= l && r <= qr) { apply(p, l, r, t); return; }
64        push(p, l, r);
65        int m = (l + r) >> 1;
66        range_update(p<<1, l, m, ql, qr, t);
67        range_update(p<<1|1, m+1, r, ql, qr, t);
68        st[p] = (st[p<<1] + st[p<<1|1]) % MOD;
69    }
70
71    long long range_sum(int p, int l, int r, int ql, int qr) {
72        if (qr < l || r < ql) return 0;
73        if (ql <= l && r <= qr) return st[p];
74        push(p, l, r);
75        int m = (l + r) >> 1;
76        return (range_sum(p<<1, l, m, ql, qr) + range_sum(p<<1|1, m+1, r, ql, qr)) % MOD;
77    }
78
79    // Public APIs
80    void range_add(int l, int r, long long d) {
81        Tag t{1 % MOD, (d % MOD + MOD) % MOD};
82        range_update(1, 0, n-1, l, r, t);
83    }
84    void range_mul(int l, int r, long long m) {
85        Tag t{(m % MOD + MOD) % MOD, 0};
86        range_update(1, 0, n-1, l, r, t);
87    }
88    void range_assign(int l, int r, long long v) {
89        Tag t{0, (v % MOD + MOD) % MOD};
90        range_update(1, 0, n-1, l, r, t);
91    }
92    long long range_sum(int l, int r) { return range_sum(1, 0, n-1, l, r); }
93};
94
95int main() {
96    ios::sync_with_stdio(false);
97    cin.tie(nullptr);
98
99    const long long MOD = 1'000'000'007LL;
100    vector<long long> a = {1, 2, 3, 4, 5};
101    SegTreeAffine st(a, MOD);
102
103    cout << st.range_sum(0, 4) << "\n"; // 15
104    st.range_add(0, 4, 5);                // +5 everywhere -> [6,7,8,9,10]
105    cout << st.range_sum(1, 3) << "\n"; // 7+8+9 = 24
106
107    st.range_mul(2, 4, 3);                // multiply last 3 by 3 -> [6,7,24,27,30]
108    cout << st.range_sum(2, 4) << "\n"; // 24+27+30 = 81
109
110    st.range_assign(1, 3, 10);            // set indices 1..3 to 10 -> [6,10,10,10,30]
111    cout << st.range_sum(0, 4) << "\n"; // 66
112
113    return 0;
114}
115

This example supports affine updates f(x)=a x + b under modulo and range sum queries. Add, multiply, and assign are encoded as affine tags and composed as P ∘ C when pushing. Applying a tag to a node updates its sum in O(1) using sum' = a·sum + b·len (mod MOD).

Time: O(log n)Space: O(n)