SyntaxPilot
Courses/Competitive Programming/Lesson 61
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 61 of 90

Segment tree with lazy propagation

queued

These are the notes for Competitive Programming episode 61. A segment tree stores, for every block of a recursive halving of the array, an aggregate of that block (a sum, a maximum…); any range [l, r] is the union of at most about 2 log₂ n whole blocks, so a range query costs O(log n). Lazy propagation makes range updates O(log n) too: a fully covered block gets its aggregate updated at once and a tag remembering what its children still owe, and the tag is pushed down whenever we go below that block. Festival Lights (range add, range sum, n, q ≤ 5 · 10^5) is Time Limit Exceeded with loops and with leaf-by-leaf updates; forgetting the push in the query prints 5 where 25 is right. Skyline Renovation (range assign, range max) shows that "tag = 0 means no tag" is wrong when 0 is a real value (8 instead of 0). Stress tests pass. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The real-life hook

Every room on floor 2 of a hostel gets a mess refund of ₹100. The warden doesn't visit forty rooms: she pins one notice on the floor. The floor's total refund is known at once (₹100 × rooms). Only when someone needs the exact balance of one wing does she copy the notice onto that wing's doors and take it off the floor. That is a lazy tag and a push.

The segment tree in one page

  • Node 1 covers [1, n]; node v covering [l, r] has children 2v ([l, m]) and 2v + 1 ([m + 1, r]), m = ⌊(l + r) / 2⌋.
  • Depth ≈ log₂ n; arrays of size 4n are always enough.
  • Query [ql, qr] at node v: block inside → use it; block outside → neutral value (0 for sums, −∞ for max); otherwise combine the two children. At most four nodes per level are visited: O(log n).

Example on 8 values (block sums shown):

              [1,8] 36
        [1,4] 10        [5,8] 26
   [1,2] 3  [3,4] 7  [5,6] 11  [7,8] 15
   1   2    3   4    5    6    7    8

sum[3, 8] = node [3,4] + node [5,8] = 7 + 26 = 33.

Problem I1 · Festival Lights

(Written for this course, in the style of a classic Codeforces data-structure problem.)

  • Input: n q (n, q ≤ 5 · 10^5), the brightnesses a[1..n], then q operations: 1 l r x (add x to a[l..r], |x| ≤ 10^9) or 2 l r (print a[l] + … + a[r]).
  • Output: one sum per type-2 operation (long long).
5 6
1 2 3 4 5
2 1 5
1 1 3 10
2 2 3
1 2 5 -1
2 1 5
2 4 4

Answers: 15 25 41 3.

The obvious attempt: loop over the range (TLE)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, q;
ll a[500001];

void rangeAdd(int l, int r, ll x) { for (int i = l; i <= r; i++) a[i] += x; }   // every bulb
ll rangeSum(int l, int r) {
    ll s = 0;
    for (int i = l; i <= r; i++) s += a[i];
    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    while (q--) {
        int type, l, r;
        cin >> type >> l >> r;
        if (type == 1) {
            ll x;
            cin >> x;
            rangeAdd(l, r, x);
        } else cout << rangeSum(l, r) << "\n";
    }
}
15
25
41
3

Worst case: n = q = 5 · 10^5 and every operation covers almost the whole street: about 2.5 · 10^11 steps.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, q;
ll a[500001];

void rangeAdd(int l, int r, ll x) { for (int i = l; i <= r; i++) a[i] += x; }   // every bulb
ll rangeSum(int l, int r) {
    ll s = 0;
    for (int i = l; i <= r; i++) s += a[i];
    return s;
}

int main() {
    n = q = 500000;                          // the whole festival street
    mt19937 rng(61);
    for (int i = 1; i <= n; i++) a[i] = rng() % 1000;
    ll check = 0;
    for (int i = 0; i < q; i++) {             // almost the whole street every time
        int l = rng() % 10 + 1, r = n - rng() % 10;
        if (i % 2 == 0) rangeAdd(l, r, rng() % 1000);
        else check ^= rangeSum(l, r);
    }
    cout << check << "\n";
}
Time Limit Exceeded

A segment tree without tags (TLE)

A segment tree answers the sums fast, but if a range add updates every leaf one by one, each operation costs O((r − l + 1) log n), even worse than the loop:

void rangeAdd(int l, int r, ll x) {          // one leaf at a time
    for (int i = l; i <= r; i++) update(1, 1, n, i, i, x);
}
Time Limit Exceeded

Lazy tags

  • sum[v] is always the true sum of v's block, including every tag at v or above that has reached v.
  • lz[v] is an addition that v's children have not received yet.
  • apply(v, l, r, x): sum[v] += x · (r − l + 1), lz[v] += x.
  • push(v, l, r): apply lz[v] to both children, then lz[v] = 0.
  • Golden rule: before going below a node (in update and in query), push.
  • An update stops at fully covered blocks: O(log n) nodes are touched, exactly like a query.

The bug: no push in the query

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, q;
ll a[500001], sum[2000004], lz[2000004];   // lz[v] = add still owed to v's children

