🗂️Data StructureAdvanced

Segment Tree - Handling Multiple Lazy Operations

Key Points

  • •
    When a segment tree supports multiple range updates, you must define how lazy tags compose, because the order of operations matters and composition is not commutative.
  • •
    Assignments typically take precedence over adds and multiplies; a new assign should overwrite any pending add, while adds should merge by summation and multiplies should scale both add and sum.
  • •
    A clean, unified approach is to model updates as affine transformations f(x) = a x + b; add and multiply are special cases, and assign v is simply f(x) = 0 · x + v.
  • •
    Lazy composition follows time order: if an old tag is F and a new update is G, the combined effect is G ∘ F, not F ∘ G.
  • •
    To update sums quickly, use the formula new_ · ol + b · segmen, which updates a node in O(1).
  • •
    Always push tags before visiting children and pull values after visiting children to maintain correctness.
  • •
    Keep identities clear: the neutral tag for affine updates is (a = 1, b = 0); for add-only it is add = 0; for assign, you usually need a special flag or use affine with a = 0.
  • •
    Most multi-operation lazy segment trees provide O(log n) time per range update/query and O(n) space.

Prerequisites

  • →Arrays and indexing — Segment trees store aggregates over subarrays; correct indexing is essential.
  • →Recursion and divide-and-conquer — Building, updating, and querying a segment tree use recursive traversal.
  • →Function composition — Multiple lazy updates combine via function composition, especially for affine tags.
  • →Modular arithmetic — Range multiply/add problems often require modulo operations to avoid overflow.
  • →Time and space complexity — Understanding why updates and queries are O(log n) and memory is O(n).

Detailed Explanation

Tap terms for definitions

01Overview

A segment tree with lazy propagation is a binary tree data structure that lets you efficiently apply range updates and answer range queries. The classic lazy segment tree defers ("lazily") pushing updates to children until absolutely necessary, so that many updates over large intervals can be handled in O(log n) time. When only one type of update exists (like range add), the lazy state is simple (just keep the pending addition). However, real problems often need multiple update types, such as range assignment plus range addition, or range multiply plus range add, or even all three simultaneously. The challenge is that these updates interact: an assignment should override older adds, and a multiply should scale pending adds. The key is to define lazy tags and their composition rules. Each node stores both an aggregate (like the sum over its interval) and a tag describing the deferred update to apply to its whole interval. New updates are composed with existing tags in a well-defined order. A powerful unifying view is that updates are affine functions f(x) = a x + b. Range add is (a=1, b=d), range multiply is (a=m, b=0), and range assign to c is (a=0, b=c). With this model, composing updates becomes function composition, and pushing a tag to children or merging multiple updates reduces to multiplying and adding the parameters a and b.

02Intuition & Analogies

Imagine you manage a long to-do list of students' test scores arranged in a line. Sometimes you want to curve all scores in a range by +5 (add), sometimes scale a range by 2 for extra credit (multiply), and sometimes overwrite a range with a fixed score, like setting the make-up exam result to 70 (assign). If you walked through each student one by one every time, you would be too slow. Instead, you keep sticky notes on folders: a folder for each segment of students. A sticky note says something like "multiply by 2 then add 5". You don't immediately open every folder and apply the change to each student; you only open subfolders when a query demands it. These sticky notes are your lazy tags. Now, if you later put another sticky note on the same folder, you must figure out what the combined effect is. Doing "+5" and then later "assign 70" should not keep the +5 or multiply around; the assignment overwrites everything. Meanwhile, doing multiply-by-2 and then add-3 is the same as a single operation f(x) = 2x + 3. If later you add +4, the total becomes g(x) = x + 4 after f, which is g ∘ f(x) = 2x + 7. Order matters: g ∘ f is not f ∘ g. This is exactly like composing little functions you write on sticky notes. When you finally need exact scores for a subrange, you "push" the note down—translating the parent’s note into equivalent notes for its children—and only then open the child folders. After finishing a child, you "pull" the updated summary back to the parent. By carefully defining what each sticky note means and how to combine notes, you can manage many types of updates efficiently without touching every single element.

