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

Segment tree beats and merging tricks

queued

These are the notes for Competitive Programming episode 62. A range chmin update (a[i] = min(a[i], x) on [l, r]) cannot be a simple lazy tag: how much a block's sum drops depends on every value in it. Segment tree beats (Ji Driver's segment tree) keeps in every node the maximum, the strict second maximum and the count of the maximum: if second max < x < max, only the maxima change and the sum drops by (max − x) · count; otherwise the update goes deeper. The total work is amortised O((n + q) log n). Price Cap shows the loop (TLE), a non-strict second maximum (correct but TLE, because the stop rule never fires on equal maxima), and the accepted version. Best Streak (maximum subarray sum in a range, with point updates) shows mergeable nodes: (sum, best prefix, best suffix, best) merged in O(1); an "empty" node made of zeros prints 0 where -2 is right. 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 market inspector hangs a board at the start of every lane: the top price in the lane, how many shops charge it, and the next price below it. A government cap of ₹8 arrives. If the top is ₹9 at two shops and the next price is ₹7, only those two shops change, each by ₹1: the lane total drops by 2 without walking in. A cap of ₹5 when the next price is ₹7 changes shops by different amounts, so the inspector must walk in, lane by lane.

Problem J1 · Price Cap

(Written for this course, in the style of the classic "Gorgeous Sequence" family.)

  • Input: n q (n, q ≤ 5 · 10^5), prices a[1..n], then 1 l r x (a[i] = min(a[i], x) for l ≤ i ≤ r) or 2 l r (print the sum).
6 5
4 9 2 9 7 1
2 1 6
1 2 5 6
2 1 6
1 1 6 3
2 2 4

Answers: 32 25 8.

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 cap(int l, int r, ll x) { for (int i = l; i <= r; i++) a[i] = min(a[i], x); }
ll total(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;
            cap(l, r, x);
        } else cout << total(l, r) << "\n";
    }
}
32
25
8

Worst case: prices 1..n and full-range caps n, n − 2, n − 4, … with sums in between:

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

int n, q;
ll a[500001];

void cap(int l, int r, ll x) { for (int i = l; i <= r; i++) a[i] = min(a[i], x); }
ll total(int l, int r) {
    ll s = 0;
    for (int i = l; i <= r; i++) s += a[i];
    return s;
}

int main() {
    n = q = 500000;                         // prices 1..n, then lower and lower caps
    for (int i = 1; i <= n; i++) a[i] = i;
    ll check = 0;
    for (int i = 0; i < q; i++) {
        if (i % 2 == 0) cap(1, n, n - i);
        else check ^= total(1, n - i);
    }
    cout << check << "\n";
}
Time Limit Exceeded

Why a lazy tag can't do it

For "add x" a block's sum changes by x · length, whatever the values are. For "chmin x" the change is Σ max(0, a[i] − x), which depends on every value. A tag alone can't say how much the sum drops… unless only one distinct value changes: the maximum.

Segment tree beats

Every node keeps sum, mx1 (max), mx2 (strictly smaller second max, −∞ if none) and cnt (how many equal mx1). For an update with x on a node:

  1. x ≥ mx1: nothing changes; return.
  2. Node fully inside the range and mx2 < x: only the maxima drop: sum −= (mx1 − x) · cnt, mx1 = x. Stop.
  3. Otherwise push, recurse into both children, pull.

Push needs no separate tag: a child whose mx1 exceeds the parent's mx1 missed a cap, so cap it to the parent's maximum.

Why it is fast (sketch). Case 3 happens only when x ≤ mx2, i.e. at least two distinct values in the node become equal to x. Each such "extra" visit reduces the number of distinct values in some node; a potential argument bounds the total number of extra visits by O((n + q) log n).

A second max that isn't strict (correct, but TLE)

If equal maxima make mx2 = mx1, rule 2 (mx2 < x < mx1) can never fire on a node whose maximum appears in both children, so every update walks down to every shop with the maximum. The answers stay right:

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

int n, q, cnt[2000004];                       // cnt[v] = how many equal mx1[v]
ll a[500001], sum[2000004], mx1[2000004], mx2[2000004];   // max, second max

void pull(int v) {
    int L = 2 * v, R = 2 * v + 1;
    sum[v] = sum[L] + sum[R];
    if (mx1[L] == mx1[R]) {
        mx1[v] = mx1[L], cnt[v] = cnt[L] + cnt[R];
        mx2[v] = mx1[L];                         // "second max" = the other max
    } else if (mx1[L] > mx1[R]) {
        mx1[v] = mx1[L], cnt[v] = cnt[L];
        mx2[v] = max(mx2[L], mx1[R]);
    } else {
        mx1[v] = mx1[R], cnt[v] = cnt[R];
        mx2[v] = max(mx1[L], mx2[R]);
    }
}
void build(int v, int l, int r) {
    if (l == r) { sum[v] = mx1[v] = a[l]; mx2[v] = LLONG_MIN; cnt[v] = 1; return; }
    int m = (l + r) / 2;
    build(2 * v, l, m);
    build(2 * v + 1, m + 1, r);
    pull(v);
}
void capNode(int v, ll x) {                  // only the maxima drop to x
    if (x >= mx1[v]) return;
    sum[v] -= (mx1[v] - x) * cnt[v];
    mx1[v] = x;
}
void push(int v) { capNode(2 * v, mx1[v]); capNode(2 * v + 1, mx1[v]); }
void update(int v, int l, int r, int ql, int qr, ll x) {
    if (qr < l || r < ql || x >= mx1[v]) return;           // nothing above x here
    if (ql <= l && r <= qr && x > mx2[v]) { capNode(v, x); return; }   // only maxima change
    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);
    pull(v);
}
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);
    int m = (l + r) / 2;
    return query(2 * v, l, m, ql, qr) + query(2 * v + 1, m + 1, r, ql, qr);
}
void cap(int l, int r, ll x) { update(1, 1, n, l, r, x); }
ll total(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;
            cap(l, r, x);
        } else cout << total(l, r) << "\n";
    }
}
32
25
8