void build(int v, int l, int r) {
    if (l == r) { sum[v] = a[l]; return; }
    int m = (l + r) / 2;
    build(2 * v, l, m);
    build(2 * v + 1, m + 1, r);
    sum[v] = sum[2 * v] + sum[2 * v + 1];
}
void apply(int v, int l, int r, ll x) {      // the whole block gets +x
    sum[v] += x * (r - l + 1);
    lz[v] += x;
}
void push(int v, int l, int r) {             // pass the notice down
    if (lz[v] == 0) return;
    int m = (l + r) / 2;
    apply(2 * v, l, m, lz[v]);
    apply(2 * v + 1, m + 1, r, lz[v]);
    lz[v] = 0;
}
void update(int v, int l, int r, int ql, int qr, ll x) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) { apply(v, l, r, x); return; }   // fully inside: stop here
    push(v, l, r);
    int m = (l + r) / 2;
    update(2 * v, l, m, ql, qr, x);
    update(2 * v + 1, m + 1, r, ql, qr, x);
    sum[v] = sum[2 * v] + sum[2 * v + 1];
}
ll query(int v, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return 0;
    if (ql <= l && r <= qr) return sum[v];
    int m = (l + r) / 2;
    return query(2 * v, l, m, ql, qr) + query(2 * v + 1, m + 1, r, ql, qr);
}
void rangeAdd(int l, int r, ll x) { update(1, 1, n, l, r, x); }
ll rangeSum(int l, int r) { return query(1, 1, n, l, r); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while (q--) {
        int type, l, r;
        cin >> type >> l >> r;
        if (type == 1) {
            ll x;
            cin >> x;
            rangeAdd(l, r, x);
        } else cout << rangeSum(l, r) << "\n";
    }
}
15
5
41
4

Adding 10 to [1, 3] tags the block [1, 3]. The query [2, 3] goes below that block without pushing and reads the children's old sums (2 + 3 = 5). The last answer is wrong for the same reason. With the push:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, q;
ll a[500001], sum[2000004], lz[2000004];   // lz[v] = add still owed to v's children

void build(int v, int l, int r) {
    if (l == r) { sum[v] = a[l]; return; }
    int m = (l + r) / 2;
    build(2 * v, l, m);
    build(2 * v + 1, m + 1, r);
    sum[v] = sum[2 * v] + sum[2 * v + 1];
}
void apply(int v, int l, int r, ll x) {      // the whole block gets +x
    sum[v] += x * (r - l + 1);
    lz[v] += x;
}
void push(int v, int l, int r) {             // pass the notice down
    if (lz[v] == 0) return;
    int m = (l + r) / 2;
    apply(2 * v, l, m, lz[v]);
    apply(2 * v + 1, m + 1, r, lz[v]);
    lz[v] = 0;
}
void update(int v, int l, int r, int ql, int qr, ll x) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) { apply(v, l, r, x); return; }   // fully inside: stop here
    push(v, l, r);
    int m = (l + r) / 2;
    update(2 * v, l, m, ql, qr, x);
    update(2 * v + 1, m + 1, r, ql, qr, x);
    sum[v] = sum[2 * v] + sum[2 * v + 1];
}
ll query(int v, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return 0;
    if (ql <= l && r <= qr) return sum[v];
    push(v, l, r);                           // children must be up to date
    int m = (l + r) / 2;
    return query(2 * v, l, m, ql, qr) + query(2 * v + 1, m + 1, r, ql, qr);
}
void rangeAdd(int l, int r, ll x) { update(1, 1, n, l, r, x); }
ll rangeSum(int l, int r) { return query(1, 1, n, l, r); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while (q--) {
        int type, l, r;
        cin >> type >> l >> r;
        if (type == 1) {
            ll x;
            cin >> x;
            rangeAdd(l, r, x);
        } else cout << rangeSum(l, r) << "\n";
    }
}
15
25
41
3

A single bulb (7, then +5):

7
12

The worst case (the answers are xor-ed into one check number):

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, q;
ll a[500001], sum[2000004], lz[2000004];   // lz[v] = add still owed to v's children

void build(int v, int l, int r) {
    if (l == r) { sum[v] = a[l]; return; }
    int m = (l + r) / 2;
    build(2 * v, l, m);
    build(2 * v + 1, m + 1, r);
    sum[v] = sum[2 * v] + sum[2 * v + 1];
}
void apply(int v, int l, int r, ll x) {      // the whole block gets +x
    sum[v] += x * (r - l + 1);
    lz[v] += x;
}
void push(int v, int l, int r) {             // pass the notice down
    if (lz[v] == 0) return;
    int m = (l + r) / 2;
    apply(2 * v, l, m, lz[v]);
    apply(2 * v + 1, m + 1, r, lz[v]);
    lz[v] = 0;
}
void update(int v, int l, int r, int ql, int qr, ll x) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) { apply(v, l, r, x); return; }   // fully inside: stop here
    push(v, l, r);
    int m = (l + r) / 2;
    update(2 * v, l, m, ql, qr, x);
    update(2 * v + 1, m + 1, r, ql, qr, x);
    sum[v] = sum[2 * v] + sum[2 * v + 1];
}
ll query(int v, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return 0;
    if (ql <= l && r <= qr) return sum[v];
    push(v, l, r);                           // children must be up to date
    int m = (l + r) / 2;
    return query(2 * v, l, m, ql, qr) + query(2 * v + 1, m + 1, r, ql, qr);
}
void rangeAdd(int l, int r, ll x) { update(1, 1, n, l, r, x); }
ll rangeSum(int l, int r) { return query(1, 1, n, l, r); }

int main() {
    n = q = 500000;                          // the whole festival street
    mt19937 rng(61);
    for (int i = 1; i <= n; i++) a[i] = rng() % 1000;
    build(1, 1, n);
    ll check = 0;
    for (int i = 0; i < q; i++) {             // almost the whole street every time
        int l = rng() % 10 + 1, r = n - rng() % 10;
        if (i % 2 == 0) rangeAdd(l, r, rng() % 1000);
        else check ^= rangeSum(l, r);
    }
    cout << check << "\n";
}
9741235287882

