Li Chao Tree

Problem Overview

Learning Goals

After studying this topic, you will be able to:

• Understand how Li Chao Tree maintains a set of lines efficiently
• Implement insertion and query operations in O(log N)
• Apply Li Chao Tree for DP optimization problems
• Choose between Li Chao Tree and Convex Hull Trick appropriately

Concept Explanation

Problem: Given a set of lines of the form y = mx + b, efficiently:

1. Insert a new line into the set
2. Query the minimum (or maximum) y-value at a given x-coordinate

Key Insight: Li Chao Tree is a segment tree where each node stores the “winner” line for its interval’s midpoint. When inserting a new line, we compare it with the existing line at the midpoint and recursively push the “loser” to the appropriate child.

Why Li Chao Tree?

• Arbitrary Query Order: Unlike standard CHT, queries can come in any order
• Simple Implementation: Easier to code than dynamic CHT with binary search
• Persistent Friendly: Can be made persistent for advanced applications

Intuition: Li Chao Tree vs Convex Hull Trick

Pattern Recognition

Key Question: When do we use Li Chao Tree instead of Convex Hull Trick?

The Convex Hull Trick (CHT) requires either:

1. Lines inserted in order of increasing/decreasing slope, OR
2. Queries in sorted order of x-coordinate

Li Chao Tree removes these restrictions at the cost of slightly higher constant factor.

Comparison Table

Breaking Down the Problem

1. What are we storing? Lines in the form y = mx + b
2. What’s the query? Find min/max y at a specific x
3. Why segment tree? Each node represents an x-interval; we store the “best” line for that interval’s midpoint

Algorithm: How Li Chao Tree Works

Core Idea

Each segment tree node covering interval [lo, hi]:

• Stores the line that is best at the midpoint mid = (lo + hi) / 2
• When inserting a new line, compare at midpoint:
  • Winner stays at current node
  • Loser is pushed to the child where it might still win

Insert Operation

insert(node, [lo, hi], new_line):
    mid = (lo + hi) / 2

    if new_line is better at mid than current line:
        swap(new_line, current_line)

    if lo == hi:
        return

    if new_line is better at lo:
        insert(left_child, [lo, mid], new_line)
    else:
        insert(right_child, [mid+1, hi], new_line)

Query Operation

query(node, [lo, hi], x):
    if node is null:
        return infinity (or -infinity for max)

    mid = (lo + hi) / 2
    current_value = evaluate(node.line, x)

    if x <= mid:
        return min(current_value, query(left_child, [lo, mid], x))
    else:
        return min(current_value, query(right_child, [mid+1, hi], x))

Dry Run: Inserting Lines

Let’s trace inserting lines into a Li Chao Tree for minimum queries with x-range [0, 8].

Lines to Insert

1. Line A: y = 2x + 1
2. Line B: y = -x + 10
3. Line C: y = 0.5x + 4

Step-by-Step Execution

Initial State: Empty tree, range [0, 8]

=== Insert Line A: y = 2x + 1 ===
Node [0,8], mid=4:
  - No existing line, store A
  Tree: [0,8] -> A

=== Insert Line B: y = -x + 10 ===
Node [0,8], mid=4:
  - A at mid=4: 2(4)+1 = 9
  - B at mid=4: -4+10 = 6
  - B wins at mid, swap: node stores B, push A down
  - A at lo=0: 2(0)+1 = 1
  - B at lo=0: -0+10 = 10
  - A better at lo, go LEFT

Node [0,4], mid=2:
  - No existing line, store A
  Tree:
        [0,8] -> B
        /
    [0,4] -> A

=== Insert Line C: y = 0.5x + 4 ===
Node [0,8], mid=4:
  - B at mid=4: 6
  - C at mid=4: 0.5(4)+4 = 6
  - Tie! Keep B (arbitrary), push C
  - C at lo=0: 0.5(0)+4 = 4
  - B at lo=0: 10
  - C better at lo, go LEFT

Node [0,4], mid=2:
  - A at mid=2: 2(2)+1 = 5
  - C at mid=2: 0.5(2)+4 = 5
  - Tie! Keep A, push C
  - C at lo=0: 4
  - A at lo=0: 1
  - A better at lo, go RIGHT

Node [3,4], mid=3:
  - No existing line, store C

Final Tree:
            [0,8] -> B (y=-x+10)
            /
        [0,4] -> A (y=2x+1)
            \
          [3,4] -> C (y=0.5x+4)

Query Example: Find min at x=1

Query x=1:
  Node [0,8]: B gives -1+10=9, go left (1 <= 4)
  Node [0,4]: A gives 2(1)+1=3, go left (1 <= 2)
  Node [0,2]: null, return inf

  Result: min(9, 3, inf) = 3 (from line A)

Solution: Python Implementation