…but the worst case, where thousands of shops share the top price after a few caps:

Time Limit Exceeded

The accepted version

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

int n, q, cnt[2000004];                       // cnt[v] = how many equal mx1[v]
ll a[500001], sum[2000004], mx1[2000004], mx2[2000004];   // max, second max

void pull(int v) {
    int L = 2 * v, R = 2 * v + 1;
    sum[v] = sum[L] + sum[R];
    if (mx1[L] == mx1[R]) {
        mx1[v] = mx1[L], cnt[v] = cnt[L] + cnt[R];
        mx2[v] = max(mx2[L], mx2[R]);            // strictly below the max
    } else if (mx1[L] > mx1[R]) {
        mx1[v] = mx1[L], cnt[v] = cnt[L];
        mx2[v] = max(mx2[L], mx1[R]);
    } else {
        mx1[v] = mx1[R], cnt[v] = cnt[R];
        mx2[v] = max(mx1[L], mx2[R]);
    }
}
void build(int v, int l, int r) {
    if (l == r) { sum[v] = mx1[v] = a[l]; mx2[v] = LLONG_MIN; cnt[v] = 1; return; }
    int m = (l + r) / 2;
    build(2 * v, l, m);
    build(2 * v + 1, m + 1, r);
    pull(v);
}
void capNode(int v, ll x) {                  // only the maxima drop to x
    if (x >= mx1[v]) return;
    sum[v] -= (mx1[v] - x) * cnt[v];
    mx1[v] = x;
}
void push(int v) { capNode(2 * v, mx1[v]); capNode(2 * v + 1, mx1[v]); }
void update(int v, int l, int r, int ql, int qr, ll x) {
    if (qr < l || r < ql || x >= mx1[v]) return;           // nothing above x here
    if (ql <= l && r <= qr && x > mx2[v]) { capNode(v, x); return; }   // only maxima change
    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);
    pull(v);
}
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);
    int m = (l + r) / 2;
    return query(2 * v, l, m, ql, qr) + query(2 * v + 1, m + 1, r, ql, qr);
}
void cap(int l, int r, ll x) { update(1, 1, n, l, r, x); }
ll total(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;
            cap(l, r, x);
        } else cout << total(l, r) << "\n";
    }
}
32
25
8

One shop capped twice (8 then 2):

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

int n, q, cnt[2000004];                       // cnt[v] = how many equal mx1[v]
ll a[500001], sum[2000004], mx1[2000004], mx2[2000004];   // max, second max

void pull(int v) {
    int L = 2 * v, R = 2 * v + 1;
    sum[v] = sum[L] + sum[R];
    if (mx1[L] == mx1[R]) {
        mx1[v] = mx1[L], cnt[v] = cnt[L] + cnt[R];
        mx2[v] = max(mx2[L], mx2[R]);            // strictly below the max
    } else if (mx1[L] > mx1[R]) {
        mx1[v] = mx1[L], cnt[v] = cnt[L];
        mx2[v] = max(mx2[L], mx1[R]);
    } else {
        mx1[v] = mx1[R], cnt[v] = cnt[R];
        mx2[v] = max(mx1[L], mx2[R]);
    }
}
void build(int v, int l, int r) {
    if (l == r) { sum[v] = mx1[v] = a[l]; mx2[v] = LLONG_MIN; cnt[v] = 1; return; }
    int m = (l + r) / 2;
    build(2 * v, l, m);
    build(2 * v + 1, m + 1, r);
    pull(v);
}
void capNode(int v, ll x) {                  // only the maxima drop to x
    if (x >= mx1[v]) return;
    sum[v] -= (mx1[v] - x) * cnt[v];
    mx1[v] = x;
}
void push(int v) { capNode(2 * v, mx1[v]); capNode(2 * v + 1, mx1[v]); }
void update(int v, int l, int r, int ql, int qr, ll x) {
    if (qr < l || r < ql || x >= mx1[v]) return;           // nothing above x here
    if (ql <= l && r <= qr && x > mx2[v]) { capNode(v, x); return; }   // only maxima change
    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);
    pull(v);
}
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);
    int m = (l + r) / 2;
    return query(2 * v, l, m, ql, qr) + query(2 * v + 1, m + 1, r, ql, qr);
}
void cap(int l, int r, ll x) { update(1, 1, n, l, r, x); }
ll total(int l, int r) { return query(1, 1, n, l, r); }

int main() {
    n = q = 500000;                         // prices 1..n, then lower and lower caps
    for (int i = 1; i <= n; i++) a[i] = i;
    build(1, 1, n);
    ll check = 0;
    for (int i = 0; i < q; i++) {
        if (i % 2 == 0) cap(1, n, n - i);
        else check ^= total(1, n - i);
    }
    cout << check << "\n";
}
58015411312
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, q, cnt[2000004];                       // cnt[v] = how many equal mx1[v]
ll a[500001], sum[2000004], mx1[2000004], mx2[2000004];   // max, second max

