Think of LiChao as a replacement of CHT. Now consider how you would answer queries of this type if you used CHT instead. Well that actually isn't so hard.

The lower hull is clearly convex, hence we can notice that the answer to some query defined by [L, R], will be the maximum of:

• query(L)

• query(R)

Well now consider using LiChao tree. You can use the exact same queries and then your queries can be solved in 2 normal LiChao queries.

PS: This is correct because of convexity applied for L and R.

Convexity states that for any $$$\alpha \in [0, 1]$$$ and any two $$$x_1, x_2$$$, we have:

$$$\alpha * f(x_1) + (1 - \alpha) * f(x_2) \geq f(\alpha * x_1 + (1 - \alpha) * x_2)$$$

Therefore, if we apply it for L, R and f(x) = query(x), we can see that for every $$$x \in [L, R]$$$, $$$f(x) \leq \max(f(L), f(R))$$$.