謎木速いけど微妙にバｇ・・・バグらないだと！？
どうもJOI夏季セミナー2012に行ってきたきゃっぱーです。きゃっとあっぱーです。
こわいひとにたくさんあえて楽しかったです（小学生並みの感想）。
遺伝的プログラミングの本を読みたかったのですが、じゃんけんでことごとく負けて
好きなテーマで本を読解して発表するというものなのですが、まず本が英語で詰んでました。
まぁ技術書なんでそこまで英語は難しくなかったのでなんとかなりますたー。
セミナー中にCodeForcesがありまして、ネット環境がなかったのでjubeat板で問題を読んで、コードはPCで組んで、Bluetoothでjubeat板に送ってsubmitしようと思ったのですがBluetooth接続で失敗して無理ですた。残念
なにより朝飯が3完でした。しかも逃したのが発表当日の最終日ということで、朝飯を抜いて午前最後の発表をするという高難易度のミッションでしたー。こんどからは目覚まし持ちあるこう。
ではでは、セミナーでやった話を具体的に。
蟻本++の中で私はvan Emde Boas treeという木構造についていろいろやりました。
この本の目次の中で唯一タイトルを見ても見当がとんとつかないものだったのでやってみました。
この木はあらゆる操作がO(log log u)でできる集合でして、すごい強者なのですが実装が重いです。
詳細についてはslideshareに上げてるスライドがあるので参照よろしくおねがいします。
なお説明の中でuとnが出てきますが、uは集合が持ちうる値の種類の数でnは集合が実際に持つ値の数です。
要素の持ち方
van Emde Boas tree(以下謎木）は集合ですので、ある要素が有るか無いかという情報を持ちます。
まずこの集合が要素として持ちうる値の種類の数だけのメモリを確保します。
たとえばint型の謎木ならば32bit分のメモリを、char型の謎木ならば8bit分のメモリを確保します。
これらのメモリはフラグとして使用し、値が有るなら1、無いなら0を格納するという感じで情報を保持します。
スライドでも出てきた平衡二分探索木はこれらを葉とするような平衡二分木を作って二分木的に操作をしています。
謎木も同じようにこれらを葉とする木なのですが、深さをlog log uにするために
サイズUの親がサイズ√Uの謎木を√U個持つ
という形をとっています。
ここで重要になってくるのは葉以外のノードがどのような情報を持つかということです。
各ノードのもつ情報
平衡二分探索木では葉以外のノードはただ一つの値を持ち、自分の子孫である葉に一つでも1があれば1,そうでなければ0という値を持ちます。
このようにするとオペレーションで再帰的に木を降りていくときに値の有無が判断でき、効率の良い枝刈りによりO(log u)ですべてのオペレーションを実現しています。
謎木でも同じように自分の子孫の葉に1が少なくとも一つあるか無いかという情報（Summary）を各ノードに持たせています。
この持ち方が実に巧妙で、平衡二分探索木ではそのノードの子孫のSummaryを持っていましたが、謎木はその子達のSummaryを持っています。
サイズUの親は√U個の子を持つので、持つSummaryの情報量は√Uになります。
ここで重要になるのが、Summaryも0,1で情報を表すビット列だという事です。
そしてサイズUの子のサイズが√Uということ。
これはつまり、各ノードのSummaryは子と同じ構造で扱うことができるという事です。
よって各親は√U + 1個のサイズ√Uの子(およびSummary）を持つことになります。
そして謎木の性質上 最も重要な情報として、そのノードの子孫の最大値と最小値を持ちます。
どうしてこれが重要なのかは後で説明しましょう。
最大値、最小値、有無のオペレーション
これは簡単です。
最大値、最小値は各ノードが持っていますのでもちろん根も持っています。それを参照するだけなのでO(1)です。
有無は、その値と対応する場所まで降りて0か1かを確認するだけなので、再帰回数は深さ分。つまりO（log log U）です。
追加
値を追加するのは情報の書き換えがあるのでややこしいです。
なによりもっとも厄介なのがこの木の情報の持ち方です。
ノードは最大値と最小値をもっているので、これを使ってその子孫の要素数が0個,1個,2個以上のどれであるかを判断できます。
最大値も最小値も無ければ0個
最大値と最小値が等しかったら1個
それいがいならば2個
です。
この木では要素を追加するとき0個から1個に増えるノードに関してはそこで再帰をやめます。なんとSummaryの更新もしません。
そして値を追加するとき、もちろん途中で通るノードのもつ最小値の情報も書き換えていくのですが、普通に更新するのではありません。
再帰の途中で最小値より小さくなったら、最小値と追加する値を交換します。それに対して最大値は交換せずに更新するだけです。いみわからん。
このような追加の仕方をすることによって謎木がどのような状態になるのかというと。
各要素はいずれかのノードの最小値である。そしてその親のSummaryはそれの有無については扱わない。またその子もその値について扱わない。
このような非対称的なやっかいな状態になります。
削除
値の削除はなお厄介です。
もっとも大変なのはSummaryの更新で、平衡二分探索木では子が2個なので再帰の帰りにSummaryを更新する時に兄弟のSummaryを見ればO(1)で0に戻すべきかそうでないかが判断できました。
しかし謎木は個の数が多いのでO(1)でSummaryを0にするべきかわかりません。
ここで役に立つのが最大値、最小値です。
Summaryを0にするのは要素数が1から0に変わるときだけです。
最大値が最小値と同じかどうかで、要素数を1かどうか判断できることができますので、O(1)でSummaryの変更の判断が可能です。
実は他にもうひとつ問題があり、最小値の削除です。
先述の通り最小値についてはそのノードの子孫はあつかっておりませんが、それ以外は扱ってますので、新しく最小値になる値をその子孫から消さないといけません。
またその親のSummaryも扱っていますからそこからも消さないといけません。
すると二回消す動作を行うので再帰呼び出し数が二個になってO(log U)になってしまうように思えます。
実はSummaryを更新するという事はそこに対応する子は値を一つしか持ってなかったことになります。つまりそちらの再帰の深さは1です。よって呼び出しを二回しても、片方はO(1)でおわるので結果的に処理数は深さ分になります。
O(log log u)
です。
Successor
これは与えられた値より大きい要素の中で最小のものを返す関数です。
最大値最小値は各ノードが持ってますのでこれをうまく使えば単純な操作だけで実現できそうです。
具体的には普通にその値に対応する葉の方向に降りて行って、とちゅうでその値が最小値よりも小さくなったらその最小値が返すべき値です。
もしも最大値よりも大きくなってしまったら、その親の「次の兄弟」の最小値が返すべき値です。「次の兄弟」というのはSummaryにおいてSuccessorを使うことによって得ることができるので結果的に処理数は深さ分になります。
O(log log u)
です。
Predecessor
こちらはSuccessorの逆で与えられた値より小さい要素の中で最大のものを返す関数で、次ソスはSuccessorの逆なので割愛します。
空間計算量
さて、データー構造は速けりゃいいってもんじゃない。メモリを沢山食っては動きません。
この謎木は普通に考えると葉の数だけメモリが必要ですので空間計算量O(u)になりそうです。long long int型ならば2**64のメモリが必要ですが、さすがに扱えません。
しかしInsertの動きをよくみてみると、各要素はいずれかのノードの最小値になっています。そして最小値はそのノード以外で扱わないので、結果的に情報を持つノードは要素数を超えません。よって、子を動的に確保していけば空間計算量は要素数分 つまりO(n)までおさえることができます。
よってヒープと同じ空間計算量でオペレーションはO(log log u)でできる謎な木が出来上がりましたー。 やったぜー。
実装
まぁ実装が重いです。 C++で組めるもんなら組んでみれば良い。
私はpythonで組みました。
URL:https://gist.github.com/3505897
こんど機会があったらC++で実装してみたいと思います。