03Formal Definition

Let A be an array of length n indexed by positions 0..n-1. A segment tree partitions the range [0, n-1] into intervals at nodes of a full binary tree. Each node v covers an interval and stores an aggregate value agg() (e.g., sum over ). A lazy tag represents a function to be applied to every element x in before agg() is considered accurate. For multi-operation updates, define each update as an affine transformation f(x) = a x + b over a ring (e.g., integers modulo M or 64-bit integers). The identity update is id(x) = x, i.e., (a, b) = (1, 0). Composition of two tags f and g is (f ∘ g)(x) = f(g(x)) with parameters (, ) ∘ (, ) = ( , + ). For an interval of length with sum S, applying f yields new sum S' = a S + b . Lazy propagation obeys these rules: when updating a node with tag f, we update its stored aggregate in O(1) using S' above and set ← f ∘ to preserve time order (new update after old). When descending into children u of v, we push by setting ← ∘ and then clearing to identity. The tree maintains correctness by always pushing before visiting children and pulling (recomputing agg from children) after recursion. Special multi-operations—like add, multiply, and assign—are modeled as affine updates: add d is (1, d), multiply m is (m, 0), and assign c is (0, c).

04When to Use

Use a multi-operation lazy segment tree whenever you need to support two or more types of range updates and queries over large arrays or dynamic ranges with tight time constraints, typically O((n + q) log n). Common competitive programming tasks include: range sum with range add and range assign; range sum with range multiply and range add (often modulo a prime); and problems where you need to apply multiple linear curves to a range (ax + b) and query sums or other linear-aggregatable functions. It is also useful when different updates must be applied in strict time order and you cannot afford to iterate over every element in the updated interval. If your queries are only point updates or only one simple range update (like add-only), a Fenwick tree may suffice and be simpler. If you need min/max with range chmin/chmax or range assign, a more advanced structure (segment tree beats) may be necessary. If you require persistence or rollbacks, consider a persistent segment tree or a treap/splay-based structure. But for most 1800–2200 CF-rating tasks that mix add/mul/assign on sums, the affine lazy segment tree is the right hammer.

⚠️Common Mistakes

  1. Wrong composition order: Using F ∘ G when you meant G ∘ F will silently produce incorrect answers. Remember: if T_old is pending and you receive a new update U_new, the combined effect is U_new ∘ T_old.
  2. Forgetting to scale by segment length: When updating sums with add or assign, you must multiply the increment by the length of the interval; otherwise results will be off by a factor. The correct formula is S' = a S + b |I|.
  3. Dropping assign precedence: In a two-tag design (assign + add), a new assign must clear the add tag; likewise, an add on top of an assign must increase the assign value instead of altering add. Using the affine model avoids this pitfall entirely.
  4. Not pushing before descending: If you forget to push a node’s lazy tag before visiting its children, you may double-apply updates or miss them entirely. Always push before partial overlaps.
  5. Overflow/modulo bugs: Multiplying large sums by large multipliers can overflow 64-bit; use modulo arithmetic where required and consistently reduce after every operation. Beware of negative mods.
  6. Incorrect identity initialization: The identity lazy tag must be (a, b) = (1, 0). Initializing to zeros will wipe data.
  7. Off-by-one and indexing errors: Clearly define whether your intervals are [l, r) or [l, r], and stick to it. Mismatches are a frequent source of WA.
  8. Forgetting to maintain node lengths: Keep each node’s interval length or compute it on the fly to update sums in O(1).

Key Formulas

Affine Tag Composition

Explanation: If you first apply (, ) and then apply (, ), the net effect is ( , + ). Order matters; this is function composition g ∘ f.

Sum Update Under Affine

