問題と背景
オンラインサービスが任意の挿入順序で直線 y = m x + b を受信し、整数のクエリ点 x における最小値を返す必要があります。クエリ点も任意です。拡張として、直線を区間 [l, r] に制限したり、代わりに最大値を求めたりすることがあります。
この問題は、動的計画法の最適化、分割統治法の不変条件、およびセグメント木の実装力をテストします。優れた回答では、まずクエリドメインが離散的かつ有界であるかを述べ、次に各ノードがどこかで勝つ直線を1本保持でき、残りの候補は厳密に1つの子ノードに送られる理由を説明します。
面接官が評価するポイント
- クエリごとにすべての直線を走査する
O(number_of_lines)のボトルネックを導出できること。 - 中点比較、スワップ、および再帰の不変条件を理解していること。
- 任意の傾き、重複する直線、負の座標、およびオーバーフローを適切に処理できること。
- 離散整数ドメイン、連続ドメイン、および線分制限された直線を区別できること。
- 挿入/クエリの計算量
O(log C)と、線分挿入の計算量O(log^2 C)の境界を示せること。 - 傾きとクエリが単調な場合に、標準的なConvex Hull Trickがよりシンプルになる理由を説明できること。
最初に確認すべき明確化のための質問
- クエリ点は整数ですか、それとも実数ですか？ドメインは固定
[L, R]ですか、それとも動的に拡張されますか？これにより、深さと座標圧縮の要否が決まります。 - 操作は最小値ですか、それとも最大値ですか？空集合は許可されますか？その場合、実際の答えと衝突しない番兵（センチネル）は何ですか？
- 傾き、切片、および答えの最大値の大きさはどれくらいですか？より大きな整数型やオーバーフローチェック付きの乗算が必要ですか？
- 直線は
[l, r]上でのみ有効ですか？区間挿入は直線を複数のツリーノードに分散させます。 - 挿入される傾きやクエリ点は単調ですか？もしそうなら、dequeベースのConvex Hull Trickの方が定数倍が小さい場合があります。
30秒の回答フレームワーク
セグメント木のドメイン [L, R] を構築し、各ノードに1本の候補直線を保持します。新しい直線を挿入する際、端点と中点においてノードの直線と比較します。新しい直線が中点で勝つ場合、ノードの直線とスワップします。追い出された直線が依然として勝てる可能性があるのは左半分または右半分のいずれか一方のみであるため、一方の子ノードにのみ再帰します。点クエリは、根から葉までのパス上のすべての直線を評価し、最小値を取ります。ドメインの長さを C とすると、挿入とクエリは O(log C) です。直線を区間に制限する場合のコストは O(log^2 C) です。最大値クエリの場合は比較器を逆にします。
ステップバイステップの詳細解説
1. 全探索とボトルネック
直線のリストを保持し、各クエリに対してすべての m x + b を評価します。これにはクエリあたり O(number_of_lines) のコストがかかります。動的計画法の遷移では挿入とクエリが交互に発生するため、問題を変えずに傾きやクエリ点を事前にソートすることはできません。データ構造によって値のドメイン全体に比較を分散させる必要があります。
2. ノードの不変条件
ノードは閉区間 [lo, hi] を表し、1本の直線 cur を保持します。まだ子ノードにプッシュされていない直線の中で、cur はこの区間内の少なくとも1つの候補位置において他の直線と同等以上に最適です。依然として最適になり得る他の直線は、左または右の子ノードでのみ最適になり得ます。葉ノードでは、ノードは1点で最も優れている直線を保持するだけで十分です。
3. 中点スワップと再帰の方向
nw を新しい直線、cur をノードの直線、mid を中点とします。mid における新しい直線の値の方が小さい場合、ノードが中点での勝者を保持するようにスワップします。スワップ後、lo においてどちらの直線が勝つかを比較します。追い出された直線が左端点で勝っている場合、その直線が再び最適になり得るのは左半分のみです。そうでない場合は右端点を比較し、右側に再帰します。2つの直線の差は線形であるため、それらの順序が入れ替わるのは最大でも1回です。
add(node, lo, hi, nw):
mid = (lo + hi) // 2
left = nw(lo) < cur(lo)
middle = nw(mid) < cur(mid)
if middle: swap(nw, cur)
if lo == hi: return
if left != middle: add(leftChild, lo, mid, nw)
else: add(rightChild, mid + 1, hi, nw)安全な中点計算式を使用してください。m * x + b が64ビットの範囲を超える可能性がある場合は、より大きな型、チェック付き算術演算、または明示的な飽和ポリシーを使用してください。
4. 根から葉へのパスのクエリ
点 x については、x を含む葉に向かって再帰し、訪問したすべてのノードで保持されている直線を x で評価し、その最小値を返します。他の部分木はその点を含んでいません。動的セグメント木（implicit tree）は、挿入によってアクセスされたパス上にのみノードを割り当てます。空のノードは正の無限大の番兵を返します。
5. 区間に制限された直線の挿入
直線が [ql, qr] 上でのみ有効である場合、標準的なセグメント木を用いてその区間を分解します。完全にカバーされる各ノードに直線を1回挿入し、部分的にカバーされるノードには再帰します。この分解は O(log C) 個のノードにアクセスし、各Li Chao挿入のコストは O(log C) であるため、計算量は O(log^2 C) となります。点クエリは O(log C) のままです。
6. 離散座標と連続クエリ
クエリが既知の有限集合から来る場合、x値をソートして重複を排除し、そのインデックスを葉として使用します。これにより、巨大な空ドメインを構築することを回避できます。実数値のクエリの場合は、精度と停止条件を明示的に規定してください。整数ドメインの証明は非有界な連続ドメインには自動的には適用されません。区間を有界にし、浮動小数点比較の許容誤差（イプシロン）を定義してください。
7. トレードオフとテストケース
傾きとクエリ点の両方が単調である場合、dequeベースのConvex Hull Trickの方が定数倍が小さくなります。Li Chao treeは、ノード数と再帰が増える代償として、任意の順序に対してより堅牢です。空集合、1点のみのドメイン、重複する傾き、同一の直線、負の座標、中点での交差、一方の端点をカバーする直線、大きな積、および最大値クエリをテストし、すべての結果を全探索の評価と比較してください。
質の高い模範解答
まず、クエリドメインが有界な整数区間であるか、座標圧縮が必要かを確認します。[L, R] に対して、候補直線をノードに格納するLi Chao treeを構築します。挿入では端点と中点を比較します。中点での勝者がノードに残り、もう一方の直線は2つの直線の順序が入れ替わり得る側の半分にのみ再帰します。両者の差は線形であるため、追い出された直線が2つの離れた方向で同時に優位になることはありません。点クエリは1本の根から葉へのパスに沿って最小値を取るため、挿入とクエリはともに O(log C) となります。傾きとクエリが単調な場合はConvex Hull Trickを使用します。区間制限された直線にはセグメント分解が必要であり、挿入には O(log^2 C) かかります。
よくある間違い
- 中点のみを比較して停止する → もう一方の直線が端点で勝つ可能性がある → 端点と中点の比較を用いて進む子ノードを1つ選択する。
- 傾きが単調でなければならないと思い込む → 任意の順序での挿入で誤った答えを出す → Li Chaoの区間不変条件を使用するか、Convex Hullの前提条件を明示する。
m * x + bをチェックなしの64ビット演算で計算する → オーバーフローによって比較結果が変わる → より大きな型またはチェック付き算術演算を使用する。- 非有界な動的ドメインを許可する → 再帰が終了しない → 整数ドメインを有界にするか、座標圧縮を行うか、浮動小数点精度を定義する。
- 区間の直線をすべての葉にコピーする → 計算量が悪化する → 区間を分解し、完全にカバーされたノードに挿入する。
- 空ノードに対して0を返す → 最小値が誤って低くなる → 答えの範囲外にある正の無限大の番兵を使用する。
フォローアップ質問と回答
最大値クエリの場合は何が変わりますか？
すべての比較を逆にするか、m と b の両方を符号反転させて最小値クエリを解き、その結果を符号反転します。最終的な戻り値だけを変更するのではなく、空集合とオーバーフローのセマンティクスを一貫して反転させる必要があります。
配列ベースのツリーで10の18乗のドメインを処理できますか？
すべてのノードを事前割り当てすることは不可能です。挿入パスに沿ってのみノードを作成する動的セグメント木（implicit tree）を使用します。深さはおよそドメインのビット数になります。クエリ座標が有限である場合は、通常、座標圧縮の方がメモリを節約できます。
2つの直線が中点で同値（タイ）になった場合、どのように誤った分岐を防ぎますか？
古い直線を保持する、または傾きの順序を優先するなど、決定論的なタイブレークルールを選択します。端点と中点で一貫して厳密不等号を使用し、同一の直線が無限に再帰しないようにします。
なぜ片側の再帰だけで十分なのですか？
2本の直線の差は線形であり、ゼロ点は最大でも1つです。中点での勝者が保持された後、追い出された直線が逆転できるのは順序が異なる端点の側のみであるため、左または右の子ノードが一意に選択されます。
Convex Hull Trickの方が優れているのはどのような場合ですか？
直線が単調な傾きの順序で到着し、クエリも単調である場合、凸包dequeを使用することで、より少ないメモリで償却 O(1) のクエリ、または二分探索による O(log n) のクエリを実現できます。順序が任意である場合や、線分制限された直線の場合は、Li Chao treeの汎用性が有利になります。