Search code examples
algorithmdynamic-programmingconvex-hull

Li Chao tree vs Convex hull trick. Which should be preferred and when?

I am having difficulty understanding the Convex hull trick. Li chao tree is way easier to understand. Is it important to understand the Convex hull trick too?

Solution

  • First of all, you should carefully look at what operations the two datastructures LiChao Tree (LC) and Convex Hull Trick (CHT) support. Both of them solve the same basic problem - we have a set of lines (linear functions) S and the operations:

    1. Add a line/linear function to the set
    2. For a given X coordinate, find the function with the maximal value at position X.

    Now, which one should you learn? I also find LC much easier to understand (and it is also shorter to implement). However, LC has a limitation that CHT does not - LC can answer queries of type 2. only for integer coordinates X, and at that, since it is very similar to a segment tree, we cannot support arbitrarily large intervals in which the X coordinate must lie. With CHT, you have no restrictions on the coordinates of the lines and the query values for X.

    In the context of competitive programming (I guess this is where the question is coming from) LiChao trees are sufficiennt in many problems, however CHT is more versatile and there can be some problems that cannot be solved with just LC.