void pull(int v) {
    int L = 2 * v, R = 2 * v + 1;
    sum[v] = sum[L] + sum[R];
    if (mx1[L] == mx1[R]) {
        mx1[v] = mx1[L], cnt[v] = cnt[L] + cnt[R];
        mx2[v] = max(mx2[L], mx2[R]);            // strictly below the max
    } else if (mx1[L] > mx1[R]) {
        mx1[v] = mx1[L], cnt[v] = cnt[L];
        mx2[v] = max(mx2[L], mx1[R]);
    } else {
        mx1[v] = mx1[R], cnt[v] = cnt[R];
        mx2[v] = max(mx1[L], mx2[R]);
    }
}
void build(int v, int l, int r) {
    if (l == r) { sum[v] = mx1[v] = a[l]; mx2[v] = LLONG_MIN; cnt[v] = 1; return; }
    int m = (l + r) / 2;
    build(2 * v, l, m);
    build(2 * v + 1, m + 1, r);
    pull(v);
}
void capNode(int v, ll x) {                  // only the maxima drop to x
    if (x >= mx1[v]) return;
    sum[v] -= (mx1[v] - x) * cnt[v];
    mx1[v] = x;
}
void push(int v) { capNode(2 * v, mx1[v]); capNode(2 * v + 1, mx1[v]); }
void update(int v, int l, int r, int ql, int qr, ll x) {
    if (qr < l || r < ql || x >= mx1[v]) return;           // nothing above x here
    if (ql <= l && r <= qr && x > mx2[v]) { capNode(v, x); return; }   // only maxima change
    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);
    pull(v);
}
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);
    int m = (l + r) / 2;
    return query(2 * v, l, m, ql, qr) + query(2 * v + 1, m + 1, r, ql, qr);
}
void cap(int l, int r, ll x) { update(1, 1, n, l, r, x); }
ll total(int l, int r) { return query(1, 1, n, l, r); }

int main() {
    mt19937 rng(62);
    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() % 10;
        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 = rng() % 10;
                cap(l, r, x);
                for (int i = l; i <= r; i++) b[i] = min(b[i], x);
            } else if (total(l, r) != accumulate(b.begin() + l, b.begin() + r + 1, 0LL)) {
                cout << "mismatch on test " << t;
                return 0;
            }
        }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Problem J2 · Best Streak

(Written for this course.)

  • Input: n q (n, q ≤ 2 · 10^5), profits a[1..n] (may be negative), then 1 i x (set day i to x) or 2 l r (print the largest sum of a non-empty run of consecutive days inside [l, r]).
7 5
3 -5 4 -1 2 -6 1
2 1 7
2 2 3
1 4 3
2 1 7
2 5 6

Answers: 5 4 9 2.

Mergeable nodes

The best streak of a block may cross its middle, so one number per node is not enough. Store four:

Field Meaning Merge of left A and right B
sum total A.sum + B.sum
pre best non-empty prefix max(A.pre, A.sum + B.pre)
suf best non-empty suffix max(B.suf, B.sum + A.suf)
best best non-empty run inside max(A.best, B.best, A.suf + B.pre)

The merge is O(1), so point updates and range queries are O(log n). The same pattern solves "longest run of equal values", "longest increasing run", bracket matching and many more: decide what a node must remember so that two neighbours can be merged.

The bug: an empty node of zeros

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

struct Node { ll sum, pre, suf, best; };      // best prefix, best suffix, best inside
Node merge(const Node &A, const Node &B) {
    return {A.sum + B.sum,
            max(A.pre, A.sum + B.pre),
            max(B.suf, B.sum + A.suf),
            max({A.best, B.best, A.suf + B.pre})};   // or a streak across the middle
}
int n, q;
ll a[200001];
Node t[800004];
const Node EMPTY = {0, 0, 0, 0};   // nothing = all zeros?

Node leaf(ll x) { return {x, x, x, x}; }
void build(int v, int l, int r) {
    if (l == r) { t[v] = leaf(a[l]); return; }
    int m = (l + r) / 2;
    build(2 * v, l, m);
    build(2 * v + 1, m + 1, r);
    t[v] = merge(t[2 * v], t[2 * v + 1]);
}
void setDay(int v, int l, int r, int i, ll x) {
    if (l == r) { t[v] = leaf(x); return; }
    int m = (l + r) / 2;
    if (i <= m) setDay(2 * v, l, m, i, x);
    else setDay(2 * v + 1, m + 1, r, i, x);
    t[v] = merge(t[2 * v], t[2 * v + 1]);
}
Node query(int v, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return EMPTY;
    if (ql <= l && r <= qr) return t[v];
    int m = (l + r) / 2;
    return merge(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, x, y;
        cin >> type >> x >> y;
        if (type == 1) setDay(1, 1, n, x, y);
        else cout << query(1, 1, n, x, y).best << "\n";
    }
}

A shop that lost money every day:

4 3
-3 -2 -4 -6
2 1 4
2 2 4
2 1 3
-2
0
0

Parts of the query outside [l, r] return EMPTY = {0, 0, 0, 0}, which pretends to be a streak worth 0 and beats every real loss. An empty node must contribute 0 to the sum but never win a comparison:

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

