# lichao
Implementation of a Li-Chao tree ported from the authors competitive programming library.
Theoretically, a Li-Chao tree should support any function which has the transcending property, but this implementation supports only lines, which are the most common use case.
Currently doesn't support adding custom-width line segments, will be added soon.
Since the performance of Li-Chao trees depends on the size of the domain, it may be preferable to use the Convex hull trick instead.
# Li-Chao trees
Li-Chao trees solve the following problem class in O(log n) time:
```
Given a set S of functions s.t. each pair of functions can intersect at most one point (e.g. lines), efficiently implement
1. Adding a function to S
2. Answering the minimum/maximum value at f(t) for all functions f in S (i.e. \min{f \in S} f(t))
```
Formally, we require the functions to have the *transcending property*, that is, given two functions $f, g \in S$, if $f(t) = g(t)$, then either $f(x) < g(x) \forall x < t$ and $f(x) > g(x) \forall x > t$, or $f(x) > g(x) \forall x < t$ and $f(x) < g(x) \forall x > t$