ngk_manh's blog

By ngk_manh, history, 3 years ago, In English

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://mirror.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)

  • Vote: I like it
  • +87
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Auto comment: topic has been updated by ngk_manh (previous revision, new revision, compare).

»
3 years ago, # |
  Vote: I like it -139 Vote: I do not like it

green colored loser, go solve some problems and become blue at least, to write blogs about li-chao tree. Anyone can see tutorials online and write what notations and definitions lead to, that doesn't mean shiiiiiiit.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +69 Vote: I do not like it

    I wouldn't say I know him personally, but I've talked to him many times and he knows his stuff. If anything, he's a pretty strong contestant (to me at least) at our national OI, and CF rating isn't really relevant there.

    Writing comments with an alt, no shit you are indeed a loser.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -104 Vote: I do not like it

      Lmaoo sure, he's sooo good, that you have to suck him up to prove that. and as for loser, go become candidate master, or master, or grandmaster...orr....you get the pattern now, right? In fact, try making your account lgm in your lifetime, if you wanna own the "I HAVE MY REAL ACCOUNT" shit, bet you just can't, even for the sake of your existence xD

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +87 Vote: I do not like it

        Well, at least people don't need to reach LGM to see that you are a clown.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it -93 Vote: I do not like it

          indeed I am a clown, which is why you're having to tell me I am one ;) go practice, sub-2000 loser. and if you're happy being low, allow me to go practice. Oh! And throwing adjectives on me can't do shit on me;)

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it +32 Vote: I do not like it

            you're a loser

            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it -28 Vote: I do not like it

              shh sub 2000 peasant lmao

              • »
                »
                »
                »
                »
                »
                »
                »
                3 years ago, # ^ |
                  Vote: I like it +30 Vote: I do not like it

                "go become candidate master, or master, or grandmaster...orr....you get the pattern now, right?" were your words two comments above

              • »
                »
                »
                »
                »
                »
                »
                »
                3 years ago, # ^ |
                Rev. 2   Vote: I like it +54 Vote: I do not like it

                Above 2000 here, anything to say, loser?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +64 Vote: I do not like it

    that's so hurt, guy. I just want to archive and share...

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You seem like someone who would tell Darooha to become Expert before writing comments about link-cut tree.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    CF rating is not equal to a person's real strength.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Lmao every LG started out as a pupil once so what exactly is your point?

»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Auto comment: topic has been updated by ngk_manh (previous revision, new revision, compare).