アルゴリズム・データ構造図鑑 · 基礎から応用へ

経路をコピーして版を残すセグメント木

一点更新の経路だけを新しく作り、三つの版の区間和、共有する参照、古い版の回収条件を追います。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 更新前の配列も使い続ける
  2. 区間を半分に分けて合計を持つ
  3. 経路だけをコピーする
  4. 三つの版の全区間を照合する
  5. 時間と追加ノードを数える
  6. 任意の旧版から更新する意味
  7. 集約の演算を変える前に確認する
  8. 共有する部分を示す課題
  9. この記事をロゲイアに質問する理解を確かめる

更新前の配列も使い続ける

配列1〜8の区間和を答えながら、一部の値を変更した複数の版を保存します。最初の版v0の合計は36です。位置2の3を30へ変えたv1は63、さらに位置7の8を80へ変えたv2は135になります。v2を作った後でも、v0へ問い合わせれば36を返してほしい、という要件です。配列全体を毎回コピーする方法なら実現できますが、一回の更新にn要素分の複製が必要になります。

永続セグメント木は、更新で変わる葉までの経路だけを新しく作り、変わらない部分木を旧版と共有します。ここでいう永続は、昔の版をプログラム内で利用できる性質です。電源を切っても保存されるストレージの永続性や、DBトランザクションの耐久性とは別の意味です。ファイルへ保存しない今回のコードは、プロセスを終了すれば木も失われます。

区間を半分に分けて合計を持つ

各ノードは半開区間[lo,hi)の合計を持ちます。根は[0,8)、その子は[0,4)と[4,8)です。長さ1になった葉に配列の値を保存します。区間[2,6)の和なら、問い合わせ区間に完全に含まれる部分木の合計を使い、外側の部分木は0として無視します。境界をまたぐノードだけ、左右へ降りて合計します。全ての葉を毎回足し直す必要はありません。

掲載例ではノードを合計と左右の子からなるtupleで表します。既存tupleの内容を書き換える操作を用意しないため、新しい版から旧ノードを壊しにくい構造です。ただし、tupleの中へ可変のリストやオブジェクトを置いた場合まで、自動的に深い不変性が得られるわけではありません。今回の葉は整数、内部参照も同じ規則のtupleへ限定します。値と参照の両方の更新方法が、版の分離へ関わります。

経路だけをコピーする

位置2を変える場合、[0,8)、[0,4)、[2,4)、[2,3)の経路を新しく作ります。右側の[4,8)は変化しないので、v0とv1が全く同じ部分木を参照します。新しい葉から戻りながら、左右の合計を新しい親へ計算します。旧版の親の子参照を書き換えてはいけません。根の参照を一つ保存すれば、その版全体へ到達できます。

次にv1の位置7を変えると、新しい経路は右側になります。v1とv2は左側を共有できます。共有は同じ値をたまたま持つコピーではなく、同じノードへの参照です。付属のassertはisで共有された部分木を確認します。正しい合計が出るだけでは、毎回全コピーする実装と経路コピーの実装を区別できないためです。意味上の正しさと、共有する構造の性質を別々に検査します。

版更新根の合計新ノード前版と共有する部分
v01〜8で構築3615なし
v1位置2を3→30634[4,8)全体。左側でも更新経路外を共有
v2位置7を8→801354[0,4)全体。右側でも更新経路外を共有

三つの版の全区間を照合する

コードは8要素の配列から木を構築し、二回の更新で三つの根を保存します。各版で開始位置0〜8と、その位置以上の終了位置を組み合わせ、45区間の和を通常のsumと比べます。空区間も含むため、その答えが0になることも確認できます。三版で計135区間です。元配列のコピーへ同じ変更を適用した参照値を用意し、旧版が後の更新で変わっていないことを検査します。

この小実装は空でない固定長配列を構築し、問い合わせは0≤start≤end≤nの範囲で使います。changeは更新位置が担当区間へ入るかを検査します。一般のAPIにするなら、空の初期配列、範囲外の問い合わせ、型の違い、保持する版の上限も入口で扱います。コード中の再帰の仕組みを理解する目的と、外部入力を受ける完成したライブラリの契約は分けて考えてください。

python
def build(a,lo,hi):
    if hi-lo==1:return (a[lo],None,None)
    mid=(lo+hi)//2;left=build(a,lo,mid);right=build(a,mid,hi)
    return (left[0]+right[0],left,right)
def change(node,lo,hi,index,value):
    if not lo<=index<hi:raise IndexError(index)
    if hi-lo==1:return (value,None,None)
    mid=(lo+hi)//2;left,right=node[1:]
    if index<mid:left=change(left,lo,mid,index,value)
    else:right=change(right,mid,hi,index,value)
    return (left[0]+right[0],left,right)
def query(node,lo,hi,start,end):
    if end<=lo or hi<=start:return 0
    if start<=lo and hi<=end:return node[0]
    mid=(lo+hi)//2
    return query(node[1],lo,mid,start,end)+query(node[2],mid,hi,start,end)
a=list(range(1,9));v0=build(a,0,8);v1=change(v0,0,8,2,30);v2=change(v1,0,8,7,80)
assert v0[2] is v1[2] and v1[1] is v2[1]
for root,values in [(v0,a),(v1,a[:2]+[30]+a[3:]),(v2,a[:2]+[30]+a[3:7]+[80])]:
    for start in range(9):
        for end in range(start,9):assert query(root,0,8,start,end)==sum(values[start:end])
assert [v[0] for v in [v0,v1,v2]]==[36,63,135]
print('3 versions; totals=36,63,135; all135 intervals passed')

時間と追加ノードを数える

平衡に区間を二分した木では、高さはO(log n)です。一点の更新で作るノードは根から葉までの一経路なのでO(log n)、初期構築はO(n)です。k回の更新を全て保持する場合、論理的なノード数はO(n+k log n)になります。区間和の問い合わせも境界に沿って分解され、通常O(log n)で答えられます。合計値の加算が定数時間であるという計算モデルを前提にしています。

版の根を全て保存すれば、共有していてもメモリ使用量は増え続けます。古い根を捨てると、その根からしか到達できなかったノードは回収できる候補になりますが、別の版が共有するノードはまだ必要です。参照カウントやGCなど、使用言語の寿命管理へ従います。共有部分を一括で解放すると新しい版まで壊す危険があり、経路コピーによる省領域と回収の設計を一緒に検討します。

任意の旧版から更新する意味

今回のコードはv0からv1、v1からv2を作りますが、changeへv0を再び渡せば、v1とは別の枝の版を作れます。過去の版を読むだけでなく更新の出発点にもできるため、根の履歴は一本の線でなく分岐を持てます。二つの枝を自動で合流する操作は提供していません。差分をまとめるには、どちらの変更を採用するかという別の契約が必要です。

履歴があることは、トランザクションの衝突検出やアクセス制御の代わりにもなりません。同じ旧版から二人が注文数を変更して別の根を作れても、どちらを現在の公開版とするかはアプリが決めます。学習では配列の版という狭い意味へ留め、DBのMVCCやファイルのスナップショットと比べる場合も、何を共有し、誰が根を保持し、何が永続化されるかを列として分けます。

集約の演算を変える前に確認する

区間和の0は、要素を含まない区間を合わせるときの単位元です。区間最小値へ変えるなら、範囲外で返す値を0のままにすると、全要素が正の場合に誤った最小値を作ります。演算と単位元を組で選び、親の集計と問い合わせの合成を同じ規則へ変えます。

一点更新の経路コピーという形は再利用できても、区間への一括加算を同じコードへ足すだけでは済みません。遅延更新の印を共有ノードへ書き込むと旧版まで変える危険があります。共有する構造へ可変の状態を加える際は、どのノードをコピーし、どこで印を伝播するかを新しく設計する必要があります。

共有する部分を示す課題

課題は、v0の配列1〜8から位置0を10へ変えた版を作り、新しいノードと共有する部分を示すことです。解答では[0,8)、[0,4)、[0,2)、[0,1)の四ノードを新しく作ります。根の右側[4,8)に加え、経路の反対側にある[2,4)と[1,2)も旧版と共有します。新しい合計は45、旧版は36のままです。経路上のノードだけを描き直してください。

追加課題では、その新しい根への参照を捨て、v0だけを保持します。新しい版だけが使っていた四ノードは回収できる候補ですが、v0の共有部分は残す必要があります。逆にv0を捨てても、新しい版が共有する旧ノードは残ります。合計の変化だけでなく、どの根からどのノードへ到達できるかを説明することで、版を残す便利さと領域管理の費用を同時に理解できます。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 9

学習コースから次を選ぶ