まえがき
この記事は投稿者(NokonoKotlin)の個人サイトの記事から Qiita 用に移植 & 加筆したものです。
(この文言は記事が剽窃でないことを周知するためのものであり、個人サイトの宣伝ではないことをあらかじめご了承ください。)
イントロダクション
Li-Chao-Tree というデータ構造を書きました。このデータ構造は、平面座標系に線分を追加する操作と、指定した $x$ 座標をカバーする線分の $y$ 座標の min/max を計算する操作をサポートします。
アルゴリズムは動的双対セグメント木をベースとしております。動的,双対についてはセグメント木の記事を参照してください。min の取得と max の取得は実質的に同じことなので、今回は min の取得の解説を行います。
注意 : 線分を英語でセグメントと呼びますが、この記事でセグメントといえば、セグメント木のノードがカバーする区間を指すものとします。
双対セグメント木で大体想像がつくと思いますが、追加する線分の定義域 (線分の $x$ 座標の区間) と対応するようにセグメントを分割します。それぞれのセグメントには線分を持たせ、ある $x$ 座標をカバーするようなセグメントそれぞれが持つ線分の $y$ 座標を比較することで、ある $x$ 座標における $y$ 座標の min を取得します。
データ構造の仕組みを紹介する前に、Li-Chao-Tree の要件をまとめておきます。
- セグメント木のセグメントは半開区間。追加する線分は閉区間(または開区間)。
-
アクセスは整数座標のみ。よってセグメント $[l,r)$ は実際は $(l,l+1,\dots,r-2,r-1)$ を表す。
- 特にセグメント木の末端ノード $[l,l+1)$ は $x = l$ の一点のみに対応している。
-
整数の $x$ 座標を指定しても、$y$ 座標は必ずしも整数とは限らない。
- 二点 (a,b) , (c,d) を結ぶ線分をつなげる場合など
- 臨機応変に $y$ 座標の型を設定する必要がある
データ構造の仕組み
動的セグメント木は必要に応じてセグメントを動的に生成するので、はじめノードは root となるノードしか存在しません。これを、任意の線分より大きい線分 $y = \mathrm{init}$ で初期化しておきます。(定義域が大きい場合はオーバーフロー注意ポイントです。)
ここに以下の線分 $S_1$ を追加してみます。
$S_1$ の定義域に対応するセグメントを選択し、$S_1$ を記録しておきます。ここでとっても罠なのが、追加する線分は両端の端点も含むので、線分の定義域が $[l,r]$ なら、$[l,r+1)$ に対応するセグメントを選択する必要があります。
続いて、$S_2$ を追加します。
$S_1$ の定義域のセグメントと独立なので、スムーズに $S_2$ を記録できました。
次は $S_3$ を追加します。このとき $S_1$ を持つセグメントと競合が起こります。
選択したセグメントにはすでに $S_1$ が記録されているので、ここで線分 $S_1$ と $S_3$ の大小の比較が発生します。$2$ つの線分上の $y$ 座標の大小は交点の前後で変わることから、少しテクニカルな比較 & ノードの更新を行う必要があります。
まず、セグメント木の末端 $[r,r+1)$ は $x = r$ のちょうど $1$ 点に対応するので、$x = r$ における $y$ 座標が小さい方の線分を採用することができます。下図の水色の部分がこれにあたります。
競合するセグメントが $2$ つの線分の交点をカバーする場合、その交点がセグメントのどの領域 (子セグメント) に存在するかを計算する必要があります。セグメントの左端,中点,右端 $(l,m,r)$ における $y$ 座標の大小関係を比較することで、交点がセグメントの左側または右側のどちらに存在するかを特定できます。ただし、交点がちょうど左端や中点にある場合は別の処理(後述)とします。
- $x = l$ における $y$ 座標の大小関係が、$x = m$ における $y$ 座標の大小関係と異なる場合、交点は左側 : $[l,m)$ に存在する。
- $x = m$ における $y$ 座標の大小関係が、$x = r$ における $y$ 座標の大小関係と異なる場合、交点は右側 : $[m,r)$ に存在する。
このとき、交点が存在しない側の子セグメントに $S_3$ を採用する代わりに、今見ているセグメントに $S_3$ を記録します。そして、採用されなかった線分 $S_1$ を、交点が存在する領域側の子セグメントに伝播させ、今と同じ処理を伝播先で再帰的に行います。
水色の部分を全て $S_3$ で置き換えてしまいましたが問題ありません。なぜなら、ここで $S_1$ を子セグメントに伝播させる操作は、水色のセグメントの $S_1 \leq S_3$ の区間 (定義域) に $S_1$ を新たに追加する操作と同義なので、再帰的に正当性が保証されます。
伝播先の処理も見てみましょう。$l,m,r$ を見ると区間内に交点が存在しないことがわかるので、$x=l$ (セグメント内ならどこでも良い) での $y$ 座標を参照して線分を採用します。
ただし、交点が $x = l$ または $x = m$ の場合は特殊な処理が必要です。
- $x = l$ で交差する場合 $\rightarrow$ 線分の傾きの大小を参照し、セグメント全体の線分を置き換える。
- $x = m$ で交差する場合 $\rightarrow$ 線分の傾きの大小から、セグメントに元々ある線分よりも $y$ 座標が小さい領域側の子セグメントに伝播させる。
最終的に、動的双対セグメント木には以下のように線分が記録されます。
このセグメントツリーを使うことで、指定した $x$ 座標をカバーする線分の min にアクセスすることができます。
設計
線分を追加する方法ごとに、$y$ 座標の型を変える必要がある。
- $x \in [l,r]$ に $y = ax+b$ を追加 $\rightarrow$ 整数型で良い (が、オーバーフロー注意)
- $2$ 点 $(a,b),(c,d)$ を結ぶ線分を追加 $\rightarrow$ 有理数型 ( 精度を要求するなら __float128 など (遅いけど) )
90° の線分を追加する際は、追加する $x$ 座標に、端点の $y$ 座標を記録する。端点を含めない場合も極限を考えて同じように追加して良い。