The Log Squared Appears

Segment tree beats with chmin alone runs in O(mlog⁡n)O(m \log n) amortized. Add range add to the operation set. What happens to the bound?

A

It degrades to O(mlog⁡n⋅α(n))O(m \log n \cdot \alpha(n)). A range add pulls the second maximum back apart from the maximum at a rate bounded by the inverse Ackermann function.

B

It degrades to O(mlog⁡2n)O(m \log^2 n). A range add can pull the second maximum back apart from the maximum, re-creating potential that the amortized argument had already spent.

C

Nothing changes, it stays O(mlog⁡n)O(m \log n). A range add commutes with chmin, so the potential the amortized argument had already spent is never re-created.

D

It degrades to Θ(mn)\Theta(m\sqrt{n}). A range add destroys the potential argument entirely, leaving only the trivial bound that one operation touches at most nn leaves.