Convex Hull Trick — Building the Lower Envelope of Lines

A DP transition dp[i] = minj(mj·x + bj) is a query against the lower envelope. Watch the deque add lines, pop the now-useless "bad middle" lines, and answer a query at x.

step 0

Lines & lower envelope

Reading the envelope at x = q gives the minimum line value.
envelope (kept) popped / useless incoming line query x

Deque of lines (slope order)

Press Step to begin. We insert lines one at a time in decreasing-slope order, popping any middle line the bad-line test says is useless, then query the envelope at x.
Self-contained visualization. Lower envelope = min over lines (MIN queries). The division-free bad-line test pops middle line L2 when (b3-b1)*(m1-m2) ≤ (b2-b1)*(m1-m3). See junior.md and professional.md for the correctness proof.