Why this matters when you build with AI
An AI tool will write a segment tree quickly, and most of the code will compile. The bugs sit in three places: the identity element, the order of the merge, and the size of the tree. A tree for "best subarray sum" that uses 0 as the identity gives 0 when every value is negative, and the code does not crash. A tree that merges left and right halves in the wrong order gives right answers on sums and wrong answers on anything that depends on position. A tree built on a size that is not a power of two can return a position past the end of the array during a search.
The way to catch these is a brute force on random small inputs, which this lesson uses for every structure. The rest of this lesson shows how each bug looks in real output.
Every program here was compiled with g++ -O2 -std=c++17 -Wall -Wextra on the machine that wrote the lesson, using g++ 15.2.0 (checked with g++ --version). Each structure was checked against a brute force on 2000 random arrays with a fixed seed, with 60 random operations on each array, and the printed outputs were copied from those runs. Timing figures come from one run on that machine and will differ on yours. No outside source was checked for this lesson.
The idea: a monoid is a merge rule with an identity
A segment tree answers a query over a range by combining values. The combining rule must follow three laws to be safe. The type is T. The merge op(a, b) must be associative, so op(op(a, b), c) equals op(a, op(b, c)). There must be an identity id with op(id, a) = op(a, id) = a. A structure with those two properties is a monoid.
Associativity is what lets the tree split a range into pieces and merge the pieces in any grouping. Commutativity is not needed. The operands must still stay in array order, because op(a, b) and op(b, a) differ for many monoids.
Examples used in this lesson:
monoid element T identity merge op(a, b)
sum integer 0 a + b
min with index (value, index) (+infinity, +infinity) the smaller pair, so the smaller value and then the smaller index
min with count (value, how many times) (+infinity, 0) keep the smaller value, add counts when equal
max subarray (sum, best prefix, best (0, -infinity, -infinity, see the code, the identity is the empty segment
suffix, best inside) -infinity)The identity matters most for max subarray. The identity stands for "no elements at all". A query on an empty range must return it. The subarray rule requires non-empty choices, so the identity cannot offer a sum of 0 as a candidate. Its best value must be minus infinity. The worked failure at the end of this lesson shows what happens when 0 is used instead.
A tree over an array: leaves and internal nodes
Take the array a = [4, -3, 5, -2, -1, 2, 6, -2]. Pad its length to a power of two, here 8. The leaves hold the values, and each internal node holds the merge of its two children. Store the tree in one array t of size 2n, with leaf i at position n + i, and with the parent of node p at p / 2.
node covers value
1 all 8 9
2 first 4 4
3 last 4 5
4 indices 0-1 1
5 indices 2-3 3
6 indices 4-5 1
7 indices 6-7 4
8..15 one index each 4 -3 5 -2 -1 2 6 -2The root is 9, which is the sum of the array. The demo printed sum[0,8)=9.
Iterative bottom-up query
A query asks for the merge of the half-open range [l, r). The bottom-up method starts with l and r at the leaves and moves up. At each level, if l is a right child (odd), its node covers a piece that belongs in the left part of the answer, so take it and move l right. If r is a right child (odd), step r down by one and take that node for the right part.
Worked trace on the tree above, query [2, 7). Here n = 8, so l = 10 and r = 15.
l = 10is even, so skip it.r = 15is odd, sorbecomes 14 and node 14 (index 6 alone) goes to the right part. Nowl = 5andr = 7.l = 5is odd, so node 5 (indices 2 and 3) goes to the left part, andlbecomes 6.r = 7is odd, sorbecomes 6 and node 6 (indices 4 and 5) goes to the right part, in front of node 14. Nowl = 3,r = 3, and the loop stops.
The answer is the left part (indices 2, 3) merged with the right part (indices 4, 5 then 6). That covers indices 2 to 6, which is [2, 7). Both parts are kept apart until the end, so the merge always puts the earlier index on the left.
The code keeps the two parts in two variables for that reason. An AI tool often writes one accumulator and merges every node into it in the order the loop meets it. That is correct for commutative monoids, such as sum and min, and wrong for the max subarray merge.
The point update changes a leaf and then recomputes its ancestors. Starting at p = n + i, set the leaf, then move to the parent and recompute t[p] = op(t[2p], t[2p + 1]) until the root is done. That is log2(n) merges.
Recursive version
The recursive tree uses the same merge with a different layout. Node k covers a range [l, r). Its children are 2k and 2k + 1 covering the two halves. A query stops at nodes that lie fully inside the range, and returns the identity for nodes that lie fully outside. Each query visits O(log n) nodes, and the constant is larger than the bottom-up version.
The recursive version does not need n to be a power of two, and it is easier to read. Use it when the problem needs a custom split, and use the bottom-up version for speed. The code below uses both, and the stress test checks both against the brute force on the same operations.
The code
The file below holds the monoids, the two trees, the brute force, a demo, a stress test, and the task reader for the worked problem. Compile with g++ -O2 -std=c++17 -Wall -Wextra -o seg seg.cpp.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// A monoid M has a type T, an identity id() and an associative op(a, b).
// The tree never assumes op is commutative, so the order of the operands matters.
struct SumM {
using T = ll;
static T id() { return 0; }
static T op(const T& a, const T& b) { return a + b; }
static T leaf(ll x) { return x; }
};
// (smallest value, index of its first occurrence)
struct MinIdxM {
using T = pair<ll, int>;
static T id() { return {LLONG_MAX, INT_MAX}; }
static T op(const T& a, const T& b) { return min(a, b); }
static T leaf(ll x, int idx) { return {x, idx}; }
};
// (smallest value, how many times it occurs)
struct MinCntM {
using T = pair<ll, ll>;
static T id() { return {LLONG_MAX, 0}; }
static T op(const T& a, const T& b) {
if (a.first < b.first) return a;
if (b.first < a.first) return b;
return {a.first, a.second + b.second};
}
static T leaf(ll x) { return {x, 1}; }
};
// Best non-empty contiguous sum. The identity is the empty segment, so its
// prefix, suffix and best are NEG (no non-empty choice exists).
struct MaxSubM {
struct Node {
ll sum, pref, suf, best;
};
using T = Node;
static constexpr ll NEG = -(1LL << 60);
static T id() { return {0, NEG, NEG, NEG}; }
static T leaf(ll x) { return {x, x, x, x}; }
static T op(const T& a, const T& b) {
T r;
r.sum = a.sum + b.sum;
r.pref = max(a.pref, a.sum + b.pref);
r.suf = max(b.suf, b.sum + a.suf);
r.best = max({a.best, b.best, a.suf + b.pref});
return r;
}
};
// Iterative bottom-up tree. Leaves live at t[n .. 2n-1], n is a power of two.
template <class M>
struct IterSeg {
using T = typename M::T;
int len; // real number of positions
int n; // padded size, a power of two
vector<T> t;
explicit IterSeg(const vector<T>& leaves) : len((int)leaves.size()) {
n = 1;
while (n < len) n <<= 1;
t.assign(2 * n, M::id());
for (int i = 0; i < len; i++) t[n + i] = leaves[i];
for (int i = n - 1; i >= 1; i--) t[i] = M::op(t[2 * i], t[2 * i + 1]);
}
// Replace the value at position p.
void set(int p, const T& v) {
p += n;
t[p] = v;
for (p >>= 1; p >= 1; p >>= 1) t[p] = M::op(t[2 * p], t[2 * p + 1]);
}
// Aggregate over the half-open range [l, r). Left parts and right parts
// are kept apart so the order of operands stays correct.
T query(int l, int r) const {
T left = M::id(), right = M::id();
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) left = M::op(left, t[l++]);
if (r & 1) right = M::op(t[--r], right);
}
return M::op(left, right);
}
// Largest r such that pred(query(l, r)) is true, given that pred is
// monotone (true for a prefix of r values) and pred(id) is true.
// Use it as first_true(l, pred) = max_right(l, not pred) to find the first
// position p >= l where pred(query(l, p + 1)) becomes true, or len if none.
template <class P>
int max_right(int l, P pred) const {
if (l == len) return len;
l += n;
T sum = M::id();
do {
while (l % 2 == 0) l >>= 1;
if (!pred(M::op(sum, t[l]))) {
while (l < n) {
l = 2 * l;
if (pred(M::op(sum, t[l]))) {
sum = M::op(sum, t[l]);
l++;
}
}
return l - n;
}
sum = M::op(sum, t[l]);
l++;
} while ((l & -l) != l);
return len;
}
};
// Recursive tree on the half-open range [l, r) of node k.
template <class M>
struct RecSeg {
using T = typename M::T;
int n;
vector<T> t;
explicit RecSeg(const vector<T>& leaves) : n((int)leaves.size()), t(4 * leaves.size(), M::id()) {
build(1, 0, n, leaves);
}
void build(int k, int l, int r, const vector<T>& leaves) {
if (r - l == 1) {
t[k] = leaves[l];
return;
}
int m = (l + r) / 2;
build(2 * k, l, m, leaves);
build(2 * k + 1, m, r, leaves);
t[k] = M::op(t[2 * k], t[2 * k + 1]);
}
void set(int k, int l, int r, int p, const T& v) {
if (r - l == 1) {
t[k] = v;
return;
}
int m = (l + r) / 2;
if (p < m) set(2 * k, l, m, p, v);
else set(2 * k + 1, m, r, p, v);
t[k] = M::op(t[2 * k], t[2 * k + 1]);
}
T query(int k, int l, int r, int ql, int qr) const {
if (qr <= l || r <= ql) return M::id();
if (ql <= l && r <= qr) return t[k];
int m = (l + r) / 2;
return M::op(query(2 * k, l, m, ql, qr), query(2 * k + 1, m, r, ql, qr));
}
};
// Brute force helpers used by the tests.
ll brute_maxsub(const vector<ll>& a, int l, int r) {
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);
}
}
return best;
}
void demo() {
vector<ll> a = {4, -3, 5, -2, -1, 2, 6, -2};
IterSeg<SumM> s(a);
printf("sum[0,8)=%lld sum[2,5)=%lld\n", s.query(0, 8), s.query(2, 5));
s.set(1, 10);
printf("after a[1]=10 sum[0,8)=%lld\n", s.query(0, 8));
vector<pair<ll, int>> leaves;
for (int i = 0; i < (int)a.size(); i++) leaves.push_back(MinIdxM::leaf(a[i], i));
IterSeg<MinIdxM> mn(leaves);
auto r1 = mn.query(0, 8);
printf("min[0,8)=%lld first index=%d\n", r1.first, r1.second);
vector<pair<ll, ll>> cl;
for (ll x : {3, 1, 4, 1, 5, 1, 2}) cl.push_back(MinCntM::leaf(x));
IterSeg<MinCntM> mc(cl);
auto r2 = mc.query(0, 7);
printf("min and count over all: value=%lld count=%lld\n", r2.first, r2.second);
vector<MaxSubM::T> ms;
for (ll x : a) ms.push_back(MaxSubM::leaf(x));
IterSeg<MaxSubM> best(ms);
printf("max subarray [0,8)=%lld, brute=%lld\n", best.query(0, 8).best, brute_maxsub(a, 0, 8));
printf("max subarray [4,8)=%lld, brute=%lld\n", best.query(4, 8).best, brute_maxsub(a, 4, 8));
// Descent: first position p >= 0 where the best sum of a[0..p] reaches 9.
int p = best.max_right(0, [](const MaxSubM::T& x) { return x.best < 9; });
printf("first p with best sum >= 9 starting at 0: %d\n", p);
}
int main(int argc, char** argv) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (argc > 1 && string(argv[1]) == "demo") {
demo();
return 0;
}
if (argc > 1 && string(argv[1]) == "stress") {
mt19937 rng(20261108);
auto rnd = [&](int lo, int hi) { return uniform_int_distribution<int>(lo, hi)(rng); };
for (int it = 0; it < 2000; it++) {
int n = rnd(1, 13);
vector<ll> a(n);
for (auto& x : a) x = rnd(-9, 9);
vector<SumM::T> s1;
vector<MinIdxM::T> s2;
vector<MinCntM::T> s3;
vector<MaxSubM::T> s4;
for (ll x : a) {
s1.push_back(SumM::leaf(x));
s4.push_back(MaxSubM::leaf(x));
}
for (int i = 0; i < n; i++) s2.push_back(MinIdxM::leaf(a[i], i));
for (ll x : a) s3.push_back(MinCntM::leaf(x));
IterSeg<SumM> it1(s1);
IterSeg<MinIdxM> it2(s2);
IterSeg<MinCntM> it3(s3);
IterSeg<MaxSubM> it4(s4);
RecSeg<SumM> rc1(s1);
RecSeg<MaxSubM> rc4(s4);
for (int q = 0; q < 60; q++) {
int op = rnd(0, 3);
if (op == 0) {
int p = rnd(0, n - 1);
ll v = rnd(-9, 9);
a[p] = v;
it1.set(p, SumM::leaf(v));
it2.set(p, MinIdxM::leaf(v, p));
it3.set(p, MinCntM::leaf(v));
it4.set(p, MaxSubM::leaf(v));
rc1.set(1, 0, n, p, SumM::leaf(v));
rc4.set(1, 0, n, p, MaxSubM::leaf(v));
continue;
}
int l = rnd(0, n - 1), r = rnd(l + 1, n);
ll sum = 0, mv = LLONG_MAX, cnt = 0;
int mi = INT_MAX;
for (int i = l; i < r; i++) {
sum += a[i];
if (a[i] < mv) { mv = a[i]; cnt = 1; mi = i; }
else if (a[i] == mv) cnt++;
}
if (it1.query(l, r) != sum) { printf("FAIL sum\n"); return 1; }
if (rc1.query(1, 0, n, l, r) != sum) { printf("FAIL rec sum\n"); return 1; }
if (it2.query(l, r) != make_pair(mv, mi)) { printf("FAIL minidx\n"); return 1; }
if (it3.query(l, r) != make_pair(mv, cnt)) { printf("FAIL mincnt\n"); return 1; }
ll bm = brute_maxsub(a, l, r);
if (it4.query(l, r).best != bm) { printf("FAIL maxsub\n"); return 1; }
if (rc4.query(1, 0, n, l, r).best != bm) { printf("FAIL rec maxsub\n"); return 1; }
// Descent: first p >= l where best sum of [l, p] reaches X.
ll X = rnd(-5, 12);
int want = n;
for (int e = l; e < n; e++) {
if (brute_maxsub(a, l, e + 1) >= X) { want = e; break; }
}
int got = it4.max_right(l, [&](const MaxSubM::T& x) { return x.best < X; });
if (got != want) { printf("FAIL descent\n"); return 1; }
}
}
printf("all stress tests passed\n");
return 0;
}
// Task: first line n and q. Second line the n values. Then q lines:
// 1 p v set a[p] = v (1-based p)
// 2 l r print the best non-empty contiguous sum inside a[l..r] (1-based, inclusive)
int n, q;
cin >> n >> q;
vector<ll> a(n);
for (auto& x : a) cin >> x;
vector<MaxSubM::T> leaves;
for (ll x : a) leaves.push_back(MaxSubM::leaf(x));
IterSeg<MaxSubM> seg(leaves);
while (q--) {
int type;
cin >> type;
if (type == 1) {
int p;
ll v;
cin >> p >> v;
seg.set(p - 1, MaxSubM::leaf(v));
} else {
int l, r;
cin >> l >> r;
cout << seg.query(l - 1, r).best << "\n";
}
}
return 0;
}Real output of ./seg demo:
sum[0,8)=9 sum[2,5)=2
after a[1]=10 sum[0,8)=22
min[0,8)=-3 first index=1
min and count over all: value=1 count=3
max subarray [0,8)=11, brute=11
max subarray [4,8)=8, brute=8
first p with best sum >= 9 starting at 0: 6Check a few lines by hand. The array sums to 4 - 3 + 5 - 2 - 1 + 2 + 6 - 2 = 9. Changing a[1] from -3 to 10 adds 13, so the total becomes 22. The minimum is -3 at index 1, which is the only -3. The counting example 3, 1, 4, 1, 5, 1, 2 has the value 1 three times.
For the max subarray of [0, 8), the best run is 4 - 3 + 5 - 2 - 1 + 2 + 6 = 11. For [4, 8) the values are -1, 2, 6, -2, and the best run is 2 + 6 = 8. For the descent, the best sum of a[0..p] first reaches 9 at p = 6, because a[0..6] contains the run 5 - 2 - 1 + 2 + 6 = 10, and no shorter prefix reaches 9.
Real output of ./seg stress, which runs 2000 random arrays of length 1 to 13, 60 random operations each, with the brute force on every query:
all stress tests passedThe stress test also checks the recursive trees and the descent. The descent check uses the brute force from the start of the range to every later position.
Monoids and what each merge does
Sum. The merge adds. The identity is 0, which is the only value that leaves a sum unchanged. This is the simplest case and the one an AI tool gets right most often.
Min with index. The merge takes the smaller pair. Comparing pairs compares the value first and the index second, so a tie keeps the smaller index. That gives the leftmost position of the minimum. The identity is a pair of large numbers, so any real value beats it. The demo returns (-3, 1), so the minimum is -3 and it first appears at index 1.
Min with count. Same idea as min with index, but the second field is a count. When two values are equal, the counts add. The identity has count 0, so an empty range adds nothing. This is the "counting equal values" monoid in the lesson plan. It answers "how many times does the smallest value occur in this range" in one query.
Max subarray. Each node holds four numbers for its segment: the total sum, the best prefix sum, the best suffix sum and the best subarray inside it. The merge combines them as follows. The total is the sum of the two totals. The best prefix is either the left best prefix, or the left total plus the right best prefix. The best suffix is either the right best suffix, or the right total plus the left best suffix. The best inside is the largest of the two children's best values, or the left best suffix plus the right best prefix, which is a subarray that crosses the middle.
The merge is not commutative. The crossing case uses the left suffix and the right prefix, and swapping the operands would give a different and wrong answer. That is why the query keeps left and right parts apart.
Descent: the first position where a monotone condition holds
Sometimes you need an index, not a value. Examples: the first position where the running sum reaches a target, or the first position where the best subarray starting at l reaches a target. Scanning one position at a time costs O(n) per query. A descent costs O(log n).
The condition must be monotone. That means that once the condition becomes true for a prefix of the range, it stays true for every longer prefix. A running sum of non-negative values is monotone. The best subarray sum of a prefix is also monotone, because a longer range can only keep or increase its best value. A running sum that can go down is not monotone, and the descent may stop at the wrong place.
The method max_right(l, pred) returns the largest r such that pred is still true on query(l, r). Turn a search for the first position into that form by negating the condition. Use max_right(l, not pred). The returned value r is then the first position where pred becomes true when the element at r is added.
Worked example from the demo. The condition is "best subarray sum of a[0..p] is at least 9". The call is max_right(0, x -> x.best < 9). The tree walks from the left, moving up when a whole node keeps the condition false, and moving down into a child when the node as a whole would make it true. It returns 6. Check: the best subarray of a[0..5] is 6, and of a[0..6] is 10.
The walk looks at O(log n) nodes. It does not need to look at each position. The stress test confirms the answer against a scan for 2000 random arrays.
Worked problem: best subarray sum with updates
A coffee shop logs how much profit it made on each day, as a number that can be negative. The owner asks two kinds of questions: change one day's value, and report the best run of consecutive days inside a range. A run must include at least one day.
Input: the first line has n and q, with n and q up to 200000. The second line has the n daily values, each between -10^9 and 10^9. Each of the next q lines is either 1 p v, which sets day p to v, or 2 l r, which asks for the best non-empty run inside days l to r, both inclusive and 1-based.
Sample input, saved as seg_in1.txt:
6 6
2 -4 3 5 -6 1
2 1 6
2 3 4
1 2 7
2 1 6
2 5 6
2 2 2Run it with ./seg < seg_in1.txt.
Real output:
8
8
17
1
7Hand check. Days 1 to 6 are 2, -4, 3, 5, -6, 1. The best run is days 3 and 4, with profit 3 + 5 = 8, so the first answer is 8. The query on days 3 and 4 gives 8 too. Then day 2 changes from -4 to 7. The array becomes 2, 7, 3, 5, -6, 1, and the best run over all six days is 2 + 7 + 3 + 5 = 17. Days 5 and 6 contain -6, 1, and the best single run is 1. Day 2 alone is 7.
The solution uses MaxSubM in the iterative tree. Each update is one set call, which recomputes the path to the root. Each query is one query call, which merges O(log n) nodes. The total time is O((n + q) log n). The memory is O(n) for the tree.
Why not a sum tree with a prefix maximum on each query? The best run can start and end anywhere inside the range, so a single prefix value does not answer it. The four-field node is what makes one tree enough.
Python version
This lesson does not include a Python version of the segment tree. The bottom-up tree is short in Python, but each query and update runs a Python loop of about 18 steps for n near 200000, and that is slow when there are 200000 operations. This lesson did not time a Python version, so it makes no claim about its speed. Use Python for a small check or a prototype, and write the final program in C++.
Timing on the lesson machine
These are single runs on the machine that wrote the lesson, and they include reading the input.
n = 200000andq = 200000with random updates and queries, mixed half and half: about 0.87 seconds, and the program printed 99760 answers.- The Fenwick tree lesson's inversion task on 200000 values: about 0.47 seconds.
Your times will differ with the machine, the compiler flags and the input format.
Complexity
| Operation | Iterative tree | Recursive tree |
|---|---|---|
| Build | O(n) | O(n) |
| Point update | O(log n) | O(log n) |
| Range query | O(log n) | O(log n) |
| Descent | O(log n) | not in this code |
| Memory | 2n nodes | 4n nodes |
The build of the iterative tree is O(n) because each internal node is merged once. The recursive tree allocates 4n nodes for a safe bound on the size, and the code does this at construction.
Hands-on exercise
Do this on your own machine. It takes about 30 minutes.
- Save the file from this lesson as
seg.cppand compile it withg++ -O2 -std=c++17 -Wall -Wextra -o seg seg.cpp. There should be no warnings. - Run
./seg demoand compare each line with the lesson. The output must match exactly. - Run
./seg stress. It should printall stress tests passed. - Make the sample input file from the worked problem and run it. You should get 8, 8, 17, 1 and 7.
- Add a monoid of your own: a max with count, which keeps the largest value and how many times it occurs. Write its
leaf,idandop. Test it with a loop that comparesIterSegagainst a scan, in the same style as the stress test. - Change the sample so that day 2 is set to -100 instead of 7. Predict the answer by hand before you run it.
Show the answer
Step 5 has no single answer. Check that your identity gives the right result on an empty range, and that ties keep the count. Step 6 changes the array to 2, -100, 3, 5, -6, 1. The five answers are 8, 8, 8, 1 and -100. The first query on days 1 to 6 gives 8, since the best run is still 3 + 5, and the query on days 2 to 2 gives -100.
Common mistakes
Identity 0 for max subarray. If the identity is {0, 0, 0, 0}, an empty segment looks like a candidate with best sum 0. An all-negative range then returns 0 instead of the largest negative value. A test folds the three leaves -3, -1 and -2 with the identity {0, 0, 0, 0} and prints:
buggy identity, all negative [-3,-1,-2]: best=0 (correct is -1)The fix is the identity used in this lesson, with minus infinity for the prefix, suffix and best fields.
Wrong operand order. A tree that merges each visited node into one accumulator in visit order is only right for commutative monoids. For max subarray, the crossing case needs the left suffix and the right prefix. A wrong order fails the comparison with the brute force, which is what the FAIL maxsub line in the stress test reports. Do not trust a non-commutative tree until it has passed that test.
Padded size in a descent. The tree is padded to a power of two. The descent can walk into the padding, which holds identity values, and then return a position past the real end. In an early version of this code, the stress test printed this line when the array length was not a power of two (the lesson did not keep the value it returned):
FAIL descentThe fix is to keep the real length in len and return it when nothing matches. The current max_right does that.
A predicate that is not monotone. The descent needs a condition that stays true once it becomes true. A condition like "the running sum equals 9" is not monotone, so the descent can skip past the right place and return a wrong position. Check monotonicity on paper before writing pred. The stress test compares the descent with a scan, so this kind of mistake shows up as a FAIL descent line.
Forgetting ancestors after an update. A point update must recompute every node on the path to the root. A version that recomputes only the leaf gives right answers for single values and wrong answers for ranges that cover the changed leaf.
Using int for sums. Sums of 200000 values near 10^9 need long long. The code uses ll throughout.
Checklist
- Write the identity first, and check that
op(id, x)andop(x, id)equalx. - Check that
opis associative on three values by hand, and that the operand order is left then right. - Keep the left and right parts apart in a bottom-up query when the monoid is not commutative.
- Store the real length, and do not return a padded position.
- Use a monotone condition for a descent, and negate it for
max_right. - Recompute every ancestor on a point update.
- Test each monoid against a brute force on random small arrays, with updates interleaved with queries, and print the seed.
Practice problems
These problems use your own machine. Write the code in C++17, test it against a brute force, and check the answer before you open the solution.
Practice 1: Leftmost maximum with ties
Given an array, answer queries [l, r) with the largest value in the range and the leftmost index where it occurs. Values can be equal. Updates are not needed.
Hint: a pair (value, index) with the right comparison does the job. The comparison must pick the larger value, and on a tie the smaller index.
Show the answer
Use the pair (-value, index) with min, or write a merge that compares the value first and then uses the smaller index on a tie. The identity is (+infinity, +infinity) in the first form, so the answer is (-result.first, result.second). Test it with the stress pattern from this lesson, with arrays that have many equal values.
Practice 2: Longest run of ones with updates
Given an array of 0s and 1s, support two operations: set a position to 0 or 1, and report the longest run of consecutive 1s inside a range [l, r). Write the node fields and the merge.
Hint: each node needs the length of its segment, the run of 1s at its left end, the run of 1s at its right end, and the best run inside it.
Show the answer
A node holds len, pref, suf and best. For a leaf with value 1, all four are 1. For a leaf with value 0, pref, suf and best are 0. The merge is: pref = a.pref == a.len ? a.len + b.pref : a.pref, suf = b.suf == b.len ? b.len + a.suf : b.suf, and best = max(a.best, b.best, a.suf + b.pref). The identity has len = 0 and all other fields 0, so pref == len holds and the merge with it changes nothing. Test it against a scan.
Practice 3: Trace the bottom-up query by hand
Take n = 8 and the iterative layout from this lesson. Work out, step by step, which nodes the query [1, 5) visits, and in which order they go to the left part and the right part.
Hint: write l = 1 + 8 = 9 and r = 5 + 8 = 13, then apply the two rules from the lesson at each level.
Show the answer
Start with l = 9, r = 13. Node 9 is leaf index 1, since leaf i sits at 8 + i. Since l is odd, node 9 goes to the left part and l becomes 10. Since r is odd, r becomes 12, and node 12 (leaf index 4) goes to the right part. Now l = 5 and r = 6. Since l is odd, node 5 (leaf indices 2 and 3) goes to the left part, after node 9, and l becomes 6. Now r = 6 is even. Then l = 3 and r = 3, and the loop stops. The left part is node 9, then node 5. The right part is node 12. The answer covers leaf indices 1 to 4, which is the half-open range [1, 5).
Practice 4: Descent on a sum tree
Write a function that returns the first index p where the prefix sum of a non-negative array reaches a target X, using the descent. Explain why the descent needs non-negative values.
Hint: use a sum tree and max_right with the negated condition sum < X. Check the answer against a loop.
Show the answer
With pred(x) = (x >= X) and the tree of sums, call max_right(0, [](ll s) { return s < X; }). The result is the first index where the prefix sum reaches X, or len if it never does. The descent needs non-negative values because only then does the prefix sum never decrease. A negative value could make the prefix sum drop back below X after the search passed it, and then the descent would return a point that is not the first.
Summary
A segment tree is a monoid over an array, built once and updated one leaf at a time. The identity, the operand order and the padded size decide whether it is right, and a brute-force test on random inputs is the way to find the mistakes that an AI tool makes most often. The descent gives the first position for a monotone condition in O(log n) steps.