あなたの庭に永続データ構造を飾りませんか？

2019/02/06 永続 Stack のやや丁寧な実装例を追加しました
2020/12/13 数式などを整えました

概要

あなたのライブラリに新しい彩りを与える永続データ構造の紹介です。

永続データ構造とは

永続データ構造とは、普段のデータ構造で更新をするときに更新前の状態のデータも保存しておけるデータ構造です。唐突ですが、数列 $A$ に対するクエリを処理する問題を考えてみてください。

${\tt type0}$ : $A \lbrack i \rbrack$ に $c$ を加える
${\tt type 1}$ : " $t$ 番目のクエリ直後の" $A \lbrack l \rbrack \cdots A \lbrack r \rbrack$ の和を出力

${\tt type 0}, {\tt type 1}$ のクエリを一緒にソートすればいつもの Segment Tree で解くことが出来ます。ではこれがオンラインクエリだったらどうでしょうか。これは Segment Tree では容易には解くことが出来ません。
こういった「過去の状態が必要になる」状況で永続データ構造は効率的です。

永続 Stack

具体的に、基本的なデータ構造である Stack の永続化をしてみましょう。整数を要素とする Stack は次の 3 種類のクエリを処理します。

${\tt int\ top}()$ : 先頭要素にアクセス
${\tt void\ push}({\tt int}\ x)$ : $x$ を先頭に追加
${\tt void\ pop}()$ : 先頭要素を削除

これを永続化すると以下のようになります。

${\tt int\ top}()$ : 先頭要素にアクセス
${\tt Stack\ push}({\tt int}\ x)$ : $x$ を先頭に追加した結果得られる Stack を作成
${\tt Stack\ pop}()$ : 先頭要素を削除した結果得られる Stack を作成
※ ${\tt push}, {\tt pop}$ の際、元のデータは書き換えられない

計算量を考慮しなければ、毎回 Stack の中身を全部コピーすればこれらのクエリは実現可能です。しかしよく考えると、末尾のほとんどの要素は一切変化していません。これを利用して効率的に、具体的には計算量を ${\rm O}(1)$ のままで処理できるのです！

具体的にはどうすればよいのでしょうか。一般的に Stack は配列で実装すると思いますが、実は配列は永続化と相性が悪いので単方向連結リストを使います。すると永続 Stack はリストの先頭ノードへのポインタそのものになります！各関数の処理を確認しましょう。

${\tt top}$ : ポインタから先頭ノードの値を読む
${\tt push}$ : 追加する値とポインタから新しくノードを作成し、それへのポインタを持つ Stack を作成
${\tt pop}$ : ポインタから先頭ノードを読み、次のノードへのポインタを持つ Stack を作成

以上をコードにまとめると以下のようになります。(行儀や効率やらを投げ捨てています)

#include <iostream>

struct Node {
    int value;
    Node *next;
};

struct Stack {
    Node *head;

    int top() { return head->value; }
    Stack push(int x) { return Stack({ new Node({x, head}) }); }
    Stack pop() { return Stack({ head->next }); }
};

int main() {

    Stack st0({nullptr});
    Stack st1 = st0.push(1);
    Stack st2 = st1.push(2);
    Stack st3 = st2.pop();

    std::cout << st1.top() << " " << st2.top() << " " << st3.top(); // 1 2 1

    return 0;
}