SyntaxPilot
Courses/Competitive Programming/Lesson 65
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 65 of 90

Sqrt decomposition

queued

These are the notes for Competitive Programming episode 65. Square root decomposition cuts an array of n values into blocks of about B = √n values. Any range [l, r] is then a broken piece of one block, some whole blocks, and a broken piece of another block. The broken pieces have at most 2B elements and are handled one by one; every whole block is handled in one step from a small summary it keeps (its max, its sum, a sorted copy…). With B = √n an operation costs O(√n). Monsoon Gauges (range add, range max) shows the loop (TLE), blocks with a pending add (a lazy tag) per block, and the bug where the broken ends forget the tag (9 5 1 9 instead of 9 9 5 13). Thick Books (count values ≥ k in a range, with replacements) keeps a sorted copy of every block and uses binary search. 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

A school assembly: 1,000 students stand in rows of about 32, and every row has a monitor. "Sweets for roll numbers 45 to 870": in the two broken rows at the ends you hand out sweets one by one, and for every full row in between you tell the monitor once, "everyone in your row gets one". "Who is the tallest from 45 to 870?": ask the monitors of the full rows (each knows their row's tallest) and check the students of the two broken rows yourself. About a hundred checks instead of a thousand.

Problem Q1 · Monsoon Gauges

(Written for this course, in the style of a classic range-update / range-query problem.)

  • Input: n q (n, q ≤ 5 · 10^5), readings a[1..n], then q operations:
  • 1 l r x: add x (|x| ≤ 1000, may be negative) to every gauge l..r;
  • 2 l r: print the highest reading in l..r.
8 6
3 1 4 1 5 9 2 6
2 1 8
1 2 7 4
2 3 5
1 1 3 -10
2 1 4
2 6 6

Answers: 9, 9, 5, 13.

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 add(int l, int r, ll x) {
    for (int i = l; i <= r; i++) a[i] += x;
}
ll highest(int l, int r) {
    ll m = LLONG_MIN;
    for (int i = l; i <= r; i++) m = max(m, a[i]);
    return m;
}

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 t, l, r;
        cin >> t >> l >> r;
        if (t == 1) { ll x; cin >> x; add(l, r, x); }
        else cout << highest(l, r) << "\n";
    }
}
9
9
5
13

With half a million operations, each over almost the whole array:

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

int n, q;
ll a[500001];

void add(int l, int r, ll x) {
    for (int i = l; i <= r; i++) a[i] += x;
}
ll highest(int l, int r) {
    ll m = LLONG_MIN;
    for (int i = l; i <= r; i++) m = max(m, a[i]);
    return m;
}

int main() {
    n = q = 500000;                          // half a million gauges and operations
    mt19937 rng(65);
    for (int i = 1; i <= n; i++) a[i] = rng() % 1000;
    ll check = 0;
    for (int k = 0; k < q; k++) {
        int l = rng() % 10 + 1, r = n - rng() % 10;     // long stretches
        if (k % 2 == 0) add(l, r, (ll)(rng() % 2001) - 1000);
        else check ^= highest(l, r);
    }
    cout << check << "\n";
}
Time Limit Exceeded

n · q ≈ 2.5 · 10^11 steps.

Blocks of √n

Cut the array into blocks of B elements: block b holds positions b·B + 1 … min(n, (b + 1)·B), and position i is in block (i − 1) / B. A range [l, r] costs at most 2B steps for the two broken ends plus at most n / B steps for the whole blocks. Small B means many blocks; big B means long ends. The sum 2B + n / B is smallest around B = √n: for n = 5 · 10^5, B ≈ 707 and one operation is about 2,100 steps.

Each block keeps:

  • mx[b]: the max of its raw values a[i];
  • lz[b]: a pending add (lazy tag) that applies to every element of the block but hasn't been written into a[].

The real value of position i is a[i] + lz[blk(i)]. A whole block's real max is mx[b] + lz[b].

  • add(l, r, x): broken ends: a[i] += x one by one, then rebuild that block's max; whole blocks: lz[b] += x (O(1)).
  • highest(l, r): broken ends: a[i] + lz[block]; whole blocks: mx[b] + lz[b].

On the sample, B = 2: rain +4 on 2..7 changes a[2] and a[7] by hand and tags blocks 2 and 3 (positions 3..6). The question 3..5 reads only broken ends: 4 + 4, 1 + 4, 5 + 4, so the answer is 9.

The bug: the ends forget the tag

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