Stress test against the brute force

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, q;
ll a[500001], sum[2000004], lz[2000004];   // lz[v] = add still owed to v's children

void build(int v, int l, int r) {
    if (l == r) { sum[v] = a[l]; return; }
    int m = (l + r) / 2;
    build(2 * v, l, m);
    build(2 * v + 1, m + 1, r);
    sum[v] = sum[2 * v] + sum[2 * v + 1];
}
void apply(int v, int l, int r, ll x) {      // the whole block gets +x
    sum[v] += x * (r - l + 1);
    lz[v] += x;
}
void push(int v, int l, int r) {             // pass the notice down
    if (lz[v] == 0) return;
    int m = (l + r) / 2;
    apply(2 * v, l, m, lz[v]);
    apply(2 * v + 1, m + 1, r, lz[v]);
    lz[v] = 0;
}
void update(int v, int l, int r, int ql, int qr, ll x) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) { apply(v, l, r, x); return; }   // fully inside: stop here
    push(v, l, r);
    int m = (l + r) / 2;
    update(2 * v, l, m, ql, qr, x);
    update(2 * v + 1, m + 1, r, ql, qr, x);
    sum[v] = sum[2 * v] + sum[2 * v + 1];
}
ll query(int v, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return 0;
    if (ql <= l && r <= qr) return sum[v];
    push(v, l, r);                           // children must be up to date
    int m = (l + r) / 2;
    return query(2 * v, l, m, ql, qr) + query(2 * v + 1, m + 1, r, ql, qr);
}
void rangeAdd(int l, int r, ll x) { update(1, 1, n, l, r, x); }
ll rangeSum(int l, int r) { return query(1, 1, n, l, r); }

int main() {
    mt19937 rng(61);
    for (int t = 1; t <= 500; t++) {
        n = rng() % 12 + 1;
        vector<ll> b(n + 1);
        for (int i = 1; i <= n; i++) b[i] = a[i] = rng() % 20;
        fill(lz, lz + 4 * n + 4, 0);
        build(1, 1, n);
        for (int k = 0; k < 30; k++) {
            int l = rng() % n + 1, r = rng() % n + 1;
            if (l > r) swap(l, r);
            if (rng() % 2) {
                ll x = (ll)(rng() % 21) - 10;
                rangeAdd(l, r, x);
                for (int i = l; i <= r; i++) b[i] += x;
            } else {
                ll s = 0;
                for (int i = l; i <= r; i++) s += b[i];
                if (rangeSum(l, r) != s) { cout << "mismatch on test " << t; return 0; }
            }
        }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Problem I2 · Skyline Renovation

(Written for this course.)

  • Input: n q, heights a[1..n], then 1 l r h (set every building in [l, r] to height h, 0 ≤ h; h = 0 = demolished) or 2 l r (print the tallest in [l, r]).
6 6
5 3 8 6 2 1
2 1 6
1 1 3 0
2 1 6
2 2 3
1 2 5 7
2 6 6

Answers: 8 6 0 1.

The node stores the maximum; the tag means "set everything below me to h". apply(v, h) sets mx[v] = h and tag[v] = h. Two assignments compose by replacement (the newer wins), unlike additions, which add up.

The bug: tag 0 means "no tag"

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, q;
ll a[500001], mx[2000004], tag[2000004];   // tag[v] = height to set below v

void build(int v, int l, int r) {
    tag[v] = 0;
    if (l == r) { mx[v] = a[l]; return; }
    int m = (l + r) / 2;
    build(2 * v, l, m);
    build(2 * v + 1, m + 1, r);
    mx[v] = max(mx[2 * v], mx[2 * v + 1]);
}
void apply(int v, ll h) { mx[v] = h; tag[v] = h; }   // the whole block becomes h
void push(int v) {
    if (tag[v] == 0) return;                 // 0 = no tag?
    apply(2 * v, tag[v]);
    apply(2 * v + 1, tag[v]);
    tag[v] = 0;
}
void update(int v, int l, int r, int ql, int qr, ll h) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) { apply(v, h); return; }
    push(v);
    int m = (l + r) / 2;
    update(2 * v, l, m, ql, qr, h);
    update(2 * v + 1, m + 1, r, ql, qr, h);
    mx[v] = max(mx[2 * v], mx[2 * v + 1]);
}
ll query(int v, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return LLONG_MIN;
    if (ql <= l && r <= qr) return mx[v];
    push(v);
    int m = (l + r) / 2;
    return max(query(2 * v, l, m, ql, qr), query(2 * v + 1, m + 1, r, ql, qr));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while (q--) {
        int type, l, r;
        cin >> type >> l >> r;
        if (type == 1) {
            ll h;
            cin >> h;
            update(1, 1, n, l, r, h);
        } else cout << query(1, 1, n, l, r) << "\n";
    }
}
8
6
8
1

Demolishing [1, 3] stores tag 0 at that block; push thinks there is no tag, so the children keep their old heights, and the tallest of [2, 3] is reported as 8. A value that can never be data fixes it:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, q;
ll a[500001], mx[2000004], tag[2000004];   // tag[v] = height to set below v
const ll NONE = LLONG_MIN;                // "no tag": a height can never be this

