Segment Tree Beats

Range chmin (ai = min(ai, x)) with range sum / max. Each node shows max1 / max2 / cnt. The three-way rule: break when x ≥ max1, tag (O(1)) when max2 < x < max1, recurse when x ≤ max2.

Build: O(n) Query: O(log n) chmin: amortized O(log² n) Node: sum,max1,max2,cnt
chmin: l r x query:
SlowFast Animate steps:
Idle
Break (x ≥ max1, no-op)
Tag (max2 < x < max1, O(1))
Recurse (x ≤ max2)
Changed
n
0
Last op
-
Nodes visited
0
Tag applies
0
Recursions
0
Result
-

Trace

Load an array, then apply a chmin. Watch where it breaks, tags, or recurses.

Complexity

OperationCostNote
BuildO(n)same as any segment tree
Range max / sum queryO(log n)plain query on max1 / sum
chmin (chmin + max)amortized O(log n)per-op unbounded; total O((n+q)log n)
chmin (chmin + sum)amortized O(log² n)sum maintenance adds a log
SpaceO(n)4n nodes, 4 fields each

A plain lazy segment tree cannot do chmin because a single tag cannot capture "lower the big ones, leave the small ones". Storing max1/max2/cnt makes the tag case O(1): exactly cnt elements equal to max1 drop to x, so sum -= cnt*(max1-x).