Coding Interview: How would you use a Li Chao tree for dynamic line minimum queries?

Problem and Context

An online service receives lines y = m x + b in arbitrary insertion order and must return the minimum value at an integer query point x. Query points are also arbitrary. An extension may restrict a line to an interval [l, r] or ask for maximum values instead.

This problem tests dynamic-programming optimization, divide-and-conquer invariants, and segment-tree implementation. A strong answer first states whether the query domain is discrete and bounded, then explains why each node can retain one line that wins somewhere while any remaining candidate is sent to exactly one child.

What the Interviewer Evaluates

• Deriving the bottleneck of scanning every line in O(numberoflines) per query.
• Understanding the midpoint comparison, swap, and recursion invariant.
• Handling arbitrary slopes, duplicate lines, negative coordinates, and overflow.
• Distinguishing discrete integer domains, continuous domains, and segment-restricted lines.
• Giving O(log C) insertion/query and O(log^2 C) segment insertion bounds.
• Explaining when monotone slopes and monotone queries make a standard convex hull trick simpler.

Clarifications to Ask First

1. Are query points integers or reals? Is the domain fixed [L, R] or dynamically expanded? This determines depth and coordinate compression.
2. Is the operation a minimum or maximum? Is an empty set allowed, and what sentinel cannot collide with a real answer?
3. What are the maximum magnitudes of slopes, intercepts, and answers? Is a wider integer or checked multiplication required?
4. Does a line apply only on [l, r]? Interval insertion distributes a line to several tree nodes.
5. Are insertion slopes or query points monotone? If so, a deque-based convex hull trick may use smaller constants.

30-Second Answer Framework

I build a segment-tree domain [L, R] and store one candidate line at each node. When inserting a new line, I compare it with the node line at the endpoints and midpoint. If the new line wins at the midpoint, I swap it into the node. The displaced line can still win on only the left or right half, so I recurse into one child. A point query evaluates every line on its root-to-leaf path and takes the minimum. With domain length C, insertion and query are O(log C); restricting a line to an interval costs O(log^2 C). Maximum queries reverse the comparator.

Step-by-Step Deep Dive

1. Brute Force and the Bottleneck

Keep a list of lines and evaluate every m x + b for each query. This costs O(numberoflines) per query. In a dynamic-programming transition, insertions and queries interleave, so neither slopes nor query points can be sorted without changing the problem. The data structure must distribute comparisons over the value domain.

2. The Node Invariant

A node represents a closed interval [lo, hi] and stores a line cur. Among lines not already pushed into children, cur is no worse at at least one candidate position in this interval. Any other line that may still become optimal can do so only in the left or right child. At a leaf, the node only needs the line that is best at one point.

3. Midpoint Swap and Recursion Direction

Let nw be the new line, cur the node line, and mid the midpoint. If the new line's value at mid is smaller, swap them so the node keeps the midpoint winner. After the swap, compare which line wins at lo. If the displaced line wins on the left endpoint, it may reappear only in the left half; otherwise compare the right endpoint and recurse right. The difference of two lines is linear, so their order changes at most once.

add(node, lo, hi, nw):
  mid = (lo + hi) // 2
  left = nw(lo) < cur(lo)
  middle = nw(mid) < cur(mid)
  if middle: swap(nw, cur)
  if lo == hi: return
  if left != middle: add(leftChild, lo, mid, nw)
  else: add(rightChild, mid + 1, hi, nw)

Use a safe midpoint formula. If m * x + b can exceed 64-bit range, use a wider type, checked arithmetic, or an explicit saturation policy.

4. Query the Root-to-Leaf Path

For point x, recurse toward the leaf containing x, evaluate the stored line at x at every visited node, and return the minimum. Other subtrees do not contain the point. An implicit tree allocates nodes only on paths touched by insertions; an empty node returns a positive-infinity sentinel.

5. Insert a Line Restricted to an Interval

If a line is valid only on [ql, qr], decompose that interval with a standard segment tree. Insert the line once into every fully covered node and recurse for partial coverage. The decomposition touches O(log C) nodes and each Li Chao insertion costs O(log C), giving O(log^2 C); point query remains O(log C).

6. Discrete Coordinates and Continuous Queries

If queries come from a known finite set, sort and deduplicate the x-values and use their indices as leaves. This avoids building a huge empty domain. For real-valued queries, state precision and stopping conditions explicitly. The integer-domain proof does not automatically apply to an unbounded continuous domain; bound the interval and define floating-point comparison tolerance.

7. Trade-offs and Tests

When slopes and query points are both monotone, a deque-based convex hull trick has smaller constants. Li Chao is more robust for arbitrary order, at the cost of more nodes and recursion. Test an empty set, a one-point domain, duplicate slopes, identical lines, negative coordinates, an intersection at the midpoint, a line covering one endpoint, large products, and maximum queries; compare every result with brute-force evaluation.

High-Quality Model Answer

I would first confirm whether the query domain is a bounded integer interval or needs coordinate compression. For [L, R], I build a Li Chao tree whose nodes store candidate lines. Insertion compares endpoints and midpoint; the midpoint winner stays at the node, and the other line recurses into the one half where the two lines can change order. Their difference is linear, so the displaced line cannot become better in two separated directions. A point query takes the minimum along one root-to-leaf path, giving O(log C) insertion and query. If slopes and queries are monotone, I would use a convex hull trick; interval-restricted lines require segment decomposition and O(log^2 C) insertion.

Common Mistakes

• Comparing only the midpoint and stopping → the other line may win at an endpoint → use endpoint and midpoint comparisons to choose one child.
• Assuming slopes must be monotone → arbitrary insertion produces wrong answers → use Li Chao's interval invariant or state the convex-hull precondition.
• Computing m * x + b in unchecked 64-bit arithmetic → overflow changes comparisons → use wider or checked arithmetic.
• Allowing an unbounded dynamic domain → recursion has no termination → bound the integer domain, compress coordinates, or define floating-point precision.
• Copying an interval line to every leaf → complexity degenerates → decompose the interval and insert at fully covered nodes.
• Returning zero for an empty node → a minimum is incorrectly lowered → use a positive-infinity sentinel outside the answer range.

Follow-ups and Responses

What changes for maximum queries?

Reverse every comparison, or negate both m and b, solve a minimum query, and negate the result. Empty-set and overflow semantics must be reversed consistently rather than changing only the final return value.

Can an array-based tree handle a domain of 10 to the 18?

Not by preallocating every node. Use an implicit tree that creates nodes only along insertion paths; depth is roughly the number of domain bits. If query coordinates are finite, coordinate compression usually saves more memory.

Two lines tie at the midpoint. How do you avoid a bad branch?

Choose a deterministic tie rule, such as keeping the old line or preferring a slope order. Use strict inequalities consistently at endpoints and midpoint so identical lines do not recurse forever.

Why is one recursive side enough?

The difference of two lines is linear and has at most one zero. After the midpoint winner is kept, the displaced line can recover only toward an endpoint where the ordering differs, uniquely selecting the left or right child.

When is a convex hull trick better?

If lines arrive in monotone slope order and queries are monotone, a hull deque can provide amortized O(1) queries or O(log n) binary-search queries with less memory. Arbitrary order, or segment-restricted lines, favors Li Chao's generality.