struct Node { ll sum, pre, suf, best; };      // best prefix, best suffix, best inside
Node merge(const Node &A, const Node &B) {
    return {A.sum + B.sum,
            max(A.pre, A.sum + B.pre),
            max(B.suf, B.sum + A.suf),
            max({A.best, B.best, A.suf + B.pre})};   // or a streak across the middle
}
int n, q;
ll a[200001];
Node t[800004];
const Node EMPTY = {0, -(ll)4e18, -(ll)4e18, -(ll)4e18};   // nothing: never the best

Node leaf(ll x) { return {x, x, x, x}; }
void build(int v, int l, int r) {
    if (l == r) { t[v] = leaf(a[l]); return; }
    int m = (l + r) / 2;
    build(2 * v, l, m);
    build(2 * v + 1, m + 1, r);
    t[v] = merge(t[2 * v], t[2 * v + 1]);
}
void setDay(int v, int l, int r, int i, ll x) {
    if (l == r) { t[v] = leaf(x); return; }
    int m = (l + r) / 2;
    if (i <= m) setDay(2 * v, l, m, i, x);
    else setDay(2 * v + 1, m + 1, r, i, x);
    t[v] = merge(t[2 * v], t[2 * v + 1]);
}
Node query(int v, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return EMPTY;
    if (ql <= l && r <= qr) return t[v];
    int m = (l + r) / 2;
    return merge(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, x, y;
        cin >> type >> x >> y;
        if (type == 1) setDay(1, 1, n, x, y);
        else cout << query(1, 1, n, x, y).best << "\n";
    }
}
-2
-2
-2
5
4
9
2

Stress test against trying every streak

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

struct Node { ll sum, pre, suf, best; };      // best prefix, best suffix, best inside
Node merge(const Node &A, const Node &B) {
    return {A.sum + B.sum,
            max(A.pre, A.sum + B.pre),
            max(B.suf, B.sum + A.suf),
            max({A.best, B.best, A.suf + B.pre})};   // or a streak across the middle
}
int n, q;
ll a[200001];
Node t[800004];
const Node EMPTY = {0, -(ll)4e18, -(ll)4e18, -(ll)4e18};   // nothing: never the best

Node leaf(ll x) { return {x, x, x, x}; }
void build(int v, int l, int r) {
    if (l == r) { t[v] = leaf(a[l]); return; }
    int m = (l + r) / 2;
    build(2 * v, l, m);
    build(2 * v + 1, m + 1, r);
    t[v] = merge(t[2 * v], t[2 * v + 1]);
}
void setDay(int v, int l, int r, int i, ll x) {
    if (l == r) { t[v] = leaf(x); return; }
    int m = (l + r) / 2;
    if (i <= m) setDay(2 * v, l, m, i, x);
    else setDay(2 * v + 1, m + 1, r, i, x);
    t[v] = merge(t[2 * v], t[2 * v + 1]);
}
Node query(int v, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return EMPTY;
    if (ql <= l && r <= qr) return t[v];
    int m = (l + r) / 2;
    return merge(query(2 * v, l, m, ql, qr), query(2 * v + 1, m + 1, r, ql, qr));
}

int main() {
    mt19937 rng(62);
    for (int t = 1; t <= 500; t++) {
        n = rng() % 12 + 1;
        for (int i = 1; i <= n; i++) a[i] = (ll)(rng() % 11) - 7;      // mostly losses
        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() % 11) - 7;
                a[l] = x;
                setDay(1, 1, n, l, x);
                continue;
            }
            ll best = LLONG_MIN;
            for (int i = l; i <= r; i++) {
                ll s = 0;
                for (int j = i; j <= r; j++) s += a[j], best = max(best, s);
            }
            if (query(1, 1, n, l, r).best != best) { cout << "mismatch on test " << t; return 0; }
        }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Complexity vs the constraints

Method Time Verdict
J1: loop O(n) per operation TLE
J1: second max not strict O(n) per update on equal maxima TLE
J1: segment tree beats O((n + q) log n) amortised accepted
J2: Kadane per query O(n) per query too slow for 2 · 10^5 full queries
J2: mergeable nodes O(log n) per operation accepted

Common mistakes (and the real outputs)

Mistake What you see Why Fix
loop over the range Time Limit Exceeded O(n · q) beats
mx2 = mx1 when the maxima are equal Time Limit Exceeded rule 2 never fires strict second max
no push in beats wrong sums children miss a cap cap children to the parent max
rule 2 without "fully inside" wrong sums caps outside [l, r] check ql ≤ l && r ≤ qr
empty node = zeros 0 (expected -2) 0 beats real losses −∞ pre, suf, best
best = max(A.best, B.best) too small the crossing run is missed + A.suf + B.pre
mx2 initialised to 0 wrong with 0 or negatives 0 can be a real value LLONG_MIN

Mini project

Implement the full "Gorgeous Sequence" tree: range chmin, range max and range sum (homework 2), then add range chmax and range add (keeping max, second max, count and the mirrored min, second min, count). Stress it with small values (0–5) so that equal values and collisions between max and min happen often.

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 was also checked against brute force on 150 random cases.

1. Range chmax (the mirror image). 1 l r x: a[i] = max(a[i], x); 2 l r: sum.

Solution

max(a, x) = −min(−a, −x): store −a, cap with −x, and negate the sums. (Or mirror the code with min, second min and count.) Sample: 1 5 2 8 3, chmax all with 4 → 25; chmax [2, 3] with 6 → sum of [1, 3] = 16.

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

