_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://mirror.codeforces.com/blog/entry/86731 (code is in Prerequistes section)↵
↵
**Add** operation : Instead of ternary serach and range update, we will searchthe $x$ 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)
_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://mirror.codeforces.com/blog/entry/86731 (code is in Prerequistes section)↵
↵
**Add** operation : Instead of ternary serach and range update, we will search
$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)
