Li Chao interval offers: limit each line to its valid minutes

Last updated: 4 Oct 20269 min read

tutorial

An interval-limited Li Chao index answers the minimum value among lines that are valid at a queried integer coordinate. Its outer segment recursion decomposes each offer's half-open validity interval into covered nodes. Inside each covered node, a Li Chao insertion keeps the line that is cheaper at that node's midpoint and sends a displaced line toward the side where it can still win. Two distinct affine lines cross at most once, which makes that displacement rule valid. A point query follows the coordinate path and evaluates every stored line it encounters. The example uses one fixed integer minute domain, accepts overlapping offers and negative slopes, and returns no result where no offer covers the minute. Lines remain after insertion; there is no expiration or deletion operation.

Operational case

On minutes [0,16), a base offer charges 3x+47 everywhere. A second charges -2x+83 only on [4,12), and a third charges x+29 only on [9,16). The least prices at minutes 2, 7, 10, and 15 are 53, 68, 39, and 44. At minute 7, the second line costs 69, so the base offer wins by one; at minute 10, the third offer costs 39. Evaluating the second line at minute 15 would be a correctness error even if it happened to be cheaper. Query endpoints are integer points and the interval right endpoint is excluded.

Working Python program

class SegmentTariffIndex:
    def __init__(self, first_minute, past_last_minute):
        if first_minute >= past_last_minute:
            raise ValueError("nonempty integer domain required")
        self.start = first_minute
        self.stop = past_last_minute
        self.lines = {}

    @staticmethod
    def _charge(line, minute):
        slope, base = line
        return slope * minute + base

    def _place_line(self, node, low, high, offered):
        incumbent = self.lines.get(node)
        if incumbent is None:
            self.lines[node] = offered
            return
        middle = (low + high) // 2
        if self._charge(offered, middle) < self._charge(incumbent, middle):
            self.lines[node], offered = offered, incumbent
        incumbent = self.lines[node]
        if high - low == 1:
            return
        if self._charge(offered, low) < self._charge(incumbent, low):
            self._place_line(node * 2, low, middle, offered)
        elif self._charge(offered, high - 1) < self._charge(incumbent, high - 1):
            self._place_line(node * 2 + 1, middle, high, offered)

    def add_tariff(self, first_minute, past_last_minute, slope, base):
        if not self.start <= first_minute < past_last_minute <= self.stop:
            raise IndexError("offer interval outside domain")

        def visit(node, low, high):
            if past_last_minute <= low or high <= first_minute:
                return
            if first_minute <= low and high <= past_last_minute:
                self._place_line(node, low, high, (slope, base))
                return
            middle = (low + high) // 2
            visit(node * 2, low, middle)
            visit(node * 2 + 1, middle, high)

        visit(1, self.start, self.stop)

    def minimum_charge(self, minute):
        if not self.start <= minute < self.stop:
            raise IndexError(minute)
        node, low, high = 1, self.start, self.stop
        answer = None
        while True:
            if node in self.lines:
                candidate = self._charge(self.lines[node], minute)
                answer = candidate if answer is None else min(answer, candidate)
            if high - low == 1:
                return answer
            middle = (low + high) // 2
            if minute < middle:
                node, high = node * 2, middle
            else:
                node, low = node * 2 + 1, middle


tariffs = SegmentTariffIndex(0, 16)
tariffs.add_tariff(0, 16, 3, 47)
tariffs.add_tariff(4, 12, -2, 83)
tariffs.add_tariff(9, 16, 1, 29)
print(tariffs.minimum_charge(2), tariffs.minimum_charge(7))
print(tariffs.minimum_charge(10), tariffs.minimum_charge(15))

Output

53 68
39 44

Time, space, and tradeoff

Let D be the number of integer coordinates in the fixed domain. A validity interval decomposes into O(log D) covered segment nodes, and placing a line inside each can descend O(log D) more levels, so one offer insertion costs O(log squared D) worst-case time. A point query reads O(log D) nodes. The sparse dictionary retains up to O(M log squared D) line-bearing nodes after M offers in the worst case, plus recursion of O(log D). This implementation does not prove a smaller compressed-memory bound. Whole-domain Li Chao insertion is cheaper because it performs only one placement. A linear scan over M active offers costs O(M) per query and can be preferable for a tiny catalog.

Common Mistakes

Do not let a line affect coordinates outside its validity interval.
Do not compare only slopes; intercepts decide where lines cross.
Do not query outside the fixed integer domain.
Do not describe insertion here as the whole-domain O(log D) operation.

Connected lessons

Compare this operation boundary with Persistent subarray ranks: subtract prefix frequency trees, Maximum-subarray segment trees: preserve the crossing burst, All-one frequency buckets: increment, decrement, and read both extremes, Patricia binary routing: compress chains without losing prefix matches, then complete the audit project and decision quiz.

data structures

range-query-structures