int n, q;
ll a[500001];
int B;                                         // block size, about √n
ll mx[800], lz[800];                           // per block: max of a[], pending add
int blk(int i) { return (i - 1) / B; }
void rebuild(int b) {                          // recompute one block's max
    mx[b] = LLONG_MIN;
    for (int i = b * B + 1; i <= min(n, (b + 1) * B); i++) mx[b] = max(mx[b], a[i]);
}
void add(int l, int r, ll x) {
    int bl = blk(l), br = blk(r);
    if (bl == br) { for (int i = l; i <= r; i++) a[i] += x; rebuild(bl); return; }
    for (int i = l; blk(i) == bl; i++) a[i] += x;          // left end: one by one
    rebuild(bl);
    for (int b = bl + 1; b < br; b++) lz[b] += x;          // whole blocks: O(1) each
    for (int i = r; blk(i) == br; i--) a[i] += x;          // right end: one by one
    rebuild(br);
}
ll highest(int l, int r) {
    int bl = blk(l), br = blk(r);
    ll m = LLONG_MIN;
    if (bl == br) { for (int i = l; i <= r; i++) m = max(m, a[i]); return m; }
    for (int i = l; blk(i) == bl; i++) m = max(m, a[i]);
    for (int b = bl + 1; b < br; b++) m = max(m, mx[b] + lz[b]);   // whole blocks
    for (int i = r; blk(i) == br; i--) m = max(m, a[i]);
    return m;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    B = max(1, (int)sqrt(n));
    for (int b = 0; b <= blk(n); b++) rebuild(b);
    while (q--) {
        int t, l, r;
        cin >> t >> l >> r;
        if (t == 1) { ll x; cin >> x; add(l, r, x); }
        else cout << highest(l, r) << "\n";
    }
}
9
5
1
9

Expected 9 9 5 13. The second question reads the raw 4, 1, 5 and misses the pending +4.

The fix

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

int n, q;
ll a[500001];
int B;                                         // block size, about √n
ll mx[800], lz[800];                           // per block: max of a[], pending add
int blk(int i) { return (i - 1) / B; }
void rebuild(int b) {                          // recompute one block's max
    mx[b] = LLONG_MIN;
    for (int i = b * B + 1; i <= min(n, (b + 1) * B); i++) mx[b] = max(mx[b], a[i]);
}
void add(int l, int r, ll x) {
    int bl = blk(l), br = blk(r);
    if (bl == br) { for (int i = l; i <= r; i++) a[i] += x; rebuild(bl); return; }
    for (int i = l; blk(i) == bl; i++) a[i] += x;          // left end: one by one
    rebuild(bl);
    for (int b = bl + 1; b < br; b++) lz[b] += x;          // whole blocks: O(1) each
    for (int i = r; blk(i) == br; i--) a[i] += x;          // right end: one by one
    rebuild(br);
}
ll highest(int l, int r) {
    int bl = blk(l), br = blk(r);
    ll m = LLONG_MIN;
    if (bl == br) { for (int i = l; i <= r; i++) m = max(m, a[i] + lz[bl]); return m; }
    for (int i = l; blk(i) == bl; i++) m = max(m, a[i] + lz[bl]);
    for (int b = bl + 1; b < br; b++) m = max(m, mx[b] + lz[b]);   // whole blocks
    for (int i = r; blk(i) == br; i--) m = max(m, a[i] + lz[br]);
    return m;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    B = max(1, (int)sqrt(n));
    for (int b = 0; b <= blk(n); b++) rebuild(b);
    while (q--) {
        int t, l, r;
        cin >> t >> l >> r;
        if (t == 1) { ll x; cin >> x; add(l, r, x); }
        else cout << highest(l, r) << "\n";
    }
}
9
9
5
13

A single gauge:

1 3
5
2 1 1
1 1 1 -7
2 1 1
5
-2

Half a million operations (about a second; the maxima are folded into one xor check number):

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

int n, q;
ll a[500001];
int B;                                         // block size, about √n
ll mx[800], lz[800];                           // per block: max of a[], pending add
int blk(int i) { return (i - 1) / B; }
void rebuild(int b) {                          // recompute one block's max
    mx[b] = LLONG_MIN;
    for (int i = b * B + 1; i <= min(n, (b + 1) * B); i++) mx[b] = max(mx[b], a[i]);
}
void add(int l, int r, ll x) {
    int bl = blk(l), br = blk(r);
    if (bl == br) { for (int i = l; i <= r; i++) a[i] += x; rebuild(bl); return; }
    for (int i = l; blk(i) == bl; i++) a[i] += x;          // left end: one by one
    rebuild(bl);
    for (int b = bl + 1; b < br; b++) lz[b] += x;          // whole blocks: O(1) each
    for (int i = r; blk(i) == br; i--) a[i] += x;          // right end: one by one
    rebuild(br);
}
ll highest(int l, int r) {
    int bl = blk(l), br = blk(r);
    ll m = LLONG_MIN;
    if (bl == br) { for (int i = l; i <= r; i++) m = max(m, a[i] + lz[bl]); return m; }
    for (int i = l; blk(i) == bl; i++) m = max(m, a[i] + lz[bl]);
    for (int b = bl + 1; b < br; b++) m = max(m, mx[b] + lz[b]);   // whole blocks
    for (int i = r; blk(i) == br; i--) m = max(m, a[i] + lz[br]);
    return m;
}

int main() {
    n = q = 500000;                          // half a million gauges and operations
    mt19937 rng(65);
    for (int i = 1; i <= n; i++) a[i] = rng() % 1000;
    B = max(1, (int)sqrt(n));
    for (int b = 0; b <= blk(n); b++) rebuild(b);
    ll check = 0;
    for (int k = 0; k < q; k++) {
        int l = rng() % 10 + 1, r = n - rng() % 10;     // long stretches
        if (k % 2 == 0) add(l, r, (ll)(rng() % 2001) - 1000);
        else check ^= highest(l, r);
    }
    cout << check << "\n";
}
-188178

