# Convex hull trick This blog is the first blog in a series of blogs about line containers. Links: - 1: Data structure: add line, query max (this blog) - 2: [Slope trick](https://hackmd.io/K7t3ly9USMWT8BFLr-GjlQ) - 3: [Convex hulls](https://hackmd.io/DpZ_bPNWSd6nwov6Ym1n2w) ## The data structure The problem that convex hull trick solves is the following: you have set of lines that starts empty. You have to handle the following queries: - Add a line $y=kx+m$ - Which line has highest y-value at a given x-coordinate? This blog does a good job of explaining this technique can be used to optimize DPs: https://codeforces.com/blog/entry/63823 So what should your takeaway be? - If you're inserting lines in sorted order (either ascending or descending), you should use a deque of lines. It's easy if queries are sorted, otherwise binary search for the optimal line. - If lines are inserted in arbitrary order, use Li Chao tree. If coordinates are small, it can be built explicitly. If coordinates are big, use a sparse Li Chao tree. This is the fastest and easiest, as can be seen from looking at the top solutions here: https://judge.yosupo.jp/problem/line_add_get_min. This solution looks nice https://judge.yosupo.jp/submission/258299. In addition, Li Chao trees are very extandable: you can make it persistent and remove lines offline with an extra log factor by doing offline deletion https://cp-algorithms.com/data_structures/deleting_in_log_n.html.