Competitive Programming Advent Calendar 2014 23日目かんたん！永続化！

この記事は Competitive Programming Advent Calendar 2014 のために執筆されました。

想定読者：データ構造を知っている人，ポインタを把握している人

今回は，巷ではアレルギー反応を起こし，よくわからないという印象のまま過ごしている人が多く見受けられる，永続データ構造の基本的なところについて取り扱いたいと思います．

データ構造の永続化については，アイデアとして全然難しいとは思わないのですが，どうやらピンときてない人が多いみたいです．

この記事はC++で書かれていますが，あまり言語は重用でない気もするので適当に読み進めて下さい．

永続化を使うとどういうメリットがある？

・リアルタイムクエリーに簡単に対応できるようになる

・データ構造の大部分がどこかの部分からのコピーである場合に，コピー部分をうまく取り扱って省メモリ化・高速化できる

さて，永続化に適したデータ構造なのですが，変更が加わるノードが少ないデータ構造(例えば各操作の参照するノード数がO(log n)である平衡二分木やヒープ)は適しています．逆に単純なリスト等は適していません．

ただ，ならし解析で良い速度を実現するアルゴリズム(スプレー木，O(α^-1(n))のUnionFind等)とか，乱数の一様性を利用したデータ構造(Treap等)は，計算量が永続化によって変わってしまいます．

多分O(log n)のUnionFindは永続化できます．

では，実際にデータ構造を永続化していくアイデアを説明していきます．

基本的なポリシーは，「あらゆる操作(参照・削除・挿入)時，過去に生成された全てのノードはconstであるという条件下での操作を行う」です．

例)リストの永続化

　先ほど適していない，とは言いましたが，参照するノード数が少ない場合は早く動きます．

例えばスタックやキューを双方向リストを利用して実装した場合，一回の操作で参照するノードはO(1)個なので，永続化できます．

　ちなみに，平方分割リストとかも参照するノード数が減るので永続化できると言っても良いのですが，省略します．

今回は，説明のためなので，単方向リストを永続化してみます．

それではさっそく実装していきます．まずは永続化なしの場合から．

実装の都合上，というか永続化すると，データ構造で最初に参照する場所(根ノードとか先頭ノードとか)はどこになんねんという問題がありますし，永続化する際大変便利なので，あるノードを計算した後，自身を返す再帰関数を実装しておきます．

#define NULL (0)
// 0-indexed

struct NODE{
	char val;
	NODE *next;
};
NODE *insert(NODE *node,int position,char value){
	if( position == 0 ){
		NODE *newNode = new NODE();
		newNode->val = value;
		newNode->next = node;
		return newNode;
	}else{
		node->next = insert(node->next,position-1,value);
		return node;
	}
}
int main(){
	NODE *head = NULL;
	head = insert(head,0,'a');
	head = insert(head,1,'b');
	head = insert(head,2,'c');
	head = insert(head,3,'d');
	head = insert(head,4,'e');
}

以上のような実装をすると，以下のようなリストが出来上がることは分かると思います．

それでは，こうしてできたリストに対して，永続化に対応したinsert，ここでは一例として

head = insert(head,2,'f');

みたいな感じの挿入を行うことを考え，そのための関数immutable_insert()[※insertと永続化対応以外同等]を実装していきます．

ポリシーである，過去に生成されたノードはconstであるという条件を忘れずにやっていきます．まず，とりあえず関数の引数をconstにしちゃいます．

NODE *immutable_insert(const NODE *node,int position,char value){
	if( position == 0 ){
		NODE *newNode = new NODE();
		newNode->val = value;
		newNode->next = node; //こことか
		return newNode;
	}else{
		node->next = immutable_insert(node->next,position-1,value); //こことか
		return node;
	}
}

コメントの部分でコンパイルエラーが出ます．そこで，

NODE *immutable_insert(const NODE *node,int position,char value){
	//参照したノードは複製する
	NODE *copyNode = new NODE();
	copyNode->val = node->val;
	copyNode->next = node->next;

	if( position == 0 ){
		NODE *newNode = new NODE();
		newNode->val = value;
		newNode->next = copyNode;
		return newNode;
	}else{
		copyNode->next = immutable_insert(node->next,position-1,value);
		return copyNode;
	}
}

やったことは，const回避のためにnodeと全く同じなcopyNodeを複製しただけです．コピーは適当に関数とか実装して良いと思います．

このimmutable_insert()関数を用いて挿入操作

NODE *head2 = immutable_insert(head,2,'f');

を行うと，以下のような感じになります．

(番号はわかりやすさのために勝手に振ってるだけです

なんでhead2に代入してるのかっていうと，更新したとき根の部分をどっかに保持しとかないとせっかく永続化したのに行方不明になっちゃうからです．別に用途によっては先頭とか必要ない場合も有るし，必要に応じてください．

さてさて，お次は木構造の永続化です．

平衡二分木は永続化でない部分が最高に面倒くさいので，今回は遅延評価付きセグメントツリーの永続化についてやっちゃいます．

(工事中たぶんちょっとしたらできます)

[追記]

思ったより本質でない部分でコードが複雑化していて時間がかかりそう