一次関数（直線）を管理するデータ構造． 空の集合 $S$ に対して以下のクエリが高速に行える．

• add(a,b) : $S$ に $(a,b)$ を追加
• query(x) : $\min \{ax+b\mid (a,b)\in S\}$ を返す

基本アイデア

簡単のため以下ではどの二つの直線も一点で交わり，その交点は全て異なる場合を考える．

無駄な直線の削除

直線の集合には，絶対に最小値を取らない直線が存在する場合がある．

この直線を適宜削除し，どの直線も最小値を取る $x$ が存在するようにしたい

直線集合

赤が最小値，灰が入らない直線

今管理している直線を傾き (a) の降順に $f_1,\dots,f_m$ とおく． まず $x$ を $-\infty$ から $\infty$ まで動かして $f_1(x),\dots,f_m(x)$ の大小関係の推移に注目してみる． 各 $i<j$ に対し $f_i$ と $f_j$ の交点の $x$ 座標を以下では $x_{i,j}$ と書く．

始めは $f_1(x)<f_2(x)<\cdots<f_m(x)$ が成立する． その後各 $i<j$ について $x_{i,j}$ で $f_i(x)<f_j(x)$ が $f_i(x)> f_j(x)$ に逆転し，最後には $f_1(x)>f_2(x)>\cdots>f_m(x)$ となる．

したがって $f_1$ と $f_m$ は明らかに最小値を取る $x$ が存在する．

また， $1<i<m$ が $x_{i,i+1}<x_{i-1,i}$ 満たす時， $f_i$ は最小値を取る $x$ が存在しない． これは $f_i$ が $f_{i-1}$ より下にいく前に $f_{i+1}$ が $f_i$ の下に行くためである．

$f_2$ は最小値を取ることがない

逆に各 $1<i<m$ について $x_{i-1,i} < x_{i,i+1}$ が成り立つなら全ての $f_i$ は最小値を取る $x$ が存在． これは例えば $m$ の昇順に帰納法で示すことができる（詳細略）．

結局 $x_{i,i+1}<x_{i-1,i}$ を満たす $i$ が発生するたびに $f_i$ を $S$ から削除することを繰り返し，常に $x_{i-1,i} < x_{i,i+1}$ が成り立つようにしておくことで，最小値を取る $x$ が存在する直線だけを管理している状態に出来る．

今この条件が満たされている $S$ に対し新たに直線を追加する時を考える． 追加後の $S$ を傾き降順に $f_1,\dots,f_m$ とおき，新たに追加された直線が $f_i$ とする．