There are to simple ways to do this.

The first one is using LiChao segment tree.

The second one is doing dynamic convex hull trick.

The basic idea is to save the lines in a set, sorted by their slope (k_i). When we add a line we insert it in the set and find its position (iterator) and we check if it's irrelevant (there is no point in which this line has maximum y). If this is the case (the line is irrelevant) we erase it from the set. For this checking it's enough to look only at the two adjecent lines in the set of the line we are adding.

Now we arr sure that the line will stay in the set. Well now we will just remove all lines to the left and right of the one we are adding which are irrelevant. Note that the lines (if there are) will be groups of consecutive lines to the left and right of the one we are adding.

The complexity of adding the lines will be as we are adding and removing each line at most once.

The query is also done in a simple way. For every line we will also store it's intersection (x coordinate) with the next one in the set. Note that when we add and remove lines we should change intersections. Now the query can be done by simply doing binary search on the lines and finding the line which corresponds for the query x coordinate. Then we just take the value of this line for the query x coordinate.

The complexity will be per query.

You can look at my implementation. It's in my coding library in "other/dp_optimizations". You can find a link to the coding library in my latest blog.

I'm quite sure that solution with sqrt-decomposition on queries works as fast as solution with sets

Read this blog.