A simpler way to understand Li-Chao tree

Revision en1, by ngk_manh, 2021-10-01 11:04:28

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English ngk_manh 2021-10-01 14:49:15 13 Tiny change: 'll search the $x$ coordinate' -> 'll search point with x-coordinate'
en3 English ngk_manh 2021-10-01 12:57:33 1931 Tiny change: 'ind point x such that' -> 'ind point $x$ such that' (published)
en2 English ngk_manh 2021-10-01 12:03:50 800 Tiny change: 'ive slope.\n-If a li' -> 'ive slope.&\break$\n-If a li'
en1 English ngk_manh 2021-10-01 11:04:28 1712 Initial revision (saved to drafts)