int n, q, cnt[2000004];                       // cnt[v] = how many equal mx1[v]
ll a[500001], sum[2000004], mx1[2000004], mx2[2000004];   // max, second max

void pull(int v) {
    int L = 2 * v, R = 2 * v + 1;
    sum[v] = sum[L] + sum[R];
    if (mx1[L] == mx1[R]) {
        mx1[v] = mx1[L], cnt[v] = cnt[L] + cnt[R];
        mx2[v] = max(mx2[L], mx2[R]);            // strictly below the max
    } else if (mx1[L] > mx1[R]) {
        mx1[v] = mx1[L], cnt[v] = cnt[L];
        mx2[v] = max(mx2[L], mx1[R]);
    } else {
        mx1[v] = mx1[R], cnt[v] = cnt[R];
        mx2[v] = max(mx1[L], mx2[R]);
    }
}
void build(int v, int l, int r) {
    if (l == r) { sum[v] = mx1[v] = a[l]; mx2[v] = LLONG_MIN; cnt[v] = 1; return; }
    int m = (l + r) / 2;
    build(2 * v, l, m);
    build(2 * v + 1, m + 1, r);
    pull(v);
}
void capNode(int v, ll x) {                  // only the maxima drop to x
    if (x >= mx1[v]) return;
    sum[v] -= (mx1[v] - x) * cnt[v];
    mx1[v] = x;
}
void push(int v) { capNode(2 * v, mx1[v]); capNode(2 * v + 1, mx1[v]); }
void update(int v, int l, int r, int ql, int qr, ll x) {
    if (qr < l || r < ql || x >= mx1[v]) return;           // nothing above x here
    if (ql <= l && r <= qr && x > mx2[v]) { capNode(v, x); return; }   // only maxima change
    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);
    pull(v);
}
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);
    int m = (l + r) / 2;
    return query(2 * v, l, m, ql, qr) + query(2 * v + 1, m + 1, r, ql, qr);
}
void cap(int l, int r, ll x) { update(1, 1, n, l, r, x); }
ll total(int l, int r) { return query(1, 1, n, l, r); }

int main() {
    // range chmax: a[i] = max(a[i], x). Store -a: max(a, x) = -min(-a, -x)
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i], a[i] = -a[i];
    build(1, 1, n);
    while (q--) {
        int type, l, r;
        cin >> type >> l >> r;
        if (type == 1) {
            ll x;
            cin >> x;
            cap(l, r, -x);
        } else cout << -total(l, r) << "\n";
    }
}
25
16

2. Chmin + range max + range sum. 1 l r x cap, 2 l r max, 3 l r sum.

Solution

The beats node already has mx1; a range max query just combines mx1 with pushes on the way.

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

int n, q, cnt[2000004];                       // cnt[v] = how many equal mx1[v]
ll a[500001], sum[2000004], mx1[2000004], mx2[2000004];   // max, second max

void pull(int v) {
    int L = 2 * v, R = 2 * v + 1;
    sum[v] = sum[L] + sum[R];
    if (mx1[L] == mx1[R]) {
        mx1[v] = mx1[L], cnt[v] = cnt[L] + cnt[R];
        mx2[v] = max(mx2[L], mx2[R]);            // strictly below the max
    } else if (mx1[L] > mx1[R]) {
        mx1[v] = mx1[L], cnt[v] = cnt[L];
        mx2[v] = max(mx2[L], mx1[R]);
    } else {
        mx1[v] = mx1[R], cnt[v] = cnt[R];
        mx2[v] = max(mx1[L], mx2[R]);
    }
}
void build(int v, int l, int r) {
    if (l == r) { sum[v] = mx1[v] = a[l]; mx2[v] = LLONG_MIN; cnt[v] = 1; return; }
    int m = (l + r) / 2;
    build(2 * v, l, m);
    build(2 * v + 1, m + 1, r);
    pull(v);
}
void capNode(int v, ll x) {                  // only the maxima drop to x
    if (x >= mx1[v]) return;
    sum[v] -= (mx1[v] - x) * cnt[v];
    mx1[v] = x;
}
void push(int v) { capNode(2 * v, mx1[v]); capNode(2 * v + 1, mx1[v]); }
void update(int v, int l, int r, int ql, int qr, ll x) {
    if (qr < l || r < ql || x >= mx1[v]) return;           // nothing above x here
    if (ql <= l && r <= qr && x > mx2[v]) { capNode(v, x); return; }   // only maxima change
    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);
    pull(v);
}
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);
    int m = (l + r) / 2;
    return query(2 * v, l, m, ql, qr) + query(2 * v + 1, m + 1, r, ql, qr);
}
void cap(int l, int r, ll x) { update(1, 1, n, l, r, x); }
ll total(int l, int r) { return query(1, 1, n, l, r); }

ll best(int v, int l, int r, int ql, int qr) {     // range maximum: mx1 is already there
    if (qr < l || r < ql) return LLONG_MIN;
    if (ql <= l && r <= qr) return mx1[v];
    push(v);
    int m = (l + r) / 2;
    return max(best(2 * v, l, m, ql, qr), best(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 x; cin >> x; cap(l, r, x); }
        else if (type == 2) cout << best(1, 1, n, l, r) << "\n";
        else cout << total(l, r) << "\n";
    }
}
9
6
25
4