class LiChaoTree:
  """
  Li Chao Tree for minimum line queries.

  Time: O(log N) per insert/query
  Space: O(N) where N = hi - lo + 1
  """

  def __init__(self, lo: int, hi: int):
    self.lo = lo
    self.hi = hi
    self.tree = {}  # node_id -> (m, b) representing y = mx + b
    self.INF = float('inf')

  def _eval(self, line, x):
    """Evaluate line y = mx + b at point x."""
    if line is None:
      return self.INF
    m, b = line
    return m * x + b

  def insert(self, m: int, b: int):
    """Insert line y = mx + b."""
    self._insert(1, self.lo, self.hi, (m, b))

  def _insert(self, node: int, lo: int, hi: int, new_line):
    if lo > hi:
      return

    mid = (lo + hi) // 2
    cur_line = self.tree.get(node)

    # Determine winner at midpoint
    new_better_at_mid = self._eval(new_line, mid) < self._eval(cur_line, mid)

    if new_better_at_mid:
      self.tree[node] = new_line
      new_line, cur_line = cur_line, new_line

    if lo == hi or new_line is None:
      return

    # Determine which side the loser might still win
    new_better_at_lo = self._eval(new_line, lo) < self._eval(cur_line, lo)

    if new_better_at_lo:
      self._insert(2 * node, lo, mid, new_line)
    else:
      self._insert(2 * node + 1, mid + 1, hi, new_line)

  def query(self, x: int) -> int:
    """Query minimum y-value at x."""
    return self._query(1, self.lo, self.hi, x)

  def _query(self, node: int, lo: int, hi: int, x: int):
    if lo > hi or node not in self.tree:
      return self.INF

    mid = (lo + hi) // 2
    cur_val = self._eval(self.tree.get(node), x)

    if lo == hi:
      return cur_val

    if x <= mid:
      return min(cur_val, self._query(2 * node, lo, mid, x))
    else:
      return min(cur_val, self._query(2 * node + 1, mid + 1, hi, x))


# Example usage
if __name__ == "__main__":
  tree = LiChaoTree(0, 1000000)

  # Insert lines: y = mx + b
  tree.insert(2, 1)      # y = 2x + 1
  tree.insert(-1, 10)    # y = -x + 10
  tree.insert(0, 5)      # y = 5 (horizontal)

  # Query minimum at various x
  print(tree.query(0))   # min at x=0
  print(tree.query(5))   # min at x=5
  print(tree.query(10))  # min at x=10

Common Mistakes

Mistake 1: Using Wrong Infinity Value

Problem: When m and x are both up to 10^6, their product exceeds int range. Fix: Use long long for all line evaluations and a sufficiently large INF.

Mistake 2: Wrong Recursion Direction

Problem: The loser should go to the child where it has a chance to win. Fix: Use XOR logic: if results differ at lo and mid, go left; else go right.

Mistake 3: Not Handling Empty Nodes

# WRONG: Accessing node without checking
cur_val = self.tree[node].eval(x)  # KeyError if node doesn't exist

# CORRECT: Check for existence
cur_line = self.tree.get(node)
if cur_line is None:
  return self.INF

Edge Cases

When to Use Li Chao Tree

Use Li Chao Tree When:

• Lines are inserted in arbitrary order (no slope sorting)
• Queries come in arbitrary order (no x sorting)
• You need online queries (no offline processing possible)
• DP optimization where slopes are not monotonic

Use Standard CHT Instead When:

• Lines come in sorted slope order AND queries are sorted
• Memory is very tight (CHT uses O(n), Li Chao uses O(range))
• You need the absolute fastest constant factor

Pattern Recognition Checklist:

• DP recurrence of form: dp[i] = min(dp[j] + cost(j, i)) where cost(j,i) = a[j] * b[i] + c[j] -> CHT/Li Chao
• Need min/max over lines at arbitrary x? -> Li Chao Tree
• Slopes not sorted, queries not sorted? -> Li Chao Tree (not basic CHT)
• Need to delete lines? -> Consider other structures

Comparison: Li Chao vs CHT Implementations

*O(1) queries possible with pointer technique when x values are monotonic.

Related Problems

Prerequisites (Do These First)

Direct Applications

Harder (Do These After)

Key Takeaways

1. Core Idea: Store “winner” line at midpoint, push “loser” to potential winning region
2. Main Advantage: Handles arbitrary insert and query order
3. Trade-off: O(N) space for x-range vs O(n) space for CHT
4. Use Case: DP optimization when slopes/queries are unsorted

Practice Checklist

Before moving on, make sure you can:

• Implement Li Chao Tree from scratch
• Explain why the loser goes to a specific child
• Convert a DP problem to Li Chao Tree form
• Choose between CHT and Li Chao Tree for a given problem
• Handle both min and max query variants

Additional Resources

• CP-Algorithms: Li Chao Tree
• Codeforces Blog: Li Chao Tree Tutorial
• KACTL Implementation