永続的なカットツリー

はじめに

データ構造は、 一時 （ 一時 ）と永続 （ 永続 ）の2つのグループに分けることができます。



エフェメラルは、最新バージョンのみを保存するデータ構造です。

永続構造、つまり以前のバージョンをすべて保持する構造は、2つのサブグループに分けることができます：データ構造で最新バージョンのみを変更できる場合、 部分永続と呼ばれますが、バージョンの変更が許可されている場合、そのような構造は完全に永続的と考えられます。



次に、セグメントのツリーとその完全に永続的なバージョンが考慮されます。

すべてのコードはGitHubで入手できます 。

ラインツリー

セグメントのツリーにすでに精通している人は、 永続バージョンのセクションにすぐに行くことができます。



セグメントツリーは、特定の配列A



に対して次の操作をすばやく実行できるデータ構造です。

• Change(i, x)



A[i]
  
  
  
  値をChange(i, x)
  
  
  
  変更します
• F(i, j)



f(A[i], A[i + 1], ..., A[j])
  
  
  
  計算f(A[i], A[i + 1], ..., A[j])
  
  
  
  

両方の操作はO（log n）で実行されます。 f



関数としてf



しばしば合計、最小、または最大を取ります。

説明

n



を配列A



長さとすると、その長さが2の累乗に等しくなるまで中立要素で埋めます（たとえば、 f



が合計の場合、配列はゼロで補われます）。



ここで、 A



すべての要素が葉であり、すべての葉の深さが同じで、子頂点の値からのf



値が他のすべての頂点に格納されるようなバイナリツリーを構築します。



例として、配列A = [4, 1, 4, 2, 5, 3]



4、1、4、2、5、3]のセグメントツリーを考えA = [4, 1, 4, 2, 5, 3]



。





このようなツリーをバイナリヒープとして保存すると便利です。頂点の配列として、上から下へ左から右へと連続して記述されます。

  19 11 8 5 6 8 0 4 1 4 2 5 3 0 0 

この場合、インデックスi



頂点の場合、その祖先は頂点((i - 1) / 2)



になり、左右の子頂点にはそれぞれインデックス(2 * i + 1)



と(2 * i + 2)



割り当てられます（仮定）配列内の要素には最初から番号が付けられていること）。

建物

セグメントのツリーを上から下に再帰的に構築すると便利です。各頂点について、左右の子頂点を構築し、その値からf



の値を計算します。シートの場合、対応する配列値をツリーに書き込むだけです。



このような方法でツリーを構築すると、各頂点が1回訪問されます。また、ツリー内の頂点の数はΘ（n）であるため、構築の複雑さもΘ（n）です。

変更

要素の値が変更された後、この要素の祖先の値の一部がツリー内で劣化した可能性があります。 これを修正するには、この要素の祖先の値を再カウントし、ツリーを下から上に登っていきます。



たとえば、配列A



A[3]



を10



に置き換えると、値6、11 11



および19



の頂点が再計算されます。



ツリーの高さはlog nであるため、変更操作は正確にlog nの頂点に影響を与えるため、操作の漸近的な動作はO（log n）です。

Fの計算

この操作は、上から下に再帰的に実行されます。



任意の頂点v



F



範囲l..r



に対して計算されると仮定すると、 l..((l + r) / 2)



の値F



l..((l + r) / 2)



左ドーター頂点で計算され、 ((l + r) / 2 + 1)..r



。



要求F(i, j)



到着し、現在の頂点がv



ます。 次の2つのケースが考えられます。

• ノードv
  
  
  
  では、値F(i, j)
  
  
  
  はすでに計算されています。 その場合、要求に対する答えは頂点v
  
  
  
  値になります。
• ノードv
  
  
  
  では、 F
  
  
  
  より大きな範囲に対して書き込まれます。 この場合、左の子頂点に対して計算F(i, (l + r) / 2)
  
  
  
  を呼び出し、右の子頂点に対してF((l + r) / 2 + 1, j)
  
  
  
  を再帰的に呼び出します。答えはこれら2つの値からfです。

例

C ++での行ツリーの実装 。

永続的な回線ツリー

永続化はさまざまな方法で実現できますが、最も簡単なのは古いバージョンの完全なコピーを作成し、変更ごとにセグメントの通常のツリーのように変更することです。ただし、この方法はメモリを大量に消費し、 Change



操作の漸近的な動作をO（n）に悪化させます。

建物

セグメントの永続的なツリーの構築は、セグメントの通常のツリーの構築に似ていますが、各頂点に対して、子頂点への参照を明示的に保存する必要がある点が異なります。

さらに、対応するバージョンのツリーのルートである頂点の配列を保存する必要があります。 構築時に、単一の頂点が追加されます。これは、結果のツリーのルートです。







セグメントの一時的なツリーと比較した場合の唯一の変更は、左右の子頂点に関する情報の追加であるため、構造の複雑さは変わらず、つまりΘ（n）です。

変更

頂点を変更するときにツリーを完全にコピーする代わりに、変更されるはずの頂点のみが追加され、古い頂点の値を変更する代わりに、再計算された値が新しいものに保存されます。 すべての新しい頂点は、古いバージョンツリーの1つの頂点と、追加したばかりの頂点の1つを参照します。



新しいブランチの追加は、ツリー全体の構築と同じ方法で行われますが、2つの子頂点を構築する代わりに、変更された頂点が存在する方向にのみ新しい頂点が構築されます。

その後、ルート頂点の配列が更新されます。







変更ではlog nの頂点のみが追加されるため、操作の漸近的な動作はO（log n）です。

Fの計算

Fの計算は、一時的なツリーに似ています。 唯一の違いは、子ノードへの移行と異なるルートノードからの起動です。

これは、O（log n）の複雑さを意味します。

例

C ++でのセグメントの永続的なツリーの実装 。

タスク

セグメントの永続的なツリーを使用して、「 ロールバック 」 タスクを解決できます （ タスク解析 ）。 セグメントの永続的なツリーの上記の実装を使用した問題の解決策は、 GitHubで利用できます 。

また、範囲に関するk番目の順序統計の問題の説明を読むことができます。