Explanation: If a node covers interval I with sum S and you apply f(x) = a x + b to every element, the new sum is a times S plus b times the length of I. This lets you update node sums in O(1).

Encoding Common Updates

Explanation: Range add, multiply, and assign can all be expressed as affine updates. Assignment overrides previous operations because its multiplier is 0.

Single Operation Descent

Explanation: Each update or query descends the tree height, touching O(log n) nodes, with O(1) work per node. This yields logarithmic time per operation.

Neutral Tag

Explanation: Composing any tag with (1,0) leaves it unchanged. Initialize all lazy tags to this identity.

Assign Overwrites

Explanation: Composing an assignment after any prior tag discards the prior effect, because 0 annihilates the old multiplier and addend.

Complexity Analysis

Let n be the array length. The segment tree has O(n) nodes (at most 4n in a flat vector implementation). Each update or query touches at most O(log n) nodes because recursion only proceeds into branches that intersect the query/update range. At each visited node, work is O(1): we either update a sum using S' = a S + b |I| and compose lazy tags, or we push a tag to children and proceed. Therefore, both range updates (add, multiply, assign, or any affine combination) and range queries (sum) run in O(log n) time. Space complexity is O(n) for storing node aggregates, lazy tags, and optionally node lengths. If you store lengths explicitly per node, you use a small constant factor more memory; otherwise you can compute length from recursion parameters. In modular variants, arithmetic operations should be reduced after each multiplication/addition to keep values in range; the complexity remains unchanged. The critical hidden constant is small: two or three integer operations per visited node, so performance is suitable for 1800–2200 CF tasks with up to 2e5 operations. The main pitfalls that can accidentally inflate complexity are failing to push before descending (leading to extra recursion or repeated updates) and writing non-tail-recursive traversals that repeatedly visit the same nodes. With correct lazy propagation, the amortized complexity per operation stays O(log n), and the tree builds in O(n).

Code Examples

