課題設定とスコープ
長さ n の整数配列が与えられたとき、閉区間 [l, r] 内のすべての値に delta を加算する操作と、[l, r] の総和を返す操作の2つのオンライン操作を処理します。目標は、O(n) の構築、操作あたり O(log n)、追加空間 O(n) です。区間は閉区間であり、delta は負の値を取り得ること、要求されない限り永続化はスコープ外であることを明記します。
面接官が見ているポイント
まず不変条件を定義します。tree[p] は常にそのノード区間の真の総和であり、lazy[p] はその総和にはすでに含まれているものの子ノードにはまだ適用されていない一様な加算値です。優れた回答では、完全にカバーされたノードのみを更新し、部分的な探索の前にpushを行い、加算値に対象区間の長さを乗算します。
コーディング前の確認事項
- 更新操作は加算、代入、あるいは区間最小値のいずれですか？これらは遅延タグの合成規則が異なります。
- 集約値は総和、最小値、最大値のどれですか？ノードのマージ方法とタグの計算式が変わります。
- 区間は閉区間ですか？この回答では閉区間
[l, r]を使用します。半開区間の場合は一貫した分割と長さの計算が必要です。 - 値はどの程度大きくなりますか？
tree[p] + delta * lengthは32ビット整数をオーバーフローする可能性があるため、より広い型を選択します。
推奨解法と導出
暗黙的な二分木を配列内に保持します。ノード [lo, hi] は mid で [lo, mid] と [mid+1, hi] に分割されます。完全にカバーされた更新では、tree[p] に delta * (hi-lo+1) を加算し、lazy[p] に delta を累積します。子ノードの値は必要になるまでそのままにしておくことができます。
class LazySumTree:
def __init__(self, values):
self.n = len(values)
self.tree = [0] * (4 * max(1, self.n))
self.lazy = [0] * len(self.tree)
if self.n:
self._build(1, 0, self.n - 1, values)
def _apply(self, p, lo, hi, delta):
self.tree[p] += delta * (hi - lo + 1)
self.lazy[p] += delta
def _push(self, p, lo, hi):
if self.lazy[p] == 0 or lo == hi:
return
mid = (lo + hi) // 2
d = self.lazy[p]
self._apply(p * 2, lo, mid, d)
self._apply(p * 2 + 1, mid + 1, hi, d)
self.lazy[p] = 0同じ不変条件のもとで再帰的に add と sum を完成させます。完全カバー時は _apply を呼び出し、部分カバー時はその前に _push を呼び出します。復帰後に子ノードから親ノードを再計算します。各レベルで訪問する境界ノードは定数個のみであるため、更新とクエリは O(log n) であり、記憶容量は O(n) です。
代替案とトレードオフ
1点更新とプレフィックス和のみであれば、Fenwick木の方がコードが短く定数倍も小さくなります。オフラインの区間加算とそれに続く1回の最終読み取りだけであれば、差分配列の方が単純です。遅延伝播セグメント木がその複雑さに見合う価値を発揮するのは、オンラインの区間更新と区間集約が共存する場合です。区間代入を行う場合は、「代入タグが存在するか」のフラグと明示的な優先順位規則が必要です。新しい代入は古い代入と加算タグを置き換え、その後の加算は代入の後に累積されます。
障害モード、境界条件、反例
- 区間の長さを掛け忘れると、
[2, 5]への3の加算が総和を12ではなく3しか増やさなくなります。 - 完全カバー後に再帰を行うと遅延伝播が失われ、更新が重複して適用される可能性があります。
- push後にタグをクリアし忘れると、次回の訪問時に同じ加算値が再度適用されてしまいます。
- 部分更新後に親ノードを再計算しないと、その後の完全カバークエリで古い値が返されます。
- 閉区間と半開区間を混同すると、1要素のズレや
mid+1のエラーが発生します。空配列、l > r、境界におけるn=0で検証してください。
テストと検証のチェックリスト
愚直な配列をオラクルとして使用し、ランダムな更新とクエリを生成して、各操作後に比較します。1要素の区間、全体区間、両端の境界、負のデルタ、重複する範囲への更新、すべての値が等しいケースを含めます。再帰呼び出しの後に親が子の合計と等しくなっていることをアサートし、大きな入力に対して選択した整数型がオーバーフローしないことを確認します。非再帰（イテレーティブ）構成を実装する場合は、等価性テストを追加してください。
フォローアップの質問
区間代入と区間加算を共存させるにはどうすればよいですか？
ノードごとにオプションの代入タグと加算タグを保持します。新しい代入は古い代入と加算の両方を上書きし、新しい加算は代入の後に累積されます。まず代入をpushし、次に加算をpushします。この順序が正当性の規則となります。
区間最小値をサポートするにはどうすればよいですか？
総和の代わりに区間の最小値を保持します。区間加算はその最小値に依然として delta を加えるだけなので、遅延タグは単純なままです。区間 chmin や chmax をサポートするには、segment-tree beats などのより高度な不変条件が必要です。
過去の履歴バージョンを公開するにはどうすればよいですか？
永続セグメント木を使用します。更新パスに沿ったノードを複製し、変更のない部分木は共有します。各更新は約 O(log n) 個のノードを複製し、ルートポインタがバージョンを識別するため、メモリ空間は更新回数に応じて増加します。