the Li Chao tree
/ lee chow /
The convex-hull trick is fast but fussy: its simplest form demands that lines be inserted in sorted slope order and queries come in sorted x order. Real problems do not always cooperate. The Li Chao tree is a more flexible structure for the same job — keep a collection of lines and answer 'which line is lowest (or highest) at this x?' — that allows lines to be inserted in ANY order and queries at ANY x, each in O(log of the coordinate range), at the small cost of being a bit slower in the best case.
It is a segment tree built over the range of possible query x-values. Each tree node, covering an x-interval, stores a single line: the one that is the best (say, the minimum) at that node's midpoint among the lines seen so far. To insert a new line, you compare it with the node's stored line at the interval's midpoint; keep whichever is better there as the node's line, and push the loser down into the half-interval where it could still win — its sign relative to the kept line at the endpoints tells you which child to recurse into. Because two straight lines cross at most once, the loser can beat the winner in at most one of the two halves, so you only ever recurse into one child, giving O(log range) per insert. To query the minimum at a point x, you walk root-to-leaf along x and take the minimum of every stored line you pass, also O(log range).
So a Li Chao tree gives O(log C) insert and query, where C is the size of the coordinate range, with no ordering assumptions on slopes or queries — exactly what you reach for when the plain convex-hull trick's monotonicity preconditions fail. The trade-offs to be honest about: it needs the query coordinates to lie in a known, bounded range (you build the tree over that range, or compress coordinates first), it answers point queries rather than supporting easy deletions, and its constant factor and log-range depth make it slightly heavier than the amortized O(1) hull when the hull's assumptions do hold. The standard extension stores line segments (each valid only on a sub-range) instead of full lines, at an extra log factor.
Insert lines y = 2x + 1, y = -x + 6, y = 0.5x + 2 in any order, then query the minimum at x = 3. The tree compares lines at node midpoints and pushes losers toward the half where they could still win. At x = 3 the candidates give 7, 3, 3.5, so the query returns 3 — found by walking root to leaf and taking the min of stored lines, regardless of insertion order.
Two lines cross at most once, so a loser need be pushed into only one child — hence O(log range) per insert.
Use a Li Chao tree when slopes or queries are not monotone (where the plain convex-hull trick breaks); when they ARE monotone, the amortized-O(1) hull is lighter. It also needs a bounded, known coordinate range (compress first if needed).