Stress test

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

int n, q;
ll a[500001];
int B;                                         // block size, about √n
ll mx[800], lz[800];                           // per block: max of a[], pending add
int blk(int i) { return (i - 1) / B; }
void rebuild(int b) {                          // recompute one block's max
    mx[b] = LLONG_MIN;
    for (int i = b * B + 1; i <= min(n, (b + 1) * B); i++) mx[b] = max(mx[b], a[i]);
}
void add(int l, int r, ll x) {
    int bl = blk(l), br = blk(r);
    if (bl == br) { for (int i = l; i <= r; i++) a[i] += x; rebuild(bl); return; }
    for (int i = l; blk(i) == bl; i++) a[i] += x;          // left end: one by one
    rebuild(bl);
    for (int b = bl + 1; b < br; b++) lz[b] += x;          // whole blocks: O(1) each
    for (int i = r; blk(i) == br; i--) a[i] += x;          // right end: one by one
    rebuild(br);
}
ll highest(int l, int r) {
    int bl = blk(l), br = blk(r);
    ll m = LLONG_MIN;
    if (bl == br) { for (int i = l; i <= r; i++) m = max(m, a[i] + lz[bl]); return m; }
    for (int i = l; blk(i) == bl; i++) m = max(m, a[i] + lz[bl]);
    for (int b = bl + 1; b < br; b++) m = max(m, mx[b] + lz[b]);   // whole blocks
    for (int i = r; blk(i) == br; i--) m = max(m, a[i] + lz[br]);
    return m;
}

int main() {
    mt19937 rng(65);
    for (int t = 1; t <= 500; t++) {
        n = rng() % 40 + 1;
        vector<ll> s(n + 1);
        for (int i = 1; i <= n; i++) s[i] = a[i] = rng() % 100;
        B = max(1, (int)sqrt(n));
        for (int b = 0; b <= blk(n); b++) lz[b] = 0, rebuild(b);
        for (int k = 0; k < 50; k++) {
            int l = rng() % n + 1, r = rng() % n + 1;
            if (l > r) swap(l, r);
            if (k % 2) {
                ll x = (ll)(rng() % 21) - 10;
                add(l, r, x);
                for (int i = l; i <= r; i++) s[i] += x;
            }
            else if (highest(l, r) != *max_element(s.begin() + l, s.begin() + r + 1)) {
                cout << "mismatch on test " << t;
                return 0;
            }
        }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Problem Q2 · Thick Books

(Written for this course.)

  • Input: n q (n, q ≤ 2 · 10^5), pages a[1..n] (≤ 10^9), then q operations:
  • 1 i x: book i is replaced by one with x pages;
  • 2 l r k: how many books in l..r have at least k pages?
9 5
120 450 300 80 610 200 330 90 500
2 1 9 300
1 4 700
2 2 8 300
1 5 100
2 4 9 250

Answers: 5, 5, 3.

Observation. k changes with every question, so a block's max (or any single number) can't answer "how many are ≥ k". But inside a whole block the order doesn't matter for counting: keep a sorted copy s[b] of every block. Then the count is s[b].end() − lower_bound(s[b], k): one binary search, O(log B). A replacement changes one block: erase the old value and insert the new one in sorted position, O(B).

The obvious attempt: loop over the range

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

int n, q, a[200001];

void replace(int i, int x) { a[i] = x; }
int thick(int l, int r, int k) {
    int c = 0;
    for (int i = l; i <= r; i++) c += a[i] >= k;
    return c;
}

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 t;
        cin >> t;
        if (t == 1) { int i, x; cin >> i >> x; replace(i, x); }
        else { int l, r, k; cin >> l >> r >> k; cout << thick(l, r, k) << "\n"; }
    }
}
5
5
3

The full-size test (2 · 10^5 operations over long ranges):

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

int n, q, a[200001];

void replace(int i, int x) { a[i] = x; }
int thick(int l, int r, int k) {
    int c = 0;
    for (int i = l; i <= r; i++) c += a[i] >= k;
    return c;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    n = q = 200000;
    mt19937 rng(65);
    for (int i = 1; i <= n; i++) a[i] = rng() % 1000000000;
    ll check = 0;
    for (int t = 0; t < q; t++) {
        if (t % 2 == 0) replace(rng() % n + 1, rng() % 1000000000);
        else check += thick(rng() % 10 + 1, n - rng() % 10, rng() % 1000000000);
    }
    cout << check << "\n";
}
10021544349

It finishes, but it takes about 8 seconds on an idle machine (12–13 s while the video was recording; the SyntaxPilot compiler allows 25 s). A contest judge allows about 2 seconds, so this is Time Limit Exceeded there.

Sorted blocks

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