void build(int v, int l, int r) {
    tag[v] = NONE;
    if (l == r) { mx[v] = a[l]; return; }
    int m = (l + r) / 2;
    build(2 * v, l, m);
    build(2 * v + 1, m + 1, r);
    mx[v] = max(mx[2 * v], mx[2 * v + 1]);
}
void apply(int v, ll h) { mx[v] = h; tag[v] = h; }   // the whole block becomes h
void push(int v) {
    if (tag[v] == NONE) return;
    apply(2 * v, tag[v]);
    apply(2 * v + 1, tag[v]);
    tag[v] = NONE;
}
void update(int v, int l, int r, int ql, int qr, ll h) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) { apply(v, h); return; }
    push(v);
    int m = (l + r) / 2;
    update(2 * v, l, m, ql, qr, h);
    update(2 * v + 1, m + 1, r, ql, qr, h);
    mx[v] = max(mx[2 * v], mx[2 * v + 1]);
}
ll query(int v, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return LLONG_MIN;
    if (ql <= l && r <= qr) return mx[v];
    push(v);
    int m = (l + r) / 2;
    return max(query(2 * v, l, m, ql, qr), query(2 * v + 1, m + 1, r, ql, qr));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while (q--) {
        int type, l, r;
        cin >> type >> l >> r;
        if (type == 1) {
            ll h;
            cin >> h;
            update(1, 1, n, l, r, h);
        } else cout << query(1, 1, n, l, r) << "\n";
    }
}
8
6
0
1
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, q;
ll a[500001], mx[2000004], tag[2000004];   // tag[v] = height to set below v
const ll NONE = LLONG_MIN;                // "no tag": a height can never be this

void build(int v, int l, int r) {
    tag[v] = NONE;
    if (l == r) { mx[v] = a[l]; return; }
    int m = (l + r) / 2;
    build(2 * v, l, m);
    build(2 * v + 1, m + 1, r);
    mx[v] = max(mx[2 * v], mx[2 * v + 1]);
}
void apply(int v, ll h) { mx[v] = h; tag[v] = h; }   // the whole block becomes h
void push(int v) {
    if (tag[v] == NONE) return;
    apply(2 * v, tag[v]);
    apply(2 * v + 1, tag[v]);
    tag[v] = NONE;
}
void update(int v, int l, int r, int ql, int qr, ll h) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) { apply(v, h); return; }
    push(v);
    int m = (l + r) / 2;
    update(2 * v, l, m, ql, qr, h);
    update(2 * v + 1, m + 1, r, ql, qr, h);
    mx[v] = max(mx[2 * v], mx[2 * v + 1]);
}
ll query(int v, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return LLONG_MIN;
    if (ql <= l && r <= qr) return mx[v];
    push(v);
    int m = (l + r) / 2;
    return max(query(2 * v, l, m, ql, qr), query(2 * v + 1, m + 1, r, ql, qr));
}

int main() {
    mt19937 rng(61);
    for (int t = 1; t <= 500; t++) {
        n = rng() % 12 + 1;
        vector<ll> b(n + 1);
        for (int i = 1; i <= n; i++) b[i] = a[i] = rng() % 5;
        build(1, 1, n);
        for (int k = 0; k < 30; k++) {
            int l = rng() % n + 1, r = rng() % n + 1;
            if (l > r) swap(l, r);
            if (rng() % 2) {
                ll h = rng() % 5;                   // 0 included
                update(1, 1, n, l, r, h);
                for (int i = l; i <= r; i++) b[i] = h;
            } else if (query(1, 1, n, l, r) != *max_element(b.begin() + l, b.begin() + r + 1)) {
                cout << "mismatch on test " << t;
                return 0;
            }
        }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Complexity vs the constraints

Method Update Query Verdict at n, q = 5 · 10^5
loops O(n) O(n) TLE
segment tree, leaf by leaf O(n log n) O(log n) TLE
lazy segment tree O(log n) O(log n) accepted
memory 4n sums + 4n tags 2 · 16 MB for long long

Common mistakes (and the real outputs)

Mistake What you see Why Fix
loop over the range Time Limit Exceeded O(n) per operation segment tree
range add leaf by leaf Time Limit Exceeded every leaf updated lazy tags
no push in the query 5 (expected 25) children are stale push before going down
tag 0 means "no tag" 8 (expected 0) 0 is a real height NONE = LLONG_MIN
sum[v] += x wrong sums forgot the block length x · (r − l + 1)
arrays of size 2n Runtime Error / garbage indexes reach ≈ 4n size 4n
add and assign tags mixed in the wrong order wrong sums a set must wipe older adds see homework 3
int sums overflow up to 5 · 10^5 · 10^9 long long

Mini project

Write a generic lazy segment tree: template<class S, class F> struct LazySeg with op(S, S), e(), mapping(F, S), composition(F, F), id(). Instantiate it for (sum, add), (max, assign) and (sum, set-then-add), and stress-test each against loops with negative numbers and zeros.

Practice

These are the four homework problems from the episode. Every answer below came from a compiled C++ program (g++ -O2 -std=c++17); homework 3 and 4 were also checked against brute force on 150 random cases.

1. Range add, range minimum.

Solution

Adding x to every value adds x to the minimum, so apply(v, x): mn[v] += x, lz[v] += x (no block length here). Sample: 4 2 6 1 3, min of all, add −4 to [3, 5], min of [3, 5], add −10 to [1, 2], min of all.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, q;
ll a[500001], mn[2000004], lz[2000004];   // range add, range minimum

void build(int v, int l, int r) {
    if (l == r) { mn[v] = a[l]; return; }
    int m = (l + r) / 2;
    build(2 * v, l, m);
    build(2 * v + 1, m + 1, r);
    mn[v] = min(mn[2 * v], mn[2 * v + 1]);
}
void apply(int v, ll x) { mn[v] += x; lz[v] += x; }   // adding x to all: the min also grows by x
void push(int v) {
    if (lz[v]) apply(2 * v, lz[v]), apply(2 * v + 1, lz[v]), lz[v] = 0;
}
void update(int v, int l, int r, int ql, int qr, ll x) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) { apply(v, x); return; }
    push(v);
    int m = (l + r) / 2;
    update(2 * v, l, m, ql, qr, x);
    update(2 * v + 1, m + 1, r, ql, qr, x);
    mn[v] = min(mn[2 * v], mn[2 * v + 1]);
}
ll query(int v, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return LLONG_MAX;
    if (ql <= l && r <= qr) return mn[v];
    push(v);
    int m = (l + r) / 2;
    return min(query(2 * v, l, m, ql, qr), query(2 * v + 1, m + 1, r, ql, qr));
}

