Hi codeforces! I was trying to learn about Li-Chao tree by some blog which i can find on gg (codeforces included). But there still some issue i was encountered while I trying to understood Li-Chao tree. Fortunately! I found that there's a simpler way to understand LC tree by thinking about another approach. So, I decide to write this blog for two reason : -Archive -Sharing If u feel interesting about this topic, welcome!

Prerequisite : -Did you read one of two blog ? : https://robert1003.github.io/2020/02/06/li-chao-segment-tree.html https://cp-algorithms.com/geometry/convex_hull_trick.html

I.Which issue that I (or maybe someone) stuck in Li-Chao tree? These question are main motivation : - Why node on Li-Chao tree only store one line that is min/max at point mid which mid is the point middle in segment [L, R] which current node manage? - Why in Query function we get max result on way from root to leaf instead of get a value in node which include point we want to query?

I guess that somebody maybe stuck in here, so, we will answer it later.

II.Problemstatement

You must give a date structure which can do two folowing operation by the best way you can : -Add a line y = a*x + b into set S -Given a point x, find min value of y among all line we added

Add operation : We can see that we will only care about convex hull of S, so that we will maintain it : We can reach two observation : -Add two line x = -oo and x = +oo into S. Easy to see that the convex hull look like a parabol with nagative slope. -If a line lie on convex hull, it will lie on a continuous interval on convex hull.