int n, q, a[200001];
int B;
vector<int> s[2000];                           // s[b] = block b, sorted
int blk(int i) { return (i - 1) / B; }
void replace(int i, int x) {                   // fix one block: O(B)
    vector<int>& v = s[blk(i)];
    v.erase(lower_bound(v.begin(), v.end(), a[i]));
    v.insert(upper_bound(v.begin(), v.end(), x), x);
    a[i] = x;
}
int thick(int l, int r, int k) {
    int bl = blk(l), br = blk(r), c = 0;
    if (bl == br) { for (int i = l; i <= r; i++) c += a[i] >= k; return c; }
    for (int i = l; blk(i) == bl; i++) c += a[i] >= k;
    for (int b = bl + 1; b < br; b++)                       // whole blocks: binary search
        c += s[b].end() - lower_bound(s[b].begin(), s[b].end(), k);
    for (int i = r; blk(i) == br; i--) c += a[i] >= k;
    return c;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    B = max(1, (int)sqrt(n));
    for (int i = 1; i <= n; i++) s[blk(i)].push_back(a[i]);
    for (int b = 0; b <= blk(n); b++) sort(s[b].begin(), s[b].end());
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) { int i, x; cin >> i >> x; replace(i, x); }
        else { int l, r, k; cin >> l >> r >> k; cout << thick(l, r, k) << "\n"; }
    }
}
5
5
3
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, q, a[200001];
int B;
vector<int> s[2000];                           // s[b] = block b, sorted
int blk(int i) { return (i - 1) / B; }
void replace(int i, int x) {                   // fix one block: O(B)
    vector<int>& v = s[blk(i)];
    v.erase(lower_bound(v.begin(), v.end(), a[i]));
    v.insert(upper_bound(v.begin(), v.end(), x), x);
    a[i] = x;
}
int thick(int l, int r, int k) {
    int bl = blk(l), br = blk(r), c = 0;
    if (bl == br) { for (int i = l; i <= r; i++) c += a[i] >= k; return c; }
    for (int i = l; blk(i) == bl; i++) c += a[i] >= k;
    for (int b = bl + 1; b < br; b++)                       // whole blocks: binary search
        c += s[b].end() - lower_bound(s[b].begin(), s[b].end(), k);
    for (int i = r; blk(i) == br; i--) c += a[i] >= k;
    return c;
}

int main() {
    n = q = 200000;
    mt19937 rng(65);
    for (int i = 1; i <= n; i++) a[i] = rng() % 1000000000;
    B = max(1, (int)sqrt(n));
    for (int i = 1; i <= n; i++) s[blk(i)].push_back(a[i]);
    for (int b = 0; b <= blk(n); b++) sort(s[b].begin(), s[b].end());
    ll check = 0;
    for (int t = 0; t < q; t++) {
        if (t % 2 == 0) replace(rng() % n + 1, rng() % 1000000000);
        else check += thick(rng() % 10 + 1, n - rng() % 10, rng() % 1000000000);
    }
    cout << check << "\n";
}
10021544349

The same check number as the brute force, about four times faster (under 2 seconds on an idle machine).

Stress test (many equal values)

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

int n, q, a[200001];
int B;
vector<int> s[2000];                           // s[b] = block b, sorted
int blk(int i) { return (i - 1) / B; }
void replace(int i, int x) {                   // fix one block: O(B)
    vector<int>& v = s[blk(i)];
    v.erase(lower_bound(v.begin(), v.end(), a[i]));
    v.insert(upper_bound(v.begin(), v.end(), x), x);
    a[i] = x;
}
int thick(int l, int r, int k) {
    int bl = blk(l), br = blk(r), c = 0;
    if (bl == br) { for (int i = l; i <= r; i++) c += a[i] >= k; return c; }
    for (int i = l; blk(i) == bl; i++) c += a[i] >= k;
    for (int b = bl + 1; b < br; b++)                       // whole blocks: binary search
        c += s[b].end() - lower_bound(s[b].begin(), s[b].end(), k);
    for (int i = r; blk(i) == br; i--) c += a[i] >= k;
    return c;
}