3. Longest run of equal values in [l, r], with point updates.

Solution

A node keeps its length, the run at its left end, the run at its right end, the best run inside, and its leftmost and rightmost values. If A's right value equals B's left value, the runs join in the middle.

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

// Longest run of equal values inside [l, r], with point updates.
struct Node { int len, pre, suf, best, lv, rv; };   // run at the left end, at the right end, best inside
Node merge(const Node &A, const Node &B) {
    if (A.len == 0) return B;
    if (B.len == 0) return A;
    Node C{A.len + B.len, A.pre, B.suf, max(A.best, B.best), A.lv, B.rv};
    if (A.rv == B.lv) {                              // the runs touch in the middle
        C.best = max(C.best, A.suf + B.pre);
        if (A.pre == A.len) C.pre = A.len + B.pre;
        if (B.suf == B.len) C.suf = B.len + A.suf;
    }
    return C;
}
int n, q, a[200001];
Node t[800004];
const Node EMPTY{0, 0, 0, 0, 0, 0};
Node leaf(int x) { return {1, 1, 1, 1, x, x}; }
void build(int v, int l, int r) {
    if (l == r) { t[v] = leaf(a[l]); return; }
    int m = (l + r) / 2;
    build(2 * v, l, m); build(2 * v + 1, m + 1, r);
    t[v] = merge(t[2 * v], t[2 * v + 1]);
}
void setVal(int v, int l, int r, int i, int x) {
    if (l == r) { t[v] = leaf(x); return; }
    int m = (l + r) / 2;
    if (i <= m) setVal(2 * v, l, m, i, x); else setVal(2 * v + 1, m + 1, r, i, x);
    t[v] = merge(t[2 * v], t[2 * v + 1]);
}
Node query(int v, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return EMPTY;
    if (ql <= l && r <= qr) return t[v];
    int m = (l + r) / 2;
    return merge(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, x, y;
        cin >> type >> x >> y;
        if (type == 1) setVal(1, 1, n, x, y);
        else cout << query(1, 1, n, x, y).best << "\n";
    }
}
3
2
4

4. Count streaks with a positive total (the whole array, no updates).

Solution

With prefix sums p, the run (i, j] has a positive total exactly when p[j] > p[i]. Count pairs i < j with p[i] < p[j] using coordinate compression and a Fenwick tree (episode 63): O(n log n). Sample 3 -5 4 -1 2 has 9 such streaks.

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

// Count streaks (subarrays) with a positive total = pairs i < j with p[j] > p[i] (prefix sums).
int main() {
    int n;
    cin >> n;
    vector<ll> p(n + 1, 0);
    for (int i = 1; i <= n; i++) { ll x; cin >> x; p[i] = p[i - 1] + x; }
    vector<ll> vals(p);                          // coordinate-compress the prefix sums
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    int m = vals.size();
    vector<int> bit(m + 1, 0);
    ll count = 0;
    for (int j = 0; j <= n; j++) {
        int id = lower_bound(vals.begin(), vals.end(), p[j]) - vals.begin();   // # of values < p[j]
        for (int i = id; i > 0; i -= i & -i) count += bit[i];                // earlier prefixes smaller than p[j]
        for (int i = id + 1; i <= m; i += i & -i) bit[i]++;
    }
    cout << count << "\n";
}
9

Quick quiz

Merge A = (sum 2, pre 3, suf 2, best 4) with B = (sum −1, pre 5, suf 1, best 5). What is the new best?

A) 5 · B) 7 · C) 9 · D) 4

Answer

B. max(4, 5, A.suf + B.pre = 2 + 5) = 7: the best run crosses the middle.

Interview questions

  1. Why can't range chmin be a normal lazy tag? The change of a block's sum depends on every value in it, not just on x and the length.
  2. What does a segment tree beats node store? Sum, maximum, strict second maximum, count of the maximum.
  3. When does the update stop at a node? When x ≥ max (nothing to do), or when the node is inside the range and second max < x < max (only the maxima change).
  4. Why must the second maximum be strict? Otherwise equal maxima block the stop rule and every update visits all of them.
  5. What is the complexity? Amortised O((n + q) log n) for chmin + sum (O((n + q) log² n) with range adds too).
  6. How do you design a mergeable node? Decide what information about a block lets you compute the same information for the concatenation of two blocks (e.g. sum, best prefix, best suffix, best).
  7. What should a query return outside the range? An identity element: merging with it changes nothing, and it can never "win".

Glossary

Term Meaning Example
Range chmin a[i] = min(a[i], x) for i in [l, r] a price cap
Range chmax a[i] = max(a[i], x) homework 1
Segment tree beats A segment tree that stops when only the maxima change, otherwise goes deeper J1
Strict second maximum The largest value strictly below the maximum 7 in 9 9 7
Count of the maximum How many values equal the maximum 2 for 9 9 7
Amortised complexity A bound on the total work over all operations O((n + q) log n)
Potential argument Counting a quantity that only decreases to bound total work distinct values
pull Recompute a node from its children pull(v)
push Pass a pending change to the children cap to the parent max
Mergeable node Information that two neighbouring blocks can combine in O(1) sum, pre, suf, best
Prefix / suffix A run starting at the left end / ending at the right end pre, suf
Maximum subarray sum The largest total of a non-empty run best streak
Kadane's algorithm O(n) maximum subarray scan the slow J2 query
Identity element A value that changes nothing when merged EMPTY
Sentinel A special "impossible" value −4 · 10^18
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 non-strict second max
Wrong Answer (WA) A wrong output 0
Fenwick tree A compact tree for prefix sums next episode

