第4章 データ探索(続き)
パシステント構造
領域を分割した構造。今自分がどの領域にいるかという問題（点位置決定問題）がお手軽に解ける。
何度も同様な質問が繰り返されるときに最適っぽい。
分割格子点がn個くらいあるとすると、すべての分割格子点で縦に分割した“スラブ”を2分探索するのにO(log(n))、スラブを2分探索するのにO(log(n))なので、O(log(n))でたぶん探索できる。
問題点：
- 各スラブでデータ構造が必要：各スラブにO(n)の領域が必要になる可能性がある。スラブはO(n)個存在するので、全体でO(n^2)個の領域が必要になる可能性がある。
対策：
- 分割する代わりにスイープラインを用いて、ライン上の領域について2色木を作ることを考える。
- 要素の挿入削除はO(log(n))で行うことができる。
- 全部覚えたら一緒だけど、スイープで変化した変化分を覚えることによってデータが少なくできるかもしれない。
2色木のパシステント化
過去の情報も覚えておく2色木はどうやって作ろうか
- 変化したパスを記憶してみる。（パスコピー木）
- 新しくルートノードを作る。
- 更新されたパスの部分だけ新しくオブジェクトを作って繋げる。そのほかのところは元通り繋いどく。
- 記憶領域はn回の操作によってO(nlog(n))くらいになる。（ちょっと多い）
- パスに時刻を付けてみる。（タイムラベル木）
- ひとつのノードから異なる時刻ラベルのついているパスが沢山出る。
- 記憶領域がn回の操作によってO(n)になる
- どのパスをたどるかを探索するのにO(log(n))かかる⇒探索時間がO((logn)^2)になるという問題点がある。
- 組み合わせてみる
- タイムスロットを設けて、最初はタイムラベル木の要領でいれ、パスの上限（スロット上限）に達したらパスコピー木の要領でコピーを行う。
- ならし計算量で考えると、良いことが分かる。（そのならし計算量が意味不明）
