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) or2 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): applylz[v]to both children, thenlz[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) or2 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
- 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.
- 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.
- When must you push? Before recursing into the children of a node, in both updates and queries.
- How do tags compose? Adds add; assignments replace; set-then-add pairs need a defined order (a set wipes earlier adds).
- Why 4n? For n not a power of two, the recursive layout can use indexes up to about 4n.
- 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.
- 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 (
5instead of25otherwise). - Adds compose by adding; assignments replace; the "no tag" value must be impossible data (
8instead of0otherwise). - 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