Summary

  • A range chmin is not a simple tag; segment tree beats stores max, strict second max and count.
  • Stop when second max < x < max (sum −= (max − x) · cnt); otherwise go deeper; push caps children to the parent max.
  • A non-strict second max is correct but TLE.
  • Mergeable nodes carry exactly what a merge needs: sum, best prefix, best suffix, best.
  • The empty node must never win (0 instead of -2 otherwise).

Solutions in C++, Java and Python

Problem J1 · Price Cap

C++

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

int n, q, cnt[2000004];                       // cnt[v] = how many equal mx1[v]
ll a[500001], sum[2000004], mx1[2000004], mx2[2000004];   // max, second max

void pull(int v) {
    int L = 2 * v, R = 2 * v + 1;
    sum[v] = sum[L] + sum[R];
    if (mx1[L] == mx1[R]) {
        mx1[v] = mx1[L], cnt[v] = cnt[L] + cnt[R];
        mx2[v] = max(mx2[L], mx2[R]);            // strictly below the max
    } else if (mx1[L] > mx1[R]) {
        mx1[v] = mx1[L], cnt[v] = cnt[L];
        mx2[v] = max(mx2[L], mx1[R]);
    } else {
        mx1[v] = mx1[R], cnt[v] = cnt[R];
        mx2[v] = max(mx1[L], mx2[R]);
    }
}
void build(int v, int l, int r) {
    if (l == r) { sum[v] = mx1[v] = a[l]; mx2[v] = LLONG_MIN; cnt[v] = 1; return; }
    int m = (l + r) / 2;
    build(2 * v, l, m);
    build(2 * v + 1, m + 1, r);
    pull(v);
}
void capNode(int v, ll x) {                  // only the maxima drop to x
    if (x >= mx1[v]) return;
    sum[v] -= (mx1[v] - x) * cnt[v];
    mx1[v] = x;
}
void push(int v) { capNode(2 * v, mx1[v]); capNode(2 * v + 1, mx1[v]); }
void update(int v, int l, int r, int ql, int qr, ll x) {
    if (qr < l || r < ql || x >= mx1[v]) return;           // nothing above x here
    if (ql <= l && r <= qr && x > mx2[v]) { capNode(v, x); return; }   // only maxima change
    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);
    pull(v);
}
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);
    int m = (l + r) / 2;
    return query(2 * v, l, m, ql, qr) + query(2 * v + 1, m + 1, r, ql, qr);
}
void cap(int l, int r, ll x) { update(1, 1, n, l, r, x); }
ll total(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;
            cap(l, r, x);
        } else cout << total(l, r) << "\n";
    }
}

Java

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

public class Main {
    static int n;
    static long[] sum, mx1, mx2;          // max, strict second max
    static int[] cnt;                     // how many equal the max

    static void pull(int v) {
        int L = 2 * v, R = 2 * v + 1;
        sum[v] = sum[L] + sum[R];
        if (mx1[L] == mx1[R]) { mx1[v] = mx1[L]; cnt[v] = cnt[L] + cnt[R]; mx2[v] = Math.max(mx2[L], mx2[R]); }
        else if (mx1[L] > mx1[R]) { mx1[v] = mx1[L]; cnt[v] = cnt[L]; mx2[v] = Math.max(mx2[L], mx1[R]); }
        else { mx1[v] = mx1[R]; cnt[v] = cnt[R]; mx2[v] = Math.max(mx1[L], mx2[R]); }
    }
    static void build(int v, int l, int r, long[] a) {
        if (l == r) { sum[v] = mx1[v] = a[l]; mx2[v] = Long.MIN_VALUE; cnt[v] = 1; return; }
        int m = (l + r) / 2;
        build(2 * v, l, m, a); build(2 * v + 1, m + 1, r, a);
        pull(v);
    }
    static void capNode(int v, long x) {                  // only the maxima drop to x
        if (x >= mx1[v]) return;
        sum[v] -= (mx1[v] - x) * cnt[v];
        mx1[v] = x;
    }
    static void push(int v) { capNode(2 * v, mx1[v]); capNode(2 * v + 1, mx1[v]); }
    static void update(int v, int l, int r, int ql, int qr, long x) {
        if (qr < l || r < ql || x >= mx1[v]) return;
        if (ql <= l && r <= qr && x > mx2[v]) { capNode(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);
        pull(v);
    }
    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);
        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;
        long[] a = new long[n + 1];
        for (int i = 1; i <= n; i++) { in.nextToken(); a[i] = (long) in.nval; }
        sum = new long[4 * n + 4]; mx1 = new long[4 * n + 4]; mx2 = new long[4 * n + 4]; cnt = new int[4 * n + 4];
        build(1, 1, n, a);
        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);
    }
}
32
25
8

Python (recursive; fine for small inputs)

import sys

