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.me/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)