int main() {
    mt19937 rng(65);
    for (int t = 1; t <= 500; t++) {
        n = rng() % 40 + 1;
        for (auto& v : s) v.clear();
        for (int i = 1; i <= n; i++) a[i] = rng() % 20;
        B = max(1, (int)sqrt(n));
        for (int i = 1; i <= n; i++) s[blk(i)].push_back(a[i]);
        for (int b = 0; b <= blk(n); b++) sort(s[b].begin(), s[b].end());
        for (int k = 0; k < 50; k++) {
            int l = rng() % n + 1, r = rng() % n + 1, x = rng() % 20;
            if (l > r) swap(l, r);
            if (k % 2) { replace(l, x); continue; }
            int slow = 0;
            for (int i = l; i <= r; i++) slow += a[i] >= x;
            if (thick(l, r, x) != slow) { cout << "mismatch on test " << t; return 0; }
        }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Complexity vs the constraints

Method Per operation Total Verdict
Q1: loop O(n) O(n · q) ≈ 2.5 · 10^11 TLE
Q1: blocks + lazy tag O(√n) O(q√n) ≈ 10^9 simple steps accepted (~1 s)
Q2: loop O(n) O(n · q) ~8 s or more: TLE on a 2 s judge
Q2: sorted blocks query O(B + (n/B) log B), update O(B) ≈ 10^9 accepted (< 2 s)
B = 1 or B = n O(n) — the brute force again

For Q2 the best block size is a little bigger than √n, around √(n log n), because whole blocks cost log B each. Try it (homework 4).

Memory: O(n) for the blocks and the sorted copies.

Where it shows up

  • Any per-block summary: max, sum, sorted copy, a count of each value, a bitset.
  • Mo's algorithm (next episode): square-root blocks on the order of the queries.
  • Rebuild every √q updates: keep a fully built structure plus a short list of recent updates, scan the list in each query, rebuild when it reaches √q.
  • Heavy and light: in a graph with m edges, at most 2√m vertices have degree above √m; treat those differently.

Common mistakes (and the real outputs)

Mistake What you see Why Fix
loop over every element Time Limit Exceeded O(n · q) blocks of √n
ends read a[i] without lz[b] 9 5 1 9 (expected 9 9 5 13) pending add forgotten a[i] + lz[b]
no rebuild(b) after changing an end wrong max stale block summary rebuild that block
B = 1 or B = n Time Limit Exceeded degenerates to the brute force B ≈ √n
block arrays too small out of bounds n / B + 1 blocks size them for the smallest B
replace without fixing s[b] wrong counts sorted copy is stale erase + insert
block of i as i / B with 1-based i wrong block boundaries mixed 0/1 indexing (i − 1) / B everywhere

Mini project

Write a reusable SqrtBlocks class with pointSet, rangeAdd, rangeSum, rangeMax and countAtLeast, choosing what each block stores. Stress-test every operation against a plain array, with n = 1, n a perfect square, and n one more than a perfect square.

Practice

These are the homework problems from the episode. Every answer below came from a compiled C++ program (g++ -O2 -std=c++17), and the C++ solutions were checked against a brute force on 400 random tests each.

1. Range add, range sum with blocks (1 l r x adds x, 2 l r prints the sum).

Solution

Each block keeps the sum of its raw values and a pending add. A whole block's real sum is sum[b] + lz[b] · (block length): the tag counts once per element, which is the one new idea compared with max.

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

int n, q, B;
ll a[500001], sum[800], lz[800];               // per block: sum of a[], pending add
int blk(int i) { return (i - 1) / B; }
int len(int b) { return min(n, (b + 1) * B) - b * B; }

void add(int l, int r, ll x) {
    int bl = blk(l), br = blk(r);
    if (bl == br) { for (int i = l; i <= r; i++) a[i] += x, sum[bl] += x; return; }
    for (int i = l; blk(i) == bl; i++) a[i] += x, sum[bl] += x;
    for (int b = bl + 1; b < br; b++) lz[b] += x;
    for (int i = r; blk(i) == br; i--) a[i] += x, sum[br] += x;
}
ll total(int l, int r) {
    int bl = blk(l), br = blk(r);
    ll s = 0;
    if (bl == br) { for (int i = l; i <= r; i++) s += a[i] + lz[bl]; return s; }
    for (int i = l; blk(i) == bl; i++) s += a[i] + lz[bl];
    for (int b = bl + 1; b < br; b++) s += sum[b] + lz[b] * len(b);   // the tag counts once per element
    for (int i = r; blk(i) == br; i--) s += a[i] + lz[br];
    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];
    B = max(1, (int)sqrt(n));
    for (int i = 1; i <= n; i++) sum[blk(i)] += a[i];
    while (q--) {
        int t, l, r;
        cin >> t >> l >> r;
        if (t == 1) { ll x; cin >> x; add(l, r, x); }
        else cout << total(l, r) << "\n";
    }
}

On the episode's sample input (now read as add / sum):

31
22
-9
13

(3 + 1 + 4 + 1 + 5 + 9 + 2 + 6 = 31 at first; after +4 on 2..7, positions 3..5 hold 8, 5, 9.)

2. Count values ≤ k in l..r (with replacements).

Solution

The same sorted blocks as Q2; a whole block contributes upper_bound(s[b].begin(), s[b].end(), k) − s[b].begin(), and the ends count a[i] <= k.

3. Range assign (1 l r x sets every value in l..r to x, 2 l r prints the max).

Solution

A whole block gets an assignment tag (has[b], asg[b]), and its max becomes x at once. Before touching a block element by element, push writes a pending assignment into a[].

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

int n, q, B;
ll a[500001], mx[800], asg[800];               // asg[b] = value the whole block was set to
bool has[800];                                 // is there a pending assignment?
int blk(int i) { return (i - 1) / B; }
int lo(int b) { return b * B + 1; }
int hi(int b) { return min(n, (b + 1) * B); }

void push(int b) {                             // write a pending assignment into a[]
    if (!has[b]) return;
    for (int i = lo(b); i <= hi(b); i++) a[i] = asg[b];
    has[b] = false;
}
void rebuild(int b) { mx[b] = LLONG_MIN; for (int i = lo(b); i <= hi(b); i++) mx[b] = max(mx[b], a[i]); }
void assign(int l, int r, ll x) {
    int bl = blk(l), br = blk(r);
    push(bl), push(br);
    if (bl == br) { for (int i = l; i <= r; i++) a[i] = x; rebuild(bl); return; }
    for (int i = l; i <= hi(bl); i++) a[i] = x;
    rebuild(bl);
    for (int b = bl + 1; b < br; b++) has[b] = true, asg[b] = x, mx[b] = x;   // whole blocks: O(1)
    for (int i = lo(br); i <= r; i++) a[i] = x;
    rebuild(br);
}
ll highest(int l, int r) {
    int bl = blk(l), br = blk(r);
    push(bl), push(br);
    ll m = LLONG_MIN;
    if (bl == br) { for (int i = l; i <= r; i++) m = max(m, a[i]); return m; }
    for (int i = l; i <= hi(bl); i++) m = max(m, a[i]);
    for (int b = bl + 1; b < br; b++) m = max(m, mx[b]);
    for (int i = lo(br); i <= r; i++) m = max(m, a[i]);
    return m;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    B = max(1, (int)sqrt(n));
    for (int b = 0; b <= blk(n); b++) rebuild(b);
    while (q--) {
        int t, l, r;
        cin >> t >> l >> r;
        if (t == 1) { ll x; cin >> x; assign(l, r, x); }
        else cout << highest(l, r) << "\n";
    }
}

On the episode's sample input (now read as assign / max):

9
4
4
4

4. Tune B for Q2.

Answer

A question costs about 2B + (n / B) · log₂ B and a replacement about B. Try B = √n, 2√n, 3√n and √(n log n) on the big test and compare the times shown by the compiler; a block size a few times √n is usually faster here because the binary searches are the expensive part.

Quick quiz

n = 10,000 and B = 100. In the worst case, about how many steps does one highest(l, r) take?

A) about 300 · B) about 10,000 · C) about 100 · D) about 1,000,000

