Hi Codeforces!
This is my first attempt at a tutorial blog XD.
Disclaimer: No headaches occured during the making of this blog
Problem statement
Given an integer array $$$A$$$ of length $$$n$$$ and $$$q$$$ of the following 5 types of queries:
- For all $$$i \in [l,r]$$$, change $$$A_i$$$ to $$$\max(A_i, v)$$$
- For all $$$i \in [l,r]$$$, change $$$A_i$$$ to $$$\min(A_i, v)$$$
- For all $$$i \in [l,r]$$$, change $$$A_i$$$ to $$$A_i + v$$$
- For all $$$i \in [l,r]$$$, change $$$A_i$$$ to $$$v$$$
- Output $$$A_i$$$
- $$$ 1 \leq n,q \leq 10^6 $$$
- $$$ 1 \leq l \leq r \leq n $$$
- $$$ -10^9 \leq A_i, v \leq 10^9 $$$
The above is solvable with techniques like Segment Tree Beats in $$$\mathcal{O}(n+q\log^2{n})$$$, but as a binary search enthusiast, you didn't learn segment tree beats?
Don't worry, here's an easier, faster, and shorter solution that solves this particular problem in $$$\mathcal{O}(n+q\log{n})$$$
Prerequisites
You should know the following to solve the full problem:
- Basics of functions (including composite functions)
- Associative, commutative, and distributive properties of $$$\max$$$ / $$$\min$$$
- Basics of a lazy propagation segment tree (not required for some subproblems)
Assuming you know the above, let's begin! But first, I'll relax the constraints a bit...
Subproblem 1
These are the queries:
- For all $$$i \in \textbf{[1,n]}$$$, change $$$A_i$$$ to $$$\max(A_i, v)$$$
- For all $$$i \in \textbf{[1,n]}$$$, change $$$A_i$$$ to $$$\min(A_i, v)$$$
Print the final array $$$A$$$ $$$\newline$$$
Example input 1Assuming input format is
$$$n \hspace{1mm} q$$$
$$$A_1 \hspace{1mm} A_2 \dots A_n$$$
$$$q$$$ lines follow
$$$T_i \hspace{1mm} v_i$$$ (where $$$T_i=1$$$ if $$$\max$$$ query, $$$T_i=2$$$ if $$$\min$$$ query)
INPUT
5 4
-1 2 15 4 -13
1 -5
2 10
1 3
2 8
OUTPUT
3 3 8 4 3
We'll use the example input to try coming up with a solution to this problem.
Let $$$f_i(x)$$$ = output after applying only $$$i$$$th query to integer $$$x$$$
Let's define a composite function $$$F(x)$$$ = $$$f_Q(f_{Q-1}(\dots f_2(f_1(x))\dots))$$$
We basically want to output $$$F(x)$$$ for all $$$x \in A$$$
We can try plotting the graph of $$$F(x)$$$ against $$$x$$$ to hopefully find a pattern.
Some observations about the above graph.
- $$$F(x)$$$ is monotonically non-decreasing i.e. $$$F(x) \leq F(x+1)$$$
And why is that?$$$ \max(x,v) \leq \max(x+1,v) \hspace{1mm} \text{for all } x, \hspace{1mm} v \\ \min(x,v) \leq \min(x+1,v) \hspace{1mm} \text{for all } x, \hspace{1mm} v \\ \text{Hence,} \hspace{1mm} F(x) \leq F(x+1) \hspace{1mm} \text{at any point in time} $$$ - The graph can be divided into 3 sections depending on $$$x$$$:
$$$ \displaystyle y = F(x) = \begin{cases} 3 &\quad\text{for } x \lt 3 \\ x &\quad\text{for } 3 \leq x \leq 8 \\ 8 &\quad\text{for } 8 \lt x \\ \end{cases} $$$In other words, $$$F(x) = \min(8,\max(x,3))$$$
In fact, it can be proven that $$$F(x) = \min(a,\max(x,b))$$$ for constants $$$a$$$, $$$b$$$ in the general case.
Mathy proofLet $$$f_{mx}(x,c) = \max(x,c) \implies f_{mx}(x,c) = \min(\infty,\max(x,c)) $$$
Let $$$f_{mn}(x,c) = \min(x,c) \implies f_{mn}(x,c) = \min(c,\max(x,-\infty)) $$$
$$$ \displaystyle
f_i(x) = \begin{cases} f_{mx}(x,v_i) &\quad\text{if } T_i = 1 \\ f_{mn}(x,v_i) &\quad\text{if } T_i = 2 \\ \end{cases}
$$$$$$\therefore f_i(x) = \min(a_i,\max(x,b_i))$$$ for some $$$a_i, b_i$$$
As $$$F(x)$$$ is just a composition of $$$f_i(x)$$$, we just need to prove that $$$f_j(f_i(x))$$$ can also be represented by $$$\min(a,\max(x,b))$$$ for some $$$a, b$$$
$$$\newline$$$
$$$ \displaystyle
f_j(f_i(x)) = f_j \left( \min(a_i,\max(x,b_i)) \right) \\
= \min( a_j,\max( \min(a_i,\max( x, b_i) ), b_j ) ) \\
= \min( a_j, \min( \max( b_j, a_i ) , \max( b_j, \max( x, b_i ) ) ) ) \\
= \min( a_j, \min( \max( b_j, a_i ) , \max( x, \max( b_i, b_j ) ) ) ) \\
= \min( \{ a_j, \max( b_j, a_i ) , \max( x, \max( b_i, b_j ) ) \} ) \\
= \min( \min( a_j, \max( b_j, a_i ) ) , \max( x, \max( b_i, b_j ) ) ) \\
= \min( a , \max( x, b ) ) \hspace{1mm} \text{where} \hspace{1mm} a = \min(a_j, \max( b_j, a_i ) ), \hspace{1mm} b = \max( b_i, b_j ) \hspace{1mm} \blacksquare $$$ Intuitive proofCredits to madlogic
Let's sort the array $$$A$$$. Notice that the max/min queries will not affect the order of the array.
So, let the minimum in $$$A$$$ be $$$\text{L}$$$, and the maximum be $$$\text{R}$$$:
The invariant $$$\text{L} \leq \text{R}$$$ always holds.
It is now easy to see that for each value $$$A_i$$$ in the array, its final value will be $$$\min(\text{R}, \max(\text{L}, A_i))$$$.
From the mathy proof, we can repeatedly spam $$$f_{i+1}(f_i(x))$$$ till we get $$$F(x)$$$.
Our starting $$$ f_0(x) = \min( \infty , \max( x, -\infty ) ) $$$ as this does not affect $$$x$$$
Now, that we have calculated our $$$F(x)$$$ in $$$\mathcal{O}(Q)$$$ , we can use it to calculate our final array in $$$\mathcal{O}(1)$$$ per $$$x$$$.
Subproblem 1 Code (Mathy version)#include <iostream>
using namespace std;
const int INF = (int) 1e9;
int x[1000010];
int A = INF, B = -INF;
int main() {
int n, q, a, b;
cin >> n >> q;
for (int i = 1; i <= n; i++)
cin >> x[i];
for (int i = 0; i < q; i++) {
int t, v;
cin >> t >> v;
if (t == 1)
a = INF, b = v;
else
a = v, b = -INF;
A = min(a, max(A, b));
B = max(B, b);
}
for (int i = 1; i <= n; i++)
cout << min(A, max(x[i], B)) << " ";
cout << "\n";
}
From the intuitive proof, we can create this solution:
Subproblem 1 Code (Intuitive version)#include <iostream>
using namespace std;
const int INF = (int) 1e9;
int A[1000010];
int L = -INF, R = INF;
int main() {
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++)
cin >> A[i];
for (int i = 0; i < q; i++) {
int t, v;
cin >> t >> v;
if (t == 1)
L = max(L, v), R = max(R, v);
else
L = min(L, v), R = min(R, v);
}
for (int i = 1; i <= n; i++)
cout << min(R, max(A[i], L)) << " ";
cout << "\n";
}
Bonus: Solve this subproblem using $$$\max(a,\min(x,b))$$$ instead.
Ok, that was easy enough. Let's make it a bit harder.
Subproblem 2
These are the queries:
- For all $$$i \in [l,r]$$$, change $$$A_i$$$ to $$$\max(A_i, v)$$$
- For all $$$i \in [l,r]$$$, change $$$A_i$$$ to $$$\min(A_i, v)$$$
- Output $$$A_i$$$ $$$\newline$$$
Example input 2Assuming input format is
$$$n \hspace{1mm} q$$$
$$$A_1 \hspace{1mm} A_2 \dots A_n$$$
$$$q$$$ lines follow
$$$T_i \hspace{1mm} l_i \hspace{1mm} r_i \hspace{1mm} v_i$$$ (where $$$T_i=1$$$ if $$$\max$$$ query, $$$T_i=2$$$ if $$$\min$$$ query)
$$$T_i \hspace{1mm} ind_i $$$ (where $$$T_i=3$$$)
INPUT
5 10
-1 2 15 4 -13
1 1 3 -5
3 1
1 1 5 10
3 2
1 2 4 3
3 3
2 1 4 8
3 4
2 3 4 2
3 5
OUTPUT
-1
10
15
8
10
In the first subproblem (mathy solution), we applied $$$f_i(x)$$$ to the entire array for each $$$i \in [1,q]$$$, but now we want to apply $$$f_i(x)$$$ only to $$$l_i, r_i$$$ for each $$$i \in [1,q]$$$. Doing this naively will take $$$\mathcal{O}(nq)$$$ time which is too slow.
We can speed this up with lazy segment trees instead. The idea is to only apply $$$f_i(x)$$$ to the $$$\mathcal{O}(\log n)$$$ segment tree nodes and lazily push down these functions from a segtree node to its children only when necessary (to make sure we apply the functions in the correct order).
Each node in the segment tree will contain the pair of integers $$$[a,b]$$$ which determines the function that is currently applied to that node (and eventually, all its decendants). Initially, each node's $$$[a,b]$$$ represents $$$f_0(x)$$$ and hence is equal to $$$[\infty,-\infty]$$$.
We apply to the $$$\mathcal{O}(\log n)$$$ nodes in the range $$$l_i, r_i$$$ for each query. Along the route to the target nodes, we push down the current node's $$$[a,b]$$$ to both children(if it's not $$$f_0(x)$$$) (to preserve order). $$$\newline$$$
Subproblem 2 Code#include <bits/stdc++.h>
using namespace std;
const int mxN = (int) 1e6 + 10;
const int INF = (int) 1e9;
int n, q, A[mxN];
array<int, 2> seg[mxN * 2], Init = {INF, -INF};
void apply(int p, int a, int b) {
seg[p][0] = min(a, max(seg[p][0], b));
seg[p][1] = max(seg[p][1], b);
}
void prop(int p, int l, int r) {
if (l == r or seg[p] == Init)
return;
int mid = (l + r) / 2;
int rp = p + 2 * (mid - l + 1);
auto [a, b] = seg[p]; // push down
apply(p + 1, a, b), apply(rp, a, b);
seg[p] = Init;
}
void upd(int i, int j, int a, int b, int p = 0, int l = 1, int r = n) {
if (i > j or i > r or j < l)
return;
if (i <= l and r <= j) {
apply(p, a, b);
return;
}
prop(p, l, r); // propagate to preserve order
int mid = (l + r) / 2;
int rp = p + 2 * (mid - l + 1);
upd(i, j, a, b, p + 1, l, mid);
upd(i, j, a, b, rp, mid + 1, r);
}
int query(int i, int p = 0, int l = 1, int r = n) {
if (l == r)
return min(seg[p][0], max(A[l], seg[p][1]));
prop(p, l, r); // propagate to preserve order
int mid = (l + r) / 2;
int rp = p + 2 * (mid - l + 1);
if (i <= mid)
return query(i, p + 1, l, mid);
return query(i, rp, mid + 1, r);
}
int main() {
cin >> n >> q;
for (int i = 1; i <= n; i++)
cin >> A[i];
fill(seg, seg + n * 2, Init);
for (int i = 1; i <= n; i++)
upd(i, i, INF, A[i]); // too lazy to build in O(N) :P
for (int i = 0; i < q; i++) {
int t, l, r, v, a, b;
cin >> t;
if (t == 1) {
cin >> l >> r >> v;
a = INF, b = v;
upd(l, r, a, b);
} else if (t == 2) {
cin >> l >> r >> v;
a = v, b = -INF;
upd(l, r, a, b);
} else {
int ind;
cin >> ind;
cout << query(ind) << "\n";
}
}
}
Bonus: Solve this subproblem using the intuitive solution instead.
Ok, now we're getting somewhere. It's still not hard enough though...
Subproblem 3
These are the queries:
- For all $$$i \in \textbf{[1,n]}$$$, change $$$A_i$$$ to $$$\max(A_i, v)$$$
- For all $$$i \in \textbf{[1,n]}$$$, change $$$A_i$$$ to $$$\min(A_i, v)$$$
- For all $$$i \in \textbf{[1,n]}$$$, change $$$A_i$$$ to $$$A_i + v$$$
Print the final array $$$A$$$ $$$\newline$$$
Example input 3Assuming input format is
$$$n \hspace{1mm} q$$$
$$$A_1 \hspace{1mm} A_2 \dots A_n$$$
$$$q$$$ lines follow
$$$T_i \hspace{1mm} v_i$$$ (where $$$T_i=1$$$ if $$$\max$$$ query, $$$T_i=2$$$ if $$$\min$$$ query, $$$T_i=3$$$ if $$$+$$$ query)
INPUT
5 7
-1 2 15 4 -13
1 -5
2 10
3 5
1 3
3 -4
2 8
3 3
OUTPUT
3 6 11 8 2
The example input3 is exactly the same as the example input1, but I added a couple of type 3 queries. We'll use example input3 to observe a pattern. On to plotting...
It seems both graphs have the same structure. Let's compare both of them.
Graph with type 3 queries vs Same graph without type 3 queriesThe Red graph is the one without type 3 queries. 
The new graph has the same 3-part structure as the old one, but with a horizontal translation by some $$$c$$$ for some new constants $$$a,b,c$$$
In other words:
$$$\displaystyle F(x) = \min(a,\max(b,x+c))$$$ for constants $$$a, b, c$$$ in the general case.
Proof is quite similar to the first subproblem.
Mathy proofLet $$$f_{mx}(x,v) = \max(x,v) \implies f_{mx}(x,v) = \min(\infty,\max(v,x+0)) $$$
Let $$$f_{mn}(x,v) = \min(x,v) \implies f_{mn}(x,v) = \min(v,\max(-\infty,x+0)) $$$
Let $$$f_{sum}(x,v) = x+v \implies f_{sum}(x,v) = \min(\infty,\max(-\infty,x+v)) $$$
$$$\therefore f_i(x) = \min(a_i,\max(b_i,x+c_i))$$$ for some $$$a_i, b_i,c_i$$$
Again, we just need to prove that $$$f_j(f_i(x))$$$ can also be represented by $$$\min(a,\max(b,x+c))$$$ for some $$$a, b, c$$$
$$$\newline$$$
$$$ \displaystyle
f_j(f_i(x)) = f_j \left( \min(a_i,\max(b_i,x+c_i)) \right) \\
= \min( a_j,\max( b_j, \min(a_i,\max(b_i,x+c_i)) + c_j ) ) \\
= \min( a_j,\max( b_j, \min(a_i+c_j,\max(b_i+c_j,x+c_i+c_j ) ) ) ) \\
= \min( a_j,\min(\max( b_j, a_i+c_j), \max( b_j, \max(b_i+c_j,x+c_i+c_j ) ) ) ) \\
= \min( \min(a_j, \max( b_j, a_i+c_j)), \max( b_j, \max(b_i+c_j,x+c_i+c_j ) ) ) \\
= \min( \min(a_j, \max( b_j, a_i+c_j)), \max(\max( b_j, b_i+c_j ) ,x+c_i+c_j ) ) \\
= \min( a , \max(b, x+c ) ) \hspace{1mm} \text{where} \hspace{1mm} a = \min(a_j, \max( b_j, a_i+c_j) ), \hspace{1mm} b = \max( b_j, b_i+c_j ), \hspace{1mm} c = c_i+c_j \hspace{1mm} \blacksquare $$$ Intuitive proofContinuing from subproblem 1 intuitive proof, introducing $$$\text{C}$$$ (initially 0) as the offset.
- For a query of type 3 with value $$$v$$$:
- $$$\text{L} = \text{L} + v$$$, $$$\text{R} = \text{R} + v$$$, $$$\text{C} = \text{C} + v$$$
For each value $$$A_i$$$ in the array, its final value will be $$$\min(\text{R}, \max(\text{L}, A_i+\text{C}))$$$.
Our starting $$$ f_0(x) = \min( \infty , \max(-\infty, x+0) ) $$$ as this does not affect $$$x$$$
Subproblem 3 Code (Mathy version)#include <iostream>
using namespace std;
using ll = long long; // overflow is possible!
const ll INF = (ll) 1e18;
ll x[1000010];
ll A = INF, B = -INF, C = 0;
int main() {
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++)
cin >> x[i];
for (int i = 0; i < q; i++) {
int t, v;
cin >> t >> v;
ll a, b, c;
if (t == 1)
a = INF, b = v, c = 0;
else if (t == 2)
a = v, b = -INF, c = 0;
else
a = INF, b = -INF, c = v;
A = min(a, max(b, A + c));
B = max(b, B + c);
C += c;
}
for (int i = 1; i <= n; i++)
cout << min(A, max(B, x[i] + C)) << " ";
cout << "\n";
}
From the intuitive proof, we can create this solution:
Subproblem 3 Code (Intuitive version)#include <iostream>
using namespace std;
using ll = long long; // overflow is possible!
const ll INF = (ll) 1e18;
ll A[1000010];
ll L = -INF, R = INF, C = 0;
int main() {
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++)
cin >> A[i];
for (int i = 0; i < q; i++) {
ll t, v;
cin >> t >> v;
if (t == 1)
L = max(L, v), R = max(R, v);
else if (t == 2)
L = min(L, v), R = min(R, v);
else
L += v, R += v, C += v;
}
for (int i = 1; i <= n; i++)
cout << min(R, max(A[i] + C, L)) << " ";
cout << "\n";
}
Bonus: We could also interpret the new graph as a vertical translation. Solve this subproblem using $$$\max(a,\min(x,b))+c$$$ instead.
Original problem
Armed with the ability to solve subproblems 1, 2, and 3, you should now be able to solve the original problem. Try solving it first : D
Full problem statementGiven an integer array $$$A$$$ of length $$$n$$$ and $$$q$$$ of the following 5 types of queries:
- For all $$$i \in [l,r]$$$, change $$$A_i$$$ to $$$\max(A_i, v)$$$
- For all $$$i \in [l,r]$$$, change $$$A_i$$$ to $$$\min(A_i, v)$$$
- For all $$$i \in [l,r]$$$, change $$$A_i$$$ to $$$A_i + v$$$
- For all $$$i \in [l,r]$$$, change $$$A_i$$$ to $$$v$$$
- Output $$$A_i$$$
- $$$ 1 \leq n,q \leq 10^6 $$$
- $$$ 1 \leq l \leq r \leq n $$$
- $$$ -10^9 \leq A_i, v \leq 10^9 $$$ $$$\newline$$$
Example InputAssuming input format is
$$$n \hspace{1mm} q$$$
$$$A_1 \hspace{1mm} A_2 \dots A_n$$$
$$$q$$$ lines follow
$$$T_i \hspace{1mm} l_i \hspace{1mm} r_i \hspace{1mm} v_i$$$ (where $$$T_i=1,2,3,4$$$)
$$$T_i \hspace{1mm} ind_i $$$ (where $$$T_i=5$$$)
INPUT
5 20
-1 2 15 4 -13
1 1 3 -5
5 1
3 1 2 6
1 1 5 10
4 4 5 69
5 2
1 2 4 3
3 2 4 6
5 3
2 1 4 8
4 4 4 20
5 4
3 1 3 5
2 3 4 2
1 1 2 6
5 1
5 2
5 3
5 4
5 5
OUTPUT
-1
10
21
20
13
13
2
2
69
How to solve? It's just subproblem 2+3 with an extra step
Handle range queries?Just like subtask 2, it's a standard application of lazy segtrees...
Handle Type 4 queries?These are not difficult.
You can replace them with a type 1 and type 2 query:
- For all $$$i \in [l,r]$$$, change $$$A_i$$$ to $$$\max(A_i, v)$$$
- For all $$$i \in [l,r]$$$, change $$$A_i$$$ to $$$\min(A_i, v)$$$
Final Code#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mxN = (int) 1e6 + 10;
const ll INF = (ll) 1e18;
int n, q;
ll A[mxN];
array<ll, 3> seg[mxN * 2], Init = {INF, -INF, 0ll};
void apply(int p, ll a, ll b, ll c) {
seg[p][0] = min(a, max(seg[p][0] + c, b));
seg[p][1] = max(seg[p][1] + c, b);
seg[p][2] += c;
}
void prop(int p, int l, int r) {
if (l == r or seg[p] == Init)
return;
int mid = (l + r) / 2;
int rp = p + 2 * (mid - l + 1);
auto [a, b, c] = seg[p]; // push down
apply(p + 1, a, b, c), apply(rp, a, b, c);
seg[p] = Init;
}
void upd(int i, int j, ll a, ll b, ll c, int p = 0, int l = 1, int r = n) {
if (i > j or i > r or j < l)
return;
if (i <= l and r <= j) {
apply(p, a, b, c);
return;
}
prop(p, l, r); // propagate to preserve order
int mid = (l + r) / 2;
int rp = p + 2 * (mid - l + 1);
upd(i, j, a, b, c, p + 1, l, mid);
upd(i, j, a, b, c, rp, mid + 1, r);
}
ll query(int i, int p = 0, int l = 1, int r = n) {
if (l == r)
return min(seg[p][0], max(A[l] + seg[p][2], seg[p][1]));
prop(p, l, r); // propagate to preserve order
int mid = (l + r) / 2;
int rp = p + 2 * (mid - l + 1);
if (i <= mid)
return query(i, p + 1, l, mid);
return query(i, rp, mid + 1, r);
}
int main() {
cin >> n >> q;
for (int i = 1; i <= n; i++)
cin >> A[i];
fill(seg, seg + n * 2, Init);
for (int i = 1; i <= n; i++)
upd(i, i, INF, A[i], 0); // too lazy to build in O(N) :P
for (int i = 0; i < q; i++) {
ll t, l, r, v, a, b, c;
cin >> t;
if (t == 1) {
cin >> l >> r >> v;
a = INF, b = v, c = 0;
upd(l, r, a, b, c);
} else if (t == 2) {
cin >> l >> r >> v;
a = v, b = -INF, c = 0;
upd(l, r, a, b, c);
} else if (t == 3) {
cin >> l >> r >> v;
a = INF, b = -INF, c = v;
upd(l, r, a, b, c);
} else if (t == 4) {
cin >> l >> r >> v;
a = INF, b = v, c = 0;
upd(l, r, a, b, c);
a = v, b = -INF, c = 0;
upd(l, r, a, b, c);
} else {
int ind;
cin >> ind;
cout << query(ind) << "\n";
}
}
}
Bonus: Solve this problem using the intuitive solution instead.
Final time complexity: $$$\mathcal{O}(n+q\log{n})$$$
Practice problems
I'll update this list if you find any more problems
- IOI 2014 Wall
- ABC 196 E Filters
- IOI 2021 Candies (Subtask 3)
Conclusion
Thanks to madlogic for proofreading this blog and useful suggestions!
If you found this trick useful, you might as well upvote :)
In the case of any bugs or questions, feel free to let me know.
DAN4LIFE ORZ!!!!
MR.WHITEBIRD ORZ!!!!
Can you show the details for "Handle range queries?". As far as I can see it won't work and saying that this can replace seg tree beats for this type of problem is a sort of a big claim imo.
Didn't say it works for range queries, just pointed out that segtree beats can solve harder variations and is overkill in this case
Yes, lazy propagation can do many types of range-range operations — as long as you can combine updates into $$$O(1)$$$ info in a node.
But please remove the segment tree beats from the title. You're wasting time of people who think that you're proposing its easier replacement. It doesn't help that the following sentence doesn't clearly say if you can do the sum:
Sure. I've made the blog less confusing.
The idea is not related to chmin, cmax, add, and assign per se. It's just a general idea: if there is some constant $$$k$$$ such that any sequence of $$$k+1$$$ updates to a sequence of numbers can be shrunk to a sequence of $$$k$$$ updates, we can use lazy segment trees to store these updates. Then, if we only care about point queries, we can already answer them. However, if we want to answer queries of calculating some function $$$F$$$ on a segment, we also need to be able to quickly (ideally, in constant time) recalculate the value of $$$F$$$ on a segment after the application of a single update to all the elements of this segment. Hence, for example, if our query is "sum all the elements on a segment", segment trees are good to go with updates like add and assign and fail with updates like chmin and chmax. On the other hands, if our query is "find minimum on a segment", there is no trouble to add chmin and chmax updates.