Convex-Hull Trick - sataniC++概要 直線集合に対して、「への直線の追加」(以下、追加クエリ)と、「あるに対し、の中で最小値(あるいは最大値)を取るような直線の値を求める」(以下、最小値クエリ)という2つのクエリを効率的に行うことが出来ます。 使える状況 DPの漸化式を整理したときなどにおいて、といった式が出てきたときに、Convex-Hull Trickを用いることで効率的に値を求めることが出来ます。 説明 ここでは最小値を求めるときのみを説明します(最大値を求めるときは上⇔下、増加⇔減少など、文章を補って読んでください)。 クエリ まず、それぞれのクエリを見ていきます。 直線集合に直線を追加する 上図は、始め直線集合がであった状態(左)から、そこに新たな直線を追加した状態(右)へと遷移している様子を表しています。 (なお、グラフの描画にはGrapesというソフトを用いています。*1 ) あるに対し、の中で最小値(ある
Convex hull trick - PEGWiki
