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 you 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 me (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 middle point 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 data structure which can do two following operation by the best way you can :

• Add a line $$$y = a*x + b$$$ into set $$$S$$$

• Given an integer point $$$x$$$, find $$$min$$$ value of $$$y$$$ among all line we added

Similar to $$$Li-Chao$$$ $$$tree$$$, we manage convex hull by the way maintain a segment $$$[L, R]$$$, for each intergers $$$x$$$ in $$$[L, R]$$$ we store line $$$y = a*x + b$$$ such that the line $$$y = a*x + b$$$ reach min at point with coordinate $$$x$$$ among all of line.

Add operation :

We can reach two observation :

• Add two line $$$x = -\infty$$$ and $$$x = +\infty$$$ 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. $$$(**)$$$

Thicker line represent the convex hull

We can iterate over $$$[L, R]$$$ whenever we add a new line into $$$S$$$ to update the "min line" for each point in $$$[L, R]$$$

However, by two observation above, we can do ternary search to find point $$$x$$$ such that:

• $$$x$$$ $$$\in$$$ $$$[L, R]$$$

• At $$$x$$$ coordinate, the current line $$$y = a*x + b$$$ is the "min line".

Because $$$(**)$$$ then we also need a segment tree to range update (lazy propagation is recommend). Add operation is done!

Query operation : We only need get result on segment tree by go to leaf which represent point $$$x$$$. So easy, right?

III.Basic Li-Chao tree

I will explain following code in this blog : https://codeforces.com/blog/entry/86731 (code is in Prerequistes section)

Add operation : Instead of ternary serach and range update, we will search point with x-coordinate which at $$$x$$$, line $$$y = a*x + b$$$ lie on convexhull, we can "walk on segment tree" to find such $$$x$$$.

Back to the first question in I section. By storing in such way, we can get some observation :

• If a line lie on a contiguous interval on convex hull, it will be stored in some node on $$$Li-Chao$$$ $$$tree$$$. $$$(***)$$$

• If a line $$$y = a*x + b$$$ reach min in range $$$[L, R]$$$ among all line we added, then any path from root to every leaf $$$x$$$ $$$\in$$$ $$$[L, R]$$$ on $$$Li-Chao$$$ $$$tree$$$ $$$(****)$$$ will pass over at least one times the line $$$y = a*x + b$$$.

Query operation : by $$$(****)$$$, we get min value of $$$y = a*x + b$$$ on path from root to leaf, we will get the min result we want. Which answer the second question in I section. All done!

IV.Epilogue

That's all thing I can think about $$$Li-Chao$$$ $$$tree$$$, so this is my first time to write something i have learn on codeforces, hope that my blog will not get nagative rate. Thanks for reading! (And sorry because my English)