Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Li Chao trees: minimum linear tariff at a chosen quantity

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A Li Chao tree stores linear cost functions over a declared inclusive integer domain. At each node, it keeps the line that is better at that node's midpoint; a displaced candidate can still be better on one side, so insertion continues only down that side. A point query walks one root-to-leaf path and takes the least value among lines encountered. This version uses integer slopes and intercepts, answers minimum only, and treats every inserted line as valid across the entire domain. It allocates nodes when needed. An empty index has no minimum, and a query outside the domain is rejected rather than silently extrapolated.

Operational case

Three delivery tariffs charge 7 times units plus 13, 4 times units plus 49, and 9 times units minus 11, with units restricted to 0 through 80. At five units the costs are 48, 69, and 34, so the minimum is 34. At 35 units they are 258, 189, and 304, so the minimum is 189. The winner changes as quantity changes; storing only the line with the smallest intercept or slope would fail. Negative intercepts are allowed in this numerical model, but a business system would separately decide whether such tariffs are valid.

Working Python program

python
from dataclasses import dataclass


@dataclass(frozen=True)
class TariffLine:
    slope: int
    intercept: int

    def cost(self, units):
        return self.slope * units + self.intercept


class TariffNode:
    def __init__(self, line):
        self.line = line
        self.left = None
        self.right = None


class LiChaoTariffs:
    def __init__(self, minimum_units, maximum_units):
        if minimum_units > maximum_units:
            raise ValueError("empty integer unit domain")
        self.minimum_units = minimum_units
        self.maximum_units = maximum_units
        self.root = None

    def add_line(self, line):
        self.root = self._insert(self.root, self.minimum_units, self.maximum_units, line)

    def _insert(self, node, left, right, incoming):
        if node is None:
            return TariffNode(incoming)
        middle = (left + right) // 2
        if incoming.cost(middle) < node.line.cost(middle):
            node.line, incoming = incoming, node.line
        if left == right:
            return node
        if incoming.cost(left) < node.line.cost(left):
            node.left = self._insert(node.left, left, middle, incoming)
        elif incoming.cost(right) < node.line.cost(right):
            node.right = self._insert(node.right, middle + 1, right, incoming)
        return node

    def min_cost(self, units):
        if not self.minimum_units <= units <= self.maximum_units:
            raise IndexError("units outside declared domain")
        if self.root is None:
            raise ValueError("no tariff lines have been added")
        node = self.root
        left, right = self.minimum_units, self.maximum_units
        minimum = float("inf")
        while node is not None:
            minimum = min(minimum, node.line.cost(units))
            middle = (left + right) // 2
            if units <= middle:
                node = node.left
                right = middle
            else:
                node = node.right
                left = middle + 1
        return minimum


if __name__ == "__main__":
    tariffs = LiChaoTariffs(0, 80)
    for tariff in (TariffLine(7, 13), TariffLine(4, 49), TariffLine(9, -11)):
        tariffs.add_line(tariff)
    print("units-5=", tariffs.min_cost(5), sep="")
    print("units-35=", tariffs.min_cost(35), sep="")

Output

Output
units-5=34
units-35=189

Time, space, and tradeoff

Let D be the number of integer coordinates in the declared domain and M the number of inserted full-domain lines. Each insertion and point query visits O(log D) nodes; insertion may allocate O(log D) nodes, so total storage is O(M log D) in the worst case. Integer evaluation also has operand-bit cost beyond the tree step count. This version does not delete lines, restrict a line to one subinterval, or expand its coordinate domain. For a small fixed set of lines, a direct O(M) scan avoids tree memory and is often enough. The logarithmic domain cost is useful when many lines and many point queries coexist.

Common Mistakes

  • Do not query outside the declared integer domain.
  • Do not assume one line wins at every quantity because it wins at the midpoint.
  • Do not describe this full-line index as supporting segment-limited tariffs or deletion.
  • Do not take a minimum before any line has been inserted.

Connected lessons

Compare its contract with Square-root blocks: update one capacity and sum a range, Merge-sort trees: count readings below a threshold in one interval, Disjoint sparse tables: immutable sums with constant-time queries, then apply the range workload project and check the range-index quiz.

Li Chao interval offers: limit each line to its valid minutes examines a related structure with a different operation boundary.

data structures
range-query-structures
Storage details