NEG = float("-inf")

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, m1, m2, cnt = [0] * size, [0] * size, [NEG] * size, [0] * size

    def pull(v):
        L, R = 2 * v, 2 * v + 1
        s[v] = s[L] + s[R]
        if m1[L] == m1[R]:
            m1[v], cnt[v], m2[v] = m1[L], cnt[L] + cnt[R], max(m2[L], m2[R])
        elif m1[L] > m1[R]:
            m1[v], cnt[v], m2[v] = m1[L], cnt[L], max(m2[L], m1[R])
        else:
            m1[v], cnt[v], m2[v] = m1[R], cnt[R], max(m1[L], m2[R])

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

    def cap_node(v, x):                       # only the maxima drop to x
        if x < m1[v]:
            s[v] -= (m1[v] - x) * cnt[v]; m1[v] = x

    def push(v):
        cap_node(2 * v, m1[v]); cap_node(2 * v + 1, m1[v])

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

    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)
        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()
32
25
8

Problem J2 · Best Streak

C++

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

struct Node { ll sum, pre, suf, best; };      // best prefix, best suffix, best inside
Node merge(const Node &A, const Node &B) {
    return {A.sum + B.sum,
            max(A.pre, A.sum + B.pre),
            max(B.suf, B.sum + A.suf),
            max({A.best, B.best, A.suf + B.pre})};   // or a streak across the middle
}
int n, q;
ll a[200001];
Node t[800004];
const Node EMPTY = {0, -(ll)4e18, -(ll)4e18, -(ll)4e18};   // nothing: never the best

Node leaf(ll x) { return {x, x, x, x}; }
void build(int v, int l, int r) {
    if (l == r) { t[v] = leaf(a[l]); return; }
    int m = (l + r) / 2;
    build(2 * v, l, m);
    build(2 * v + 1, m + 1, r);
    t[v] = merge(t[2 * v], t[2 * v + 1]);
}
void setDay(int v, int l, int r, int i, ll x) {
    if (l == r) { t[v] = leaf(x); return; }
    int m = (l + r) / 2;
    if (i <= m) setDay(2 * v, l, m, i, x);
    else setDay(2 * v + 1, m + 1, r, i, x);
    t[v] = merge(t[2 * v], t[2 * v + 1]);
}
Node query(int v, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return EMPTY;
    if (ql <= l && r <= qr) return t[v];
    int m = (l + r) / 2;
    return merge(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, x, y;
        cin >> type >> x >> y;
        if (type == 1) setDay(1, 1, n, x, y);
        else cout << query(1, 1, n, x, y).best << "\n";
    }
}

Java

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

public class Main {
    static final long NEG = -4_000_000_000_000_000_000L;
    static long[][] t;                     // t[v] = {sum, pre, suf, best}
    static int n;

    static long[] merge(long[] A, long[] B) {
        return new long[]{A[0] + B[0], Math.max(A[1], A[0] + B[1]), Math.max(B[2], B[0] + A[2]),
                          Math.max(Math.max(A[3], B[3]), A[2] + B[1])};
    }
    static final long[] EMPTY = {0, NEG, NEG, NEG};          // nothing: never the best
    static long[] leaf(long x) { return new long[]{x, x, x, x}; }
    static void build(int v, int l, int r, long[] a) {
        if (l == r) { t[v] = leaf(a[l]); return; }
        int m = (l + r) / 2;
        build(2 * v, l, m, a); build(2 * v + 1, m + 1, r, a);
        t[v] = merge(t[2 * v], t[2 * v + 1]);
    }
    static void setDay(int v, int l, int r, int i, long x) {
        if (l == r) { t[v] = leaf(x); return; }
        int m = (l + r) / 2;
        if (i <= m) setDay(2 * v, l, m, i, x); else setDay(2 * v + 1, m + 1, r, i, x);
        t[v] = merge(t[2 * v], t[2 * v + 1]);
    }
    static long[] query(int v, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return EMPTY;
        if (ql <= l && r <= qr) return t[v];
        int m = (l + r) / 2;
        return merge(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;
        long[] a = new long[n + 1];
        for (int i = 1; i <= n; i++) { in.nextToken(); a[i] = (long) in.nval; }
        t = new long[4 * n + 4][];
        build(1, 1, n, a);
        StringBuilder sb = new StringBuilder();
        while (q-- > 0) {
            in.nextToken(); int type = (int) in.nval;
            in.nextToken(); int x = (int) in.nval; in.nextToken(); long y = (long) in.nval;
            if (type == 1) setDay(1, 1, n, x, y);
            else sb.append(query(1, 1, n, x, (int) y)[3]).append('\n');
        }
        System.out.print(sb);
    }
}
5
4
9
2

Python

import sys

NEG = float("-inf")
EMPTY = (0, NEG, NEG, NEG)                    # nothing: never the best

def merge(A, B):
    return (A[0] + B[0], max(A[1], A[0] + B[1]), max(B[2], B[0] + A[2]), max(A[3], B[3], A[2] + B[1]))

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]]
    t = [None] * (4 * n + 4)

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

    def set_day(v, l, r, i, x):
        if l == r:
            t[v] = (x,) * 4; return
        m = (l + r) // 2
        if i <= m: set_day(2 * v, l, m, i, x)
        else: set_day(2 * v + 1, m + 1, r, i, x)
        t[v] = merge(t[2 * v], t[2 * v + 1])

    def query(v, l, r, ql, qr):
        if qr < l or r < ql: return EMPTY
        if ql <= l and r <= qr: return t[v]
        m = (l + r) // 2
        return merge(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):
        ty, x, y = int(data[p]), int(data[p + 1]), int(data[p + 2]); p += 3
        if ty == 1: set_day(1, 1, n, x, y)
        else: out.append(query(1, 1, n, x, y)[3])
    print("\n".join(map(str, out)))

main()
5
4
9
2