Vocabulary - Linear Function

A linear function has the form $f(x) = mx + c$. Given slope $m$ and intercept $c$, for any query $x$, you get $f(x)$ in $O(1)$. In CHT, each previous DP (dynamic programming) state (the subproblem index) $j$ contributes a line.

The slope $m_j$ and intercept $c_j$ depend on values computed at $j$. The query point $x_i$ depends on the current state $i$. Your DP becomes: evaluate all lines at $x_i$, take the minimum. That's still $O(n)$ per state. But most lines are worthless.