Range Add + Range Assign + Range Sum (two-tag design)
1#include <bits/stdc++.h>
2using namespace std;
3
4struct Node {
5    long long sum = 0; // Sum over the interval
6    int len = 0;       // Length of the interval
7};
8
9struct Tag {
10    bool has_set = false; // whether an assignment is pending
11    long long set_val = 0; // value to assign if has_set
12    long long add = 0;     // pending addition
13};
14
15struct SegTree {
16    int n;
17    vector<Node> st;
18    vector<Tag> lazy;
19
20    SegTree(const vector<long long>& a) {
21        n = (int)a.size();
22        st.resize(4*n);
23        lazy.resize(4*n);
24        build(1, 0, n-1, a);
25    }
26
27    void build(int p, int l, int r, const vector<long long>& a) {
28        st[p].len = r - l + 1;
29        if (l == r) {
30            st[p].sum = a[l];
31            return;
32        }
33        int m = (l + r) >> 1;
34        build(p<<1, l, m, a);
35        build(p<<1|1, m+1, r, a);
36        pull(p);
37    }
38
39    // Apply an assign to node p
40    void apply_assign(int p, long long v) {
41        st[p].sum = v * 1LL * st[p].len; // S' = v * len
42        lazy[p].has_set = true;
43        lazy[p].set_val = v;
44        lazy[p].add = 0; // assignment erases pending add
45    }
46
47    // Apply an add to node p
48    void apply_add(int p, long long d) {
49        st[p].sum += d * 1LL * st[p].len; // S' = S + d*len
50        if (lazy[p].has_set) {
51            // If an assignment is pending, it becomes assignment to (set_val + d)
52            lazy[p].set_val += d;
53        } else {
54            lazy[p].add += d;
55        }
56    }
57
58    void push(int p) {
59        if (lazy[p].has_set) {
60            apply_assign(p<<1, lazy[p].set_val);
61            apply_assign(p<<1|1, lazy[p].set_val);
62            lazy[p].has_set = false;
63        }
64        if (lazy[p].add != 0) {
65            apply_add(p<<1, lazy[p].add);
66            apply_add(p<<1|1, lazy[p].add);
67            lazy[p].add = 0;
68        }
69    }
70
71    void pull(int p) {
72        st[p].sum = st[p<<1].sum + st[p<<1|1].sum;
73    }
74
75    void range_assign(int p, int l, int r, int ql, int qr, long long v) {
76        if (qr < l || r < ql) return;
77        if (ql <= l && r <= qr) {
78            apply_assign(p, v);
79            return;
80        }
81        push(p);
82        int m = (l + r) >> 1;
83        range_assign(p<<1, l, m, ql, qr, v);
84        range_assign(p<<1|1, m+1, r, ql, qr, v);
85        pull(p);
86    }
87
88    void range_add(int p, int l, int r, int ql, int qr, long long d) {
89        if (qr < l || r < ql) return;
90        if (ql <= l && r <= qr) {
91            apply_add(p, d);
92            return;
93        }
94        push(p);
95        int m = (l + r) >> 1;
96        range_add(p<<1, l, m, ql, qr, d);
97        range_add(p<<1|1, m+1, r, ql, qr, d);
98        pull(p);
99    }
100
101    long long range_sum(int p, int l, int r, int ql, int qr) {
102        if (qr < l || r < ql) return 0LL;
103        if (ql <= l && r <= qr) return st[p].sum;
104        push(p);
105        int m = (l + r) >> 1;
106        return range_sum(p<<1, l, m, ql, qr) + range_sum(p<<1|1, m+1, r, ql, qr);
107    }
108
109    // Public wrappers
110    void assign_range(int l, int r, long long v) { range_assign(1, 0, n-1, l, r, v); }
111    void add_range(int l, int r, long long d) { range_add(1, 0, n-1, l, r, d); }
112    long long sum_range(int l, int r) { return range_sum(1, 0, n-1, l, r); }
113};
114
115int main() {
116    ios::sync_with_stdio(false);
117    cin.tie(nullptr);
118
119    vector<long long> a = {1, 2, 3, 4, 5};
120    SegTree st(a);
121
122    cout << st.sum_range(0, 4) << "\n"; // 15
123    st.add_range(1, 3, 10);              // [1,12,13,14,5]
124    cout << st.sum_range(0, 4) << "\n"; // 45
125    st.assign_range(2, 4, 7);            // [1,12,7,7,7]
126    cout << st.sum_range(0, 4) << "\n"; // 34
127    st.add_range(0, 4, 1);               // [2,13,8,8,8]
128    cout << st.sum_range(1, 3) << "\n"; // 29
129    return 0;
130}
131

This implementation supports range add and range assign with range sum queries. We keep two lazy components: a boolean assignment with its value, and a pending addition. Assignment erases any pending add; adding on top of an assignment increases the assignment value. Push applies the parent’s pending tags to its children before descending.

Time: O(log n) per update/querySpace: O(n)
Range Multiply + Range Add + Range Sum under Modulo (affine tags)
1#include <bits/stdc++.h>
2using namespace std;
3
4static const long long MOD = 998244353LL; // change as needed
5
6struct Node {
7    long long sum = 0; // sum modulo MOD
8    int len = 0;
9};
10
11struct Tag { // affine f(x) = a*x + b (mod MOD)
12    long long a = 1, b = 0; // identity by default
13};
14
15long long norm(long long x) { x %= MOD; if (x < 0) x += MOD; return x; }
16
17Tag compose(const Tag& f, const Tag& g) {
18    // return f ∘ g: apply g first, then f
19    Tag h;
20    h.a = (f.a * g.a) % MOD;
21    h.b = ( (f.a * g.b) + f.b ) % MOD;
22    return h;
23}
24
25struct SegTree {
26    int n;
27    vector<Node> st;
28    vector<Tag> lazy;
29
30    SegTree(const vector<long long>& a) {
31        n = (int)a.size();
32        st.resize(4*n);
33        lazy.assign(4*n, Tag());
34        build(1, 0, n-1, a);
35    }
36
37    void build(int p, int l, int r, const vector<long long>& a) {
38        st[p].len = r - l + 1;
39        if (l == r) {
40            st[p].sum = norm(a[l]);
41            return;
42        }
43        int m = (l + r) >> 1;
44        build(p<<1, l, m, a);
45        build(p<<1|1, m+1, r, a);
46        pull(p);
47    }
48
49    void apply(int p, const Tag& f) {
50        // S' = a*S + b*len
51        st[p].sum = ( (f.a * st[p].sum) + (f.b * st[p].len) ) % MOD;
52        lazy[p] = compose(f, lazy[p]); // new after old: f ∘ lazy[p]
53    }
54
55    void push(int p) {
56        if (lazy[p].a != 1 || lazy[p].b != 0) {
57            apply(p<<1, lazy[p]);
58            apply(p<<1|1, lazy[p]);
59            lazy[p] = Tag(); // reset to identity
60        }
61    }
62
63    void pull(int p) {
64        st[p].sum = (st[p<<1].sum + st[p<<1|1].sum) % MOD;
65    }
66
67    void range_apply(int p, int l, int r, int ql, int qr, const Tag& f) {
68        if (qr < l || r < ql) return;
69        if (ql <= l && r <= qr) { apply(p, f); return; }
70        push(p);
71        int m = (l + r) >> 1;
72        range_apply(p<<1, l, m, ql, qr, f);
73        range_apply(p<<1|1, m+1, r, ql, qr, f);
74        pull(p);
75    }
76
77    long long range_sum(int p, int l, int r, int ql, int qr) {
78        if (qr < l || r < ql) return 0LL;
79        if (ql <= l && r <= qr) return st[p].sum;
80        push(p);
81        int m = (l + r) >> 1;
82        return (range_sum(p<<1, l, m, ql, qr) + range_sum(p<<1|1, m+1, r, ql, qr)) % MOD;
83    }
84
85    // Convenience wrappers
86    void add_range(int l, int r, long long d) { Tag f; f.a = 1; f.b = norm(d); range_apply(1,0,n-1,l,r,f); }
87    void mul_range(int l, int r, long long m) { Tag f; f.a = norm(m); f.b = 0; range_apply(1,0,n-1,l,r,f); }
88    void assign_range(int l, int r, long long c) { Tag f; f.a = 0; f.b = norm(c); range_apply(1,0,n-1,l,r,f); }
89    long long sum_range(int l, int r) { return range_sum(1,0,n-1,l,r); }
90};
91
92int main() {
93    ios::sync_with_stdio(false);
94    cin.tie(nullptr);
95
96    vector<long long> a = {1, 2, 3, 4, 5};
97    SegTree st(a);
98
99    cout << st.sum_range(0, 4) << "\n"; // 15
100    st.mul_range(0, 4, 2);                // [2,4,6,8,10]
101    cout << st.sum_range(0, 4) << "\n"; // 30
102    st.add_range(1, 3, 3);                // [2,7,9,11,10]
103    cout << st.sum_range(1, 3) << "\n"; // 27
104    st.assign_range(2, 4, 7);             // [2,7,7,7,7]
105    cout << st.sum_range(0, 4) << "\n"; // 30
106    st.add_range(0, 2, 1);                // [3,8,8,7,7]
107    cout << st.sum_range(0, 2) << "\n"; // 19
108    return 0;
109}
110

This is a unified affine solution with modulo arithmetic. Updates are encoded as tags (a, b). The compose function returns f ∘ g. The apply function updates the node’s sum in O(1) via S' = aS + b|I| and merges lazy tags via composition. Assignment is just (a=0, b=c), which naturally overrides older tags.

Time: O(log n) per update/querySpace: O(n)
Unified Add + Multiply + Assign using only affine tags (no special flags)
1#include <bits/stdc++.h>
2using namespace std;
3
4struct Node { long long sum = 0; int len = 0; };
5struct Tag { long long a = 1, b = 0; }; // f(x) = a*x + b
6
7// Compose f after g: h = f ∘ g
8static inline Tag compose(const Tag& f, const Tag& g) {
9    __int128 A = (__int128)f.a * g.a;
10    __int128 B = (__int128)f.a * g.b + f.b;
11    Tag h; h.a = (long long)A; h.b = (long long)B; // no modulo; beware overflow in practice
12    return h;
13}
14
15struct SegTree {
16    int n; vector<Node> st; vector<Tag> lazy;
17    SegTree(const vector<long long>& a) { n=(int)a.size(); st.resize(4*n); lazy.assign(4*n, Tag()); build(1,0,n-1,a); }
18
19    void build(int p, int l, int r, const vector<long long>& a) {
20        st[p].len = r-l+1;
21        if(l==r){ st[p].sum=a[l]; return; }
22        int m=(l+r)>>1; build(p<<1,l,m,a); build(p<<1|1,m+1,r,a); pull(p);
23    }
24
25    void apply(int p, const Tag& f){
26        st[p].sum = f.a * st[p].sum + f.b * st[p].len; // may overflow without mod
27        lazy[p] = compose(f, lazy[p]);
28    }
29
30    void push(int p){
31        if(lazy[p].a!=1 || lazy[p].b!=0){
32            apply(p<<1, lazy[p]);
33            apply(p<<1|1, lazy[p]);
34            lazy[p] = Tag();
35        }
36    }
37
38    void pull(int p){ st[p].sum = st[p<<1].sum + st[p<<1|1].sum; }
39
40    void range_apply(int p,int l,int r,int ql,int qr,const Tag& f){
41        if(qr<l||r<ql) return; if(ql<=l&&r<=qr){ apply(p,f); return; }
42        push(p); int m=(l+r)>>1; range_apply(p<<1,l,m,ql,qr,f); range_apply(p<<1|1,m+1,r,ql,qr,f); pull(p);
43    }
44
45    long long range_sum(int p,int l,int r,int ql,int qr){
46        if(qr<l||r<ql) return 0; if(ql<=l&&r<=qr) return st[p].sum; push(p); int m=(l+r)>>1;
47        return range_sum(p<<1,l,m,ql,qr)+range_sum(p<<1|1,m+1,r,ql,qr);
48    }
49
50    // public wrappers
51    void add_range(int l,int r,long long d){ Tag f{1,d}; range_apply(1,0,n-1,l,r,f); }
52    void mul_range(int l,int r,long long m){ Tag f{m,0}; range_apply(1,0,n-1,l,r,f); }
53    void assign_range(int l,int r,long long c){ Tag f{0,c}; range_apply(1,0,n-1,l,r,f); }
54    long long sum_range(int l,int r){ return range_sum(1,0,n-1,l,r); }
55};
56
57int main(){
58    ios::sync_with_stdio(false); cin.tie(nullptr);
59    vector<long long> a(8); iota(a.begin(), a.end(), 1); // [1..8]
60    SegTree st(a);
61    st.add_range(0,7,5);          // +5 everywhere
62    st.mul_range(2,5,3);          // *3 on [2..5]
63    st.assign_range(4,7,10);      // set [4..7] to 10
64    cout << st.sum_range(0,7) << "\n"; // check total
65    cout << st.sum_range(2,5) << "\n"; // check middle segment
66    return 0;
67}
68

This version uses purely affine tags without any special-case flags, showing how assignment is represented as (a=0, b=c). It demonstrates composition order by always setting lazy[p] = f ∘ lazy[p] when applying a new update f to node p. Note: without modulo, you must ensure values do not overflow.

Time: O(log n) per update/querySpace: O(n)