Challenge: 2D CHT

What if the linear term has two variables? $\min(a_j \cdot x_i + b_j \cdot y_i + c_j)$ for $2$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 $1$D (one-dimensional) with clever problem reformulation.