プロンプトとコンテキスト
履歴機能を持つ整数配列の構造を実装してください。各更新では1つの位置の値を変更し、クエリでは任意の古いバージョンにおける閉区間の合計を要求できます。古いバージョンは不変（immutable）のままでなければなりません。座標の境界、時間・空間計算量、バージョンの分岐、およびテストについて説明してください。
これは、分割統治法、構造共有、不変更新、境界処理、計算量の証明に関する難度の高いデータ構造の設問です。配列の長さは固定、点代入更新、および閉区間での区間和 [l, r] を前提とします。区間更新、削除、またはバージョンのマージは別の拡張機能であり、実装前に言及する必要があります。
面接官がテストしていること
面接官は、永続化によって古いルートがクエリ可能な状態に保たれること、つまり更新のたびにツリー全体をコピーするわけではないことを受験者が明確に理解しているかを確認しています。優れた実装は、更新パスに沿って新しいノードを作成し、変更されていない部分木を再利用し、バージョンごとに1つのルートを保存します。また、区間の規約、空クエリの挙動、バージョン番号付け、負の値、境界、および空間の上限についても言及します。
最初に確認すべき明確化の質問
- 配列の長さと座標空間は固定ですか？それとも事前に座標圧縮が可能ですか？
- 更新は代入ですか、それとも加算ですか？また、同じ位置を繰り返し更新できますか？
- 区間は閉区間ですか、それとも半開区間ですか？また、空の区間は何を返すべきですか？
- バージョンは任意の古いルートから分岐できますか？それとも最新バージョンから追記するだけですか？
- スレッドセーフ性、ディスクへの永続化、またはプロセス間共有は必要ですか？
- 正確な整数和、オーバーフローチェック、または多倍長整数（BigInt）が必要ですか？
- バージョン数および総操作数の上限は何ですか？
30秒の回答フレームワーク
「各バージョンを不変セグメント木のルートで表現します。点更新ではルートから葉までの O(log n) 個のノードをコピーし、変更のない兄弟部分木はすべて共有します。クエリは要求されたルートから探索し、完全に包含されるノードの合計値を返します。ルートの配列を保持することで、任意の古いバージョンからの分岐が可能です。構築は O(n)、各更新とクエリは O(log n)、合計空間計算量は初期ツリーに加えて更新ごとに O(log n) 個の新規ノードとなります。フォーク、境界値、負の値、およびランダムな差分テストを実施します。」
ステップバイステップの回答
まず不変条件を述べます。ノードは特定の閉区間 [lo, hi] をカバーし、sum はそのバージョンにおけるその区間の合計であり、葉は1つの位置をカバーし、内部ノードの合計は子ノードの合計と等しく、ノードは作成後に決して変更されません。各バージョンは1つのルートポインタを保存します。
配列のインデックス 0..n-1 に対して、再帰的に構築します。入力がスパースで大きな整数座標を使用する場合は、構築前に使用可能な座標を収集して圧縮します。巨大な座標空間をそのまま実体化してはいけません。
以下の擬似コードは、代入更新と閉区間クエリを使用しています。
Node { left, right, sum }
build(lo, hi, values):
if lo == hi: return Node(null, null, values[lo])
mid = floor((lo + hi) / 2)
left = build(lo, mid, values)
right = build(mid + 1, hi, values)
return Node(left, right, left.sum + right.sum)
set(node, lo, hi, index, value):
if lo == hi: return Node(null, null, value)
mid = floor((lo + hi) / 2)
if index <= mid:
nextLeft = set(node.left, lo, mid, index, value)
nextRight = node.right
else:
nextLeft = node.left
nextRight = set(node.right, mid + 1, hi, index, value)
return Node(nextLeft, nextRight, nextLeft.sum + nextRight.sum)
sum(node, lo, hi, ql, qr):
if qr < lo or hi < ql: return 0
if ql <= lo and hi <= qr: return node.sum
mid = floor((lo + hi) / 2)
return sum(node.left, lo, mid, ql, qr)
+ sum(node.right, mid + 1, hi, ql, qr)roots[0] は初期ツリーを保存します。バージョン base から位置 i を更新するには、roots[next] = set(roots[base], 0, n - 1, i, value) を作成します。バージョングラフはルートによって参照される有向非巡回共有構造（DAG）であり、線形な履歴チェーンではありません。分岐とは、更新の入力として任意の古いルートを選択することを意味します。
境界を明示的に処理します。n == 0 の場合はルートを作成しません。範囲外のインデックスや ql > qr は構造化エラーを返すか、決められた契約に従う必要があります。クエリのクリッピングによって呼び出し元のエラーを暗黙に隠してはいけません。整数の境界が大きい可能性がある場合は、lo + floor((hi - lo) / 2) を計算して lo + hi のオーバーフローを防ぎます。
初期構築では O(n) 個のノードと O(n) の時間を使用します。点更新では1つのルートから葉へのパスをコピーするため、O(log n) 個のノードを作成します。区間クエリは O(log n) 個の標準的な区間を訪問し、O(log n) の時間がかかります。u 回の更新後、総空間計算量は O(nu) ではなく O(n + u log n) です。区間代入や区間加算もパスクローンを使用できますが、遅延タグ（lazy tags）、ノードの結合、および空間の境界が変化します。
不変性は正当性の境界です。更新中に古いノードの sum や子ポインタを変更してはいけません。ガベージコレクションまたは参照カウントでノードを解放できます。手動で解放する場合は、どのバージョンのルートがまだ生存しているかを把握する必要があります。1つのバージョンを削除しても、別のバージョンによってまだ共有されているノードを解放することはできないためです。
最新バージョンのみが重要である場合は、通常のセグメント木の方が単純です。永続化は、履歴クエリ、ロールバック、分岐実験、またはタイムトラベルに対してコストを支払う価値があります。完全にオフラインの操作の場合、オフラインの累積和や走査線（sweep-line）手法の方が単純な場合があります。データ構造の選択をクエリのワークロードと結び付けて説明してください。
小さな配列からテストを始めます。更新ごとにプレーンな配列をコピーし、永続構造とランダムなバージョンおよび範囲を比較します。バージョン0からの分岐、同一位置への繰り返しの更新、負の値、単一要素、全範囲、単一点、空の範囲、および両端の境界をカバーします。また、共有状態も確認します。1つの位置を更新した後、変更されていない部分木は同一のオブジェクトIDを維持している必要があります。
不変性を直接テストします。すべての古いバージョンのクエリ結果を保存し、いくつかの分岐更新を実行してから、古いルートに対して再度クエリを実行します。結果が変わった場合は、古いノードが変更されたことを意味します。大規模なワークロードでは、割り当てられたノード数をカウントし、ツリー全体が誤ってコピーされるのではなく、初期 O(n) に更新ごとの O(log n) を加えた程度で増加していることを確認します。
高品質な回答例
「固定長の配列、点代入更新、閉区間の合計、および任意の古いバージョンからの分岐を前提とします。各ノードは [lo, hi] をカバーし、その合計を保存します。ノードは構築後に不変です。roots[v] はバージョン v のルートを保存します。
再帰的に構築します。更新時は、対象の葉へのパスをコピーします。対象側には新しい子を作成し、反対側は古いポインタを再利用して、新しい各親をその子の合計から作成します。要求されたルートからクエリを実行し、重複がない場合は0を返し、完全に含まれる場合はノードの合計を返し、それ以外は再帰します。
構築は O(n) の時間と空間です。各更新は O(log n) 個のノードを作成し、更新とクエリは両方とも O(log n) です。u 回の更新後の総空間計算量は O(n + u log n) となります。古いルートは依然として古いノードを指しているため、過去のバージョンが汚染されることはありません。大きな座標空間は事前に圧縮し、区間更新の場合は遅延タグと空間計算量を再評価します。
バージョン0からのフォーク、繰り返しの更新、負の値、空の範囲、およびすべての境界について、プレーンな配列のオラクルと比較してテストします。変更されていない部分木が共有され、新しい更新後も古いクエリの結果が変わらないことを検証します。最新の値のみが必要な場合は通常のセグメント木を使用し、履歴やロールバックが実際の要件である場合にのみ永続化のコストを支払います。」
よくある間違い
- ツリー全体をコピーする → 各更新の空間が O(n) になる → ルートから葉へのパスのみをコピーする。
- 古いノードを変更して新しいルートを保存する → それを共有するすべての古いバージョンが変化してしまう → ノードを不変に保つ。
- バージョンを単一のチェーンとして扱う → 任意のルートからの実験やロールバックができなくなる → ルート配列による分岐を可能にする。
- 区間の規約を暗黙のままにする → 閉区間と半開区間の違いが境界バグを引き起こす → 不変条件とシグネチャで1つの規約に固定する。
- 巨大な座標空間をそのまま実体化する → 実際の点数に対して空間が過大になる → 座標圧縮を行うか動的ノードを使用する。
- 合計空間が O(n) であると主張する → 各更新でパスノードが追加される → O(n + u log n) と述べる。
- バージョン削除時にノードを再帰的に解放する → 別のバージョンがそれらをまだ共有している可能性がある → 参照カウントまたはガベージコレクションを使用する。
フォローアップの質問と回答
フォローアップ1：この構造は区間加算（range addition）に対しても機能しますか？
更新によって影響を受けるノードをパスクローンし、関連するすべてのパスをコピーします。遅延タグを使用する場合、そのタグは新しいノードに属するものであり、共有されているノードに書き込んではいけません。新しいノードの数は O(log n) から O(log n + カバーされるノード数) の範囲になり得るため、点更新の主張をそのまま流用せず、実際の実装に合わせた境界を示してください。
フォローアップ2：2つのバージョン間の差分をどのようにクエリしますか？
両方のルートを同時にトラバースします。ノードのポインタが同一である場合、その部分木は変更されていないためスキップできます。そうでない場合は探索を進めるか、集約された差分を計算します。変更されたすべての位置を報告する場合、計算量は出力サイズにも依存します。
フォローアップ3：毎回配列をコピーして累積和を構築しないのはなぜですか？
配列のコピーには、更新ごとに O(n) の時間と空間がかかります。バージョン数が少なく配列が小さい場合はその単純な手法の方が優れている場合もありますが、永続化は O(log n) の新規空間と引き換えに、多数のバージョン、オンラインの履歴クエリ、および局所的な更新を可能にします。
フォローアップ4：バージョンのルートをディスクに永続化するにはどうすればよいですか？
ノードに不変のIDを割り当て、メモリポインタの代わりに子のIDを保存し、バージョンとルートの対応テーブルを永続化します。追記（append）またはコピーオンライトを使用し、ルートを公開する前に新しいノードが永続化されていることを確認します。復元時は参照とルートテーブルを検証し、生のメモリアドレスを決してシリアライズしないでください。
フォローアップ5：古いバージョンが汚染されていないことをどのように証明しますか？
更新に対する数学的帰納法を用います。新しいノードのみが作成され、古いノードのフィールドは変更されず、新しいツリーは変更されていない古い部分木と新しいパスを参照します。したがって、古いルートから到達可能なノードとその値は変更されないままとなります。ランダムな分岐差分テストによって、実際の動作でもこの不変条件が検証されます。