Watch f(x) (a convex piecewise-linear valley) mutate as we relax (prefix-min) and add |x − a| penalties. The left max-heap and right min-heap hold the breakpoints; their tops bound the flat minimum.
a_i triggers a relax (clear R) then add |x − a_i|.| Operation | Cost |
|---|---|
| add |x − a| | O(log n) |
| one-sided ramp | O(log n) |
| prefix-min (clear) | O(1) amortized |
| shift (lazy) | O(1) |
| read minVal / floor | O(1) |
| whole DP (n steps) | O(n log n) |
| memory | O(n) (range-independent) |