Answer

A. Two broken ends: at most 2 · 100 = 200 gauges. Whole blocks: at most 10,000 / 100 = 100. About 300 in all.

Interview questions

  1. What is sqrt decomposition? Splitting an array into about √n blocks of √n elements, handling whole blocks through a per-block summary and partial blocks element by element, for O(√n) per operation.
  2. Why √n? One operation costs about 2B + n / B; that is smallest when B = √n.
  3. What is a lazy tag in a block? A pending update stored once for the whole block instead of being written into every element.
  4. When is it better than a segment tree? When the per-block summary is easy but a tree merge is hard (counting values ≥ k with updates, many custom operations), or when simplicity matters more than log factors.
  5. How do you count values ≥ k in a range with point updates? Sorted copy per block + binary search for whole blocks; O(B) to fix a block after an update.
  6. What's the downside? O(√n) instead of O(log n) per operation; it needs a good constant factor.
  7. Name another square-root idea. Mo's algorithm, rebuilding every √q updates, heavy/light vertices by degree.

Glossary

Term Meaning Example
Sqrt decomposition Splitting data into about √n blocks of about √n the school rows
Block A group of B consecutive elements positions 3..4 when B = 2
Block size B How many elements per block B = max(1, (int)sqrt(n))
Broken (partial) block A block only partly inside the range gauge 2 in 2..7
Whole block A block completely inside the range positions 3..6 in 2..7
Block summary What a block stores to answer in one step mx[b], a sorted copy
Lazy tag / pending add An update stored once for a whole block lz[b] += x
Rebuild Recompute a block's summary after changing its elements rebuild(b)
Range update An operation that changes every element in [l, r] rain on 2..7
Range query A question about every element in [l, r] highest in 3..5
Sorted copy A block's values kept in sorted order s[b]
lower_bound Binary search: the first position with value ≥ k count of thick books
upper_bound Binary search: the first position with value > k inserting a replacement
Binary search Halving a sorted range to find a position in O(log n) inside each block
xor checksum Folding many answers into one number check ^= highest(l, r)
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 the loop
Wrong Answer (WA) A wrong output 9 5 1 9
Mo's algorithm Square-root ordering of offline queries next episode

Summary

  • Blocks of B ≈ √n; every range = two broken ends + whole blocks.
  • Whole blocks answer in one step from a summary; ends are walked one by one: O(√n) per operation.
  • Range updates give whole blocks a pending add, which the ends must include too (9 5 1 9 otherwise).
  • Rebuild a block after changing its elements.
  • For "how many ≥ k", keep a sorted copy per block and binary search; fix one block per replacement.

Solutions in C++, Java and Python

Problem Q1 · Monsoon Gauges

C++

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

int n, q;
ll a[500001];
int B;                                         // block size, about √n
ll mx[800], lz[800];                           // per block: max of a[], pending add
int blk(int i) { return (i - 1) / B; }
void rebuild(int b) {                          // recompute one block's max
    mx[b] = LLONG_MIN;
    for (int i = b * B + 1; i <= min(n, (b + 1) * B); i++) mx[b] = max(mx[b], a[i]);
}
void add(int l, int r, ll x) {
    int bl = blk(l), br = blk(r);
    if (bl == br) { for (int i = l; i <= r; i++) a[i] += x; rebuild(bl); return; }
    for (int i = l; blk(i) == bl; i++) a[i] += x;          // left end: one by one
    rebuild(bl);
    for (int b = bl + 1; b < br; b++) lz[b] += x;          // whole blocks: O(1) each
    for (int i = r; blk(i) == br; i--) a[i] += x;          // right end: one by one
    rebuild(br);
}
ll highest(int l, int r) {
    int bl = blk(l), br = blk(r);
    ll m = LLONG_MIN;
    if (bl == br) { for (int i = l; i <= r; i++) m = max(m, a[i] + lz[bl]); return m; }
    for (int i = l; blk(i) == bl; i++) m = max(m, a[i] + lz[bl]);
    for (int b = bl + 1; b < br; b++) m = max(m, mx[b] + lz[b]);   // whole blocks
    for (int i = r; blk(i) == br; i--) m = max(m, a[i] + lz[br]);
    return m;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    B = max(1, (int)sqrt(n));
    for (int b = 0; b <= blk(n); b++) rebuild(b);
    while (q--) {
        int t, l, r;
        cin >> t >> l >> r;
        if (t == 1) { ll x; cin >> x; add(l, r, x); }
        else cout << highest(l, r) << "\n";
    }
}
9
9
5
13

Java

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

public class Main {
    static int n, B;
    static long[] a, mx, lz;
    static int blk(int i) { return (i - 1) / B; }
    static void rebuild(int b) {                       // recompute one block's max
        mx[b] = Long.MIN_VALUE;
        for (int i = b * B + 1; i <= Math.min(n, (b + 1) * B); i++) mx[b] = Math.max(mx[b], a[i]);
    }
    static void add(int l, int r, long x) {
        int bl = blk(l), br = blk(r);
        if (bl == br) { for (int i = l; i <= r; i++) a[i] += x; rebuild(bl); return; }
        for (int i = l; blk(i) == bl; i++) a[i] += x;
        rebuild(bl);
        for (int b = bl + 1; b < br; b++) lz[b] += x;   // whole blocks: O(1) each
        for (int i = r; blk(i) == br; i--) a[i] += x;
        rebuild(br);
    }
    static long highest(int l, int r) {
        int bl = blk(l), br = blk(r);
        long m = Long.MIN_VALUE;
        if (bl == br) { for (int i = l; i <= r; i++) m = Math.max(m, a[i] + lz[bl]); return m; }
        for (int i = l; blk(i) == bl; i++) m = Math.max(m, a[i] + lz[bl]);
        for (int b = bl + 1; b < br; b++) m = Math.max(m, mx[b] + lz[b]);
        for (int i = r; blk(i) == br; i--) m = Math.max(m, a[i] + lz[br]);
        return m;
    }
    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];
        for (int i = 1; i <= n; i++) { in.nextToken(); a[i] = (long) in.nval; }
        B = Math.max(1, (int) Math.sqrt(n));
        mx = new long[n / B + 2]; lz = new long[n / B + 2];
        for (int b = 0; b <= blk(n); b++) rebuild(b);
        StringBuilder sb = new StringBuilder();
        while (q-- > 0) {
            in.nextToken(); int t = (int) in.nval; in.nextToken(); int l = (int) in.nval; in.nextToken(); int r = (int) in.nval;
            if (t == 1) { in.nextToken(); add(l, r, (long) in.nval); }
            else sb.append(highest(l, r)).append('\n');
        }
        System.out.print(sb);
    }
}
9
9
5
13

Python

import sys
from math import isqrt

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]]
    B = max(1, isqrt(n))
    nb = (n - 1) // B + 1
    lz = [0] * nb
    mx = [max(a[b * B + 1:min(n, (b + 1) * B) + 1]) for b in range(nb)]   # block maxima
    def rebuild(b):
        mx[b] = max(a[b * B + 1:min(n, (b + 1) * B) + 1])
    out, p = [], n + 2
    for _ in range(q):
        t, l, r = int(data[p]), int(data[p + 1]), int(data[p + 2]); p += 3
        bl, br = (l - 1) // B, (r - 1) // B
        if t == 1:
            x = int(data[p]); p += 1
            if bl == br:
                for i in range(l, r + 1): a[i] += x
                rebuild(bl)
                continue
            for i in range(l, (bl + 1) * B + 1): a[i] += x
            rebuild(bl)
            for b in range(bl + 1, br): lz[b] += x          # whole blocks: one tag each
            for i in range(br * B + 1, r + 1): a[i] += x
            rebuild(br)
        else:
            if bl == br:
                out.append(max(a[l:r + 1]) + lz[bl])
                continue
            m = max(max(a[l:(bl + 1) * B + 1]) + lz[bl], max(a[br * B + 1:r + 1]) + lz[br])
            for b in range(bl + 1, br): m = max(m, mx[b] + lz[b])
            out.append(m)
    print("\n".join(map(str, out)))

main()
9
9
5
13

(Python is too slow for the full limits here; it is for understanding.)

Problem Q2 · Thick Books

C++

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

int n, q, a[200001];
int B;
vector<int> s[2000];                           // s[b] = block b, sorted
int blk(int i) { return (i - 1) / B; }
void replace(int i, int x) {                   // fix one block: O(B)
    vector<int>& v = s[blk(i)];
    v.erase(lower_bound(v.begin(), v.end(), a[i]));
    v.insert(upper_bound(v.begin(), v.end(), x), x);
    a[i] = x;
}
int thick(int l, int r, int k) {
    int bl = blk(l), br = blk(r), c = 0;
    if (bl == br) { for (int i = l; i <= r; i++) c += a[i] >= k; return c; }
    for (int i = l; blk(i) == bl; i++) c += a[i] >= k;
    for (int b = bl + 1; b < br; b++)                       // whole blocks: binary search
        c += s[b].end() - lower_bound(s[b].begin(), s[b].end(), k);
    for (int i = r; blk(i) == br; i--) c += a[i] >= k;
    return c;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    B = max(1, (int)sqrt(n));
    for (int i = 1; i <= n; i++) s[blk(i)].push_back(a[i]);
    for (int b = 0; b <= blk(n); b++) sort(s[b].begin(), s[b].end());
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) { int i, x; cin >> i >> x; replace(i, x); }
        else { int l, r, k; cin >> l >> r >> k; cout << thick(l, r, k) << "\n"; }
    }
}
5
5
3

Java (the replacement swaps the new value into place, which keeps the block sorted in O(B))

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

public class Main {
    static int n, B;
    static int[] a;
    static int[][] s;                                     // s[b] = block b, sorted
    static int blk(int i) { return (i - 1) / B; }
    static int lowerBound(int[] v, int k) {               // first index with v[i] >= k
        int lo = 0, hi = v.length;
        while (lo < hi) { int mid = (lo + hi) >>> 1; if (v[mid] < k) lo = mid + 1; else hi = mid; }
        return lo;
    }
    static void replace(int i, int x) {                   // fix one block: O(B)
        int[] v = s[blk(i)];
        int p = lowerBound(v, a[i]);
        v[p] = x;
        while (p > 0 && v[p - 1] > v[p]) { int t = v[p]; v[p] = v[p - 1]; v[p - 1] = t; p--; }
        while (p + 1 < v.length && v[p + 1] < v[p]) { int t = v[p]; v[p] = v[p + 1]; v[p + 1] = t; p++; }
        a[i] = x;
    }
    static int thick(int l, int r, int k) {
        int bl = blk(l), br = blk(r), c = 0;
        if (bl == br) { for (int i = l; i <= r; i++) if (a[i] >= k) c++; return c; }
        for (int i = l; blk(i) == bl; i++) if (a[i] >= k) c++;
        for (int b = bl + 1; b < br; b++) c += s[b].length - lowerBound(s[b], k);
        for (int i = r; blk(i) == br; i--) if (a[i] >= k) c++;
        return c;
    }
    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 int[n + 1];
        for (int i = 1; i <= n; i++) { in.nextToken(); a[i] = (int) in.nval; }
        B = Math.max(1, (int) Math.sqrt(n));
        int nb = blk(n) + 1;
        s = new int[nb][];
        for (int b = 0; b < nb; b++) {
            int lo = b * B + 1, hi = Math.min(n, (b + 1) * B);
            s[b] = Arrays.copyOfRange(a, lo, hi + 1);
            Arrays.sort(s[b]);
        }
        StringBuilder sb = new StringBuilder();
        while (q-- > 0) {
            in.nextToken(); int t = (int) in.nval;
            if (t == 1) { in.nextToken(); int i = (int) in.nval; in.nextToken(); replace(i, (int) in.nval); }
            else {
                in.nextToken(); int l = (int) in.nval; in.nextToken(); int r = (int) in.nval; in.nextToken(); int k = (int) in.nval;
                sb.append(thick(l, r, k)).append('\n');
            }
        }
        System.out.print(sb);
    }
}
5
5
3

Python

import sys
from bisect import bisect_left, insort
from math import isqrt

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]]
    B = max(1, isqrt(n))
    nb = (n - 1) // B + 1
    s = [sorted(a[b * B + 1:min(n, (b + 1) * B) + 1]) for b in range(nb)]   # sorted copy per block
    out, p = [], n + 2
    for _ in range(q):
        if data[p] == b"1":
            i, x = int(data[p + 1]), int(data[p + 2]); p += 3
            v = s[(i - 1) // B]
            del v[bisect_left(v, a[i])]                  # erase the old value
            insort(v, x)                                 # insert the new one
            a[i] = x
        else:
            l, r, k = int(data[p + 1]), int(data[p + 2]), int(data[p + 3]); p += 4
            bl, br = (l - 1) // B, (r - 1) // B
            if bl == br:
                out.append(sum(1 for i in range(l, r + 1) if a[i] >= k))
                continue
            c = sum(1 for i in range(l, (bl + 1) * B + 1) if a[i] >= k)
            c += sum(1 for i in range(br * B + 1, r + 1) if a[i] >= k)
            for b in range(bl + 1, br):
                c += len(s[b]) - bisect_left(s[b], k)
            out.append(c)
    print("\n".join(map(str, out)))

main()
5
5
3