*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 ? :

### 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)