Implementation Template

Class with: maxHeap $L$ (left breakpoints), minHeap $R$ (right breakpoints), base value, optional offsets. Method addAbsValue(a): push $a$ to both heaps, balance if $L.top > R.top$, update base. Method prefixMin(): clear right heap, base stays. Method query(): base value is the minimum, $L.top$ and $R.top$ give the interval of minimizers. Use a max-heap for left breakpoints and min-heap for right. The heaps maintain the piecewise linear function.

Time complexity: $O(n \log n)$ since each of the $n$ operations involves heap pushes and pops.

Space complexity: $O(n)$ for the two heaps storing breakpoints.