int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while (q--) {
        int type, l, r;
        cin >> type >> l >> r;
        if (type == 1) { ll x; cin >> x; update(1, 1, n, l, r, x); }
        else cout << query(1, 1, n, l, r) << "\n";
    }
}
1
-3
-8

2. Range assign, range sum.

Solution

apply(v, l, r, x): sum[v] = x · (r − l + 1), tag[v] = x, with NONE for "no tag" (assigning 0 is allowed).

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll NONE = LLONG_MIN;
int n, q;
ll a[500001], sum[2000004], tag[2000004];   // range assign, range sum

void apply(int v, int l, int r, ll x) { sum[v] = x * (r - l + 1); tag[v] = x; }
void build(int v, int l, int r) {
    tag[v] = NONE;
    if (l == r) { sum[v] = a[l]; return; }
    int m = (l + r) / 2;
    build(2 * v, l, m);
    build(2 * v + 1, m + 1, r);
    sum[v] = sum[2 * v] + sum[2 * v + 1];
}
void push(int v, int l, int r) {
    if (tag[v] == NONE) return;
    int m = (l + r) / 2;
    apply(2 * v, l, m, tag[v]);
    apply(2 * v + 1, m + 1, r, tag[v]);
    tag[v] = NONE;
}
void update(int v, int l, int r, int ql, int qr, ll x) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) { apply(v, l, r, x); return; }
    push(v, l, r);
    int m = (l + r) / 2;
    update(2 * v, l, m, ql, qr, x);
    update(2 * v + 1, m + 1, r, ql, qr, x);
    sum[v] = sum[2 * v] + sum[2 * v + 1];
}
ll query(int v, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return 0;
    if (ql <= l && r <= qr) return sum[v];
    push(v, l, r);
    int m = (l + r) / 2;
    return query(2 * v, l, m, ql, qr) + query(2 * v + 1, m + 1, r, ql, qr);
}

int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while (q--) {
        int type, l, r;
        cin >> type >> l >> r;
        if (type == 1) { ll x; cin >> x; update(1, 1, n, l, r, x); }
        else cout << query(1, 1, n, l, r) << "\n";
    }
}
15
6
21

3. Both add and assign on one tree (1 l r x add, 2 l r x set, 3 l r sum).

Solution

A tag is the pair (set, add) meaning "first set everything to set (if any), then add add". Applying a set replaces the whole tag (older adds are wiped); applying an add only increases add. Push the set first, then the add.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// Tag = (set, add): "first set everything to `set` (if any), then add `add`". Range sum.
const ll NONE = LLONG_MIN;
int n, q;
ll a[500001], sum[2000004], st[2000004], ad[2000004];

void applySet(int v, int l, int r, ll x) { sum[v] = x * (r - l + 1); st[v] = x; ad[v] = 0; }   // a set wipes older adds
void applyAdd(int v, int l, int r, ll x) { sum[v] += x * (r - l + 1); ad[v] += x; }
void build(int v, int l, int r) {
    st[v] = NONE;
    if (l == r) { sum[v] = a[l]; return; }
    int m = (l + r) / 2;
    build(2 * v, l, m);
    build(2 * v + 1, m + 1, r);
    sum[v] = sum[2 * v] + sum[2 * v + 1];
}
void push(int v, int l, int r) {
    int m = (l + r) / 2;
    if (st[v] != NONE) applySet(2 * v, l, m, st[v]), applySet(2 * v + 1, m + 1, r, st[v]), st[v] = NONE;
    if (ad[v]) applyAdd(2 * v, l, m, ad[v]), applyAdd(2 * v + 1, m + 1, r, ad[v]), ad[v] = 0;
}
void update(int v, int l, int r, int ql, int qr, int type, ll x) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) { type == 1 ? applyAdd(v, l, r, x) : applySet(v, l, r, x); return; }
    push(v, l, r);
    int m = (l + r) / 2;
    update(2 * v, l, m, ql, qr, type, x);
    update(2 * v + 1, m + 1, r, ql, qr, type, x);
    sum[v] = sum[2 * v] + sum[2 * v + 1];
}
ll query(int v, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return 0;
    if (ql <= l && r <= qr) return sum[v];
    push(v, l, r);
    int m = (l + r) / 2;
    return query(2 * v, l, m, ql, qr) + query(2 * v + 1, m + 1, r, ql, qr);
}

int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while (q--) {
        int type, l, r;
        cin >> type >> l >> r;
        if (type == 3) cout << query(1, 1, n, l, r) << "\n";
        else { ll x; cin >> x; update(1, 1, n, l, r, type, x); }   // 1 = add, 2 = set
    }
}
44
6

4. Flip a range of bulbs, count the lit ones.

Solution

Store how many are on; a flip turns on into len − on, and the tag is a boolean that two flips cancel (flip[v] = !flip[v]).

#include <bits/stdc++.h>
using namespace std;

// Bulbs on/off. 1 l r: flip l..r. 2 l r: how many are on.
int n, q, on[2000004];
bool flip[2000004];

void apply(int v, int l, int r) { on[v] = (r - l + 1) - on[v]; flip[v] = !flip[v]; }   // two flips cancel
void push(int v, int l, int r) {
    if (!flip[v]) return;
    int m = (l + r) / 2;
    apply(2 * v, l, m);
    apply(2 * v + 1, m + 1, r);
    flip[v] = false;
}
void update(int v, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) { apply(v, l, r); return; }
    push(v, l, r);
    int m = (l + r) / 2;
    update(2 * v, l, m, ql, qr);
    update(2 * v + 1, m + 1, r, ql, qr);
    on[v] = on[2 * v] + on[2 * v + 1];
}
int query(int v, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return 0;
    if (ql <= l && r <= qr) return on[v];
    push(v, l, r);
    int m = (l + r) / 2;
    return query(2 * v, l, m, ql, qr) + query(2 * v + 1, m + 1, r, ql, qr);
}

int main() {
    cin >> n >> q;                       // all bulbs start off
    while (q--) {
        int type, l, r;
        cin >> type >> l >> r;
        if (type == 1) update(1, 1, n, l, r);
        else cout << query(1, 1, n, l, r) << "\n";
    }
}
4
4
0

Quick quiz

A node already holds the tag "add 3". Then "add 5" arrives at the same node. What is the tag now?

lz[v] = 3;  apply(v, 5);  // lz[v] = ?

A) 5 · B) 8 · C) 15 · D) 3

Answer

B. Additions compose by adding: 3 + 5 = 8. For assignments the newer tag simply replaces the older one.

Interview questions

  1. What does a segment tree node store, and why is a range query O(log n)? An aggregate of its block; a range splits into at most two partial nodes per level, so O(log n) nodes are visited.
  2. What is lazy propagation? Updating a fully covered node's aggregate immediately and storing a tag for its children, pushed down only when the children are visited.
  3. When must you push? Before recursing into the children of a node, in both updates and queries.
  4. How do tags compose? Adds add; assignments replace; set-then-add pairs need a defined order (a set wipes earlier adds).
  5. Why 4n? For n not a power of two, the recursive layout can use indexes up to about 4n.
  6. Segment tree vs Fenwick tree? Fenwick is shorter and faster for prefix-style sums (even range add + range sum with two trees); segment trees handle min/max, assignments and custom merges.
  7. How do you choose the "no tag" value? A value the data can never take (LLONG_MIN, or a separate boolean flag).

Glossary

Term Meaning Example
Segment tree A tree of blocks from recursive halving, each storing an aggregate block sums
Node / block A tree vertex and the array range it covers node [3,4]
Leaf A node covering a single element [5,5]
Aggregate The value stored for a block: sum, max, min… sum[v]
Range query Ask about a[l..r] sum of [2, 3]
Range update Change all of a[l..r] add 10 to [1, 3]
Lazy tag An update stored at a node, owed to its children lz[v] = 10
apply Update a whole block's aggregate and its tag sum += x · len
push (push down) Hand a node's tag to its children and clear it before recursing
pull Recompute a node from its children sum[v] = sum[2v] + sum[2v+1]
Tag composition Combining two tags on the same node add + add = add
Assignment tag "Set everything below to h" Skyline Renovation
Sentinel (NONE) A special value meaning "nothing" LLONG_MIN
Neutral element The value that doesn't change an aggregate 0 for sum, −∞ for max
xor checksum Folding many answers into one number to compare runs check ^= …
O(log n) Proportional to the depth of the tree per operation
Stress test Comparing a fast solution with a slow, surely-correct one on many random inputs all 500 tests passed
Time Limit Exceeded (TLE) Too slow loops
Wrong Answer (WA) A wrong output 5, 8
Segment tree beats A segment tree for range min/max updates next episode

Summary

  • A segment tree splits any range into O(log n) whole blocks.
  • Lazy tags update a whole block at once; push before going below a node, in update and query (5 instead of 25 otherwise).
  • Adds compose by adding; assignments replace; the "no tag" value must be impossible data (8 instead of 0 otherwise).
  • Both operations are O(log n); arrays of 4n.

Solutions in C++, Java and Python

Problem I1 · Festival Lights

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, q;
ll a[500001], sum[2000004], lz[2000004];   // lz[v] = add still owed to v's children

void build(int v, int l, int r) {
    if (l == r) { sum[v] = a[l]; return; }
    int m = (l + r) / 2;
    build(2 * v, l, m);
    build(2 * v + 1, m + 1, r);
    sum[v] = sum[2 * v] + sum[2 * v + 1];
}
void apply(int v, int l, int r, ll x) {      // the whole block gets +x
    sum[v] += x * (r - l + 1);
    lz[v] += x;
}
void push(int v, int l, int r) {             // pass the notice down
    if (lz[v] == 0) return;
    int m = (l + r) / 2;
    apply(2 * v, l, m, lz[v]);
    apply(2 * v + 1, m + 1, r, lz[v]);
    lz[v] = 0;
}
void update(int v, int l, int r, int ql, int qr, ll x) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) { apply(v, l, r, x); return; }   // fully inside: stop here
    push(v, l, r);
    int m = (l + r) / 2;
    update(2 * v, l, m, ql, qr, x);
    update(2 * v + 1, m + 1, r, ql, qr, x);
    sum[v] = sum[2 * v] + sum[2 * v + 1];
}
ll query(int v, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return 0;
    if (ql <= l && r <= qr) return sum[v];
    push(v, l, r);                           // children must be up to date
    int m = (l + r) / 2;
    return query(2 * v, l, m, ql, qr) + query(2 * v + 1, m + 1, r, ql, qr);
}
void rangeAdd(int l, int r, ll x) { update(1, 1, n, l, r, x); }
ll rangeSum(int l, int r) { return query(1, 1, n, l, r); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while (q--) {
        int type, l, r;
        cin >> type >> l >> r;
        if (type == 1) {
            ll x;
            cin >> x;
            rangeAdd(l, r, x);
        } else cout << rangeSum(l, r) << "\n";
    }
}

Java

import java.util.*;
import java.io.*;

public class Main {
    static int n;
    static long[] a, sum, lz;

    static void build(int v, int l, int r) {
        if (l == r) { sum[v] = a[l]; return; }
        int m = (l + r) / 2;
        build(2 * v, l, m); build(2 * v + 1, m + 1, r);
        sum[v] = sum[2 * v] + sum[2 * v + 1];
    }
    static void apply(int v, int l, int r, long x) { sum[v] += x * (r - l + 1); lz[v] += x; }
    static void push(int v, int l, int r) {
        if (lz[v] == 0) return;
        int m = (l + r) / 2;
        apply(2 * v, l, m, lz[v]); apply(2 * v + 1, m + 1, r, lz[v]);
        lz[v] = 0;
    }
    static void update(int v, int l, int r, int ql, int qr, long x) {
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) { apply(v, l, r, x); return; }
        push(v, l, r);
        int m = (l + r) / 2;
        update(2 * v, l, m, ql, qr, x); update(2 * v + 1, m + 1, r, ql, qr, x);
        sum[v] = sum[2 * v] + sum[2 * v + 1];
    }
    static long query(int v, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return 0;
        if (ql <= l && r <= qr) return sum[v];
        push(v, l, r);
        int m = (l + r) / 2;
        return query(2 * v, l, m, ql, qr) + query(2 * v + 1, m + 1, r, ql, qr);
    }
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedInputStream(System.in));
        in.nextToken(); n = (int) in.nval; in.nextToken(); int q = (int) in.nval;
        a = new long[n + 1]; sum = new long[4 * n + 4]; lz = new long[4 * n + 4];
        for (int i = 1; i <= n; i++) { in.nextToken(); a[i] = (long) in.nval; }
        build(1, 1, n);
        StringBuilder sb = new StringBuilder();
        while (q-- > 0) {
            in.nextToken(); int type = (int) in.nval;
            in.nextToken(); int l = (int) in.nval; in.nextToken(); int r = (int) in.nval;
            if (type == 1) { in.nextToken(); update(1, 1, n, l, r, (long) in.nval); }
            else sb.append(query(1, 1, n, l, r)).append('\n');
        }
        System.out.print(sb);
    }
}
15
25
41
3

Python (recursive; fine for small inputs, too slow for 5 · 10^5 in CPython)

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n, q = int(data[0]), int(data[1])
    a = [0] + [int(x) for x in data[2:n + 2]]
    size = 4 * n + 4
    s, lz = [0] * size, [0] * size

    def build(v, l, r):
        if l == r:
            s[v] = a[l]; return
        m = (l + r) // 2
        build(2 * v, l, m); build(2 * v + 1, m + 1, r)
        s[v] = s[2 * v] + s[2 * v + 1]

    def apply(v, l, r, x):
        s[v] += x * (r - l + 1); lz[v] += x

    def push(v, l, r):
        if lz[v]:
            m = (l + r) // 2
            apply(2 * v, l, m, lz[v]); apply(2 * v + 1, m + 1, r, lz[v]); lz[v] = 0

    def update(v, l, r, ql, qr, x):
        if qr < l or r < ql: return
        if ql <= l and r <= qr:
            apply(v, l, r, x); return
        push(v, l, r)
        m = (l + r) // 2
        update(2 * v, l, m, ql, qr, x); update(2 * v + 1, m + 1, r, ql, qr, x)
        s[v] = s[2 * v] + s[2 * v + 1]

    def query(v, l, r, ql, qr):
        if qr < l or r < ql: return 0
        if ql <= l and r <= qr: return s[v]
        push(v, l, r)
        m = (l + r) // 2
        return query(2 * v, l, m, ql, qr) + query(2 * v + 1, m + 1, r, ql, qr)

    build(1, 1, n)
    out, p = [], n + 2
    for _ in range(q):
        t, l, r = int(data[p]), int(data[p + 1]), int(data[p + 2]); p += 3
        if t == 1:
            update(1, 1, n, l, r, int(data[p])); p += 1
        else:
            out.append(query(1, 1, n, l, r))
    print("\n".join(map(str, out)))

main()
15
25
41
3

Problem I2 · Skyline Renovation

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, q;
ll a[500001], mx[2000004], tag[2000004];   // tag[v] = height to set below v
const ll NONE = LLONG_MIN;                // "no tag": a height can never be this

void build(int v, int l, int r) {
    tag[v] = NONE;
    if (l == r) { mx[v] = a[l]; return; }
    int m = (l + r) / 2;
    build(2 * v, l, m);
    build(2 * v + 1, m + 1, r);
    mx[v] = max(mx[2 * v], mx[2 * v + 1]);
}
void apply(int v, ll h) { mx[v] = h; tag[v] = h; }   // the whole block becomes h
void push(int v) {
    if (tag[v] == NONE) return;
    apply(2 * v, tag[v]);
    apply(2 * v + 1, tag[v]);
    tag[v] = NONE;
}
void update(int v, int l, int r, int ql, int qr, ll h) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) { apply(v, h); return; }
    push(v);
    int m = (l + r) / 2;
    update(2 * v, l, m, ql, qr, h);
    update(2 * v + 1, m + 1, r, ql, qr, h);
    mx[v] = max(mx[2 * v], mx[2 * v + 1]);
}
ll query(int v, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return LLONG_MIN;
    if (ql <= l && r <= qr) return mx[v];
    push(v);
    int m = (l + r) / 2;
    return max(query(2 * v, l, m, ql, qr), query(2 * v + 1, m + 1, r, ql, qr));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while (q--) {
        int type, l, r;
        cin >> type >> l >> r;
        if (type == 1) {
            ll h;
            cin >> h;
            update(1, 1, n, l, r, h);
        } else cout << query(1, 1, n, l, r) << "\n";
    }
}

Java

import java.util.*;
import java.io.*;

public class Main {
    static final long NONE = Long.MIN_VALUE;          // "no tag": no height is ever this
    static int n;
    static long[] a, mx, tag;

    static void build(int v, int l, int r) {
        tag[v] = NONE;
        if (l == r) { mx[v] = a[l]; return; }
        int m = (l + r) / 2;
        build(2 * v, l, m); build(2 * v + 1, m + 1, r);
        mx[v] = Math.max(mx[2 * v], mx[2 * v + 1]);
    }
    static void apply(int v, long h) { mx[v] = h; tag[v] = h; }
    static void push(int v) {
        if (tag[v] == NONE) return;
        apply(2 * v, tag[v]); apply(2 * v + 1, tag[v]);
        tag[v] = NONE;
    }
    static void update(int v, int l, int r, int ql, int qr, long h) {
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) { apply(v, h); return; }
        push(v);
        int m = (l + r) / 2;
        update(2 * v, l, m, ql, qr, h); update(2 * v + 1, m + 1, r, ql, qr, h);
        mx[v] = Math.max(mx[2 * v], mx[2 * v + 1]);
    }
    static long query(int v, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return Long.MIN_VALUE;
        if (ql <= l && r <= qr) return mx[v];
        push(v);
        int m = (l + r) / 2;
        return Math.max(query(2 * v, l, m, ql, qr), query(2 * v + 1, m + 1, r, ql, qr));
    }
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedInputStream(System.in));
        in.nextToken(); n = (int) in.nval; in.nextToken(); int q = (int) in.nval;
        a = new long[n + 1]; mx = new long[4 * n + 4]; tag = new long[4 * n + 4];
        for (int i = 1; i <= n; i++) { in.nextToken(); a[i] = (long) in.nval; }
        build(1, 1, n);
        StringBuilder sb = new StringBuilder();
        while (q-- > 0) {
            in.nextToken(); int type = (int) in.nval;
            in.nextToken(); int l = (int) in.nval; in.nextToken(); int r = (int) in.nval;
            if (type == 1) { in.nextToken(); update(1, 1, n, l, r, (long) in.nval); }
            else sb.append(query(1, 1, n, l, r)).append('\n');
        }
        System.out.print(sb);
    }
}
8
6
0
1

Python

import sys

NONE = None                                    # "no tag" is a different kind of value than any height

def main():
    data = sys.stdin.buffer.read().split()
    n, q = int(data[0]), int(data[1])
    a = [0] + [int(x) for x in data[2:n + 2]]
    mx, tag = [0] * (4 * n + 4), [NONE] * (4 * n + 4)

    def build(v, l, r):
        if l == r:
            mx[v] = a[l]; return
        m = (l + r) // 2
        build(2 * v, l, m); build(2 * v + 1, m + 1, r)
        mx[v] = max(mx[2 * v], mx[2 * v + 1])

    def apply(v, h):
        mx[v] = h; tag[v] = h

    def push(v):
        if tag[v] is not NONE:
            apply(2 * v, tag[v]); apply(2 * v + 1, tag[v]); tag[v] = NONE

    def update(v, l, r, ql, qr, h):
        if qr < l or r < ql: return
        if ql <= l and r <= qr:
            apply(v, h); return
        push(v)
        m = (l + r) // 2
        update(2 * v, l, m, ql, qr, h); update(2 * v + 1, m + 1, r, ql, qr, h)
        mx[v] = max(mx[2 * v], mx[2 * v + 1])

    def query(v, l, r, ql, qr):
        if qr < l or r < ql: return float("-inf")
        if ql <= l and r <= qr: return mx[v]
        push(v)
        m = (l + r) // 2
        return max(query(2 * v, l, m, ql, qr), query(2 * v + 1, m + 1, r, ql, qr))

    build(1, 1, n)
    out, p = [], n + 2
    for _ in range(q):
        t, l, r = int(data[p]), int(data[p + 1]), int(data[p + 2]); p += 3
        if t == 1:
            update(1, 1, n, l, r, int(data[p])); p += 1
        else:
            out.append(query(1, 1, n, l, r))
    print("\n".join(map(str, out)))

main()
8
6
0
1