What if the linear term has two variables? for D (two-dimensional) queries. This becomes a 2D lower envelope: a convex polyhedron.
Much harder to maintain dynamically. Practical approach: if one dimension is small, enumerate it. Or use divide and conquer over one variable. Full 2D CHT is rarely needed in contests. Most problems can be reduced to D (one-dimensional) with clever problem reformulation.