週刊 spaghetti_source

できるだけ毎週土曜日更新．次回更新は2月16日．
ネタ切れ深刻なので記事リクエスト募集中．twitterないしはコメント欄まで．
貼っているコードはあんまり検証していないので，信頼性はアレです．アレ．
twitter: @tmaehara フォローはお気軽に．

2012-09-15

Knuth-Yao speedup

09:16

今回と次回は「動的計画法を加速する」タイプの話題を取り上げます．キーワードはMonge性（モンジュとよむ，人名）です．

長いので，ちゃんと読むつもりの人は覚悟してください．理屈はいいからコード出せという人は半分強くらいスクロールGO．末尾に２つ演習問題もあるよ．

全体的な導入

二変数の関数f(i,j)が「Monge」であるとは，任意の i ≦ j と k ≦ l について

　　f(i,l) + f(j,k) ≧ f(i,k) + f(j,l)

が成立することをいいます．f(i,j) が i ≦ j についてのみ定義されている場合を「上三角Monge」などといいますが，ここでは特に区別しません．この手の不等号の向きは忘れがちですが，Monge性はmin-max束の劣モジュラ不等式だと思うと忘れません：

　f(i,l) + f(j,k) ≧ f(min{i,j},min{k,l}) + f(max{i,j},max{i,k}) = f(i,k) + f(j,l)

余談１：劣モジュラなどの不等号の向きは「左にf(X)+f(Y)と書いてから，余計なことをすると減る，と思って右辺f(X∩Y)+f(X∪Y)を書く」と覚えます．数学の劣と優は，だいたいこの流儀に則っているはずです．

余談２：Monge性は分野ごとにいろんな名前で呼ばれており，有名ドコロだけでも distribution matrix (Gilmore), concave quadrangle inequality (Yaoなど), concave function (Larmore-Schieberなど) が知られていて，大変ややこしいのが現状です．論文とかなら文脈に応じて選ぶ用語ですが，ここではMongeで統一します．

Monge性があると簡単に解ける問題は様々ありますが，ここではすごく大雑把に列挙します．ポインタも示しますので，琴線に響くものがあれば参照してください．

二部グラフマッチングの枝コストが Monge のとき，貪欲解が最適解になる

[1] A. J. Hoffman: "On simple linear programming problems", Convexity: Proceedings of the Seventh Symposium in Pure Mathematics, Proceedings of Symposia in Pure Mathematics (V. Klee, ed.), Vol. 7. American Mathematical Society, Providence, RI, 317-327, 1963.
[2] M. Queyranne, F. Spieksma, and F. Tardella: "A general class of greedily solvable linear programs", Mathematics of Opeartional Research, Vol.23, No.4, 1998.

f(i,j) がMongeのとき，「各 i について最小を与える j」を全部求めるのは O(n) で計算可能

[3] A. Aggarwal, M. M. Klawe, S. Moran, P. Shor, and R. Wilber: "Geometric applications of a matrix-searching algorithm", Algorithmica, Vol.2, pp.195-208, 1987.
[4] L. L. Larmore and B. Schieber: "On-line dynamic programming with applications to the prediction of RNA secondary structure" Journal on Algorithms, Vol.12, pp.490-515, 1991.

X(i) = min_{j<i} { X(j) + w(i,j) } 型のDPは，wがMongeなら O(n) で計算可能

X(i,d) = min_{j<i} { X(j,d-1) + w(i,j) } 型のDPは，wがMongeなら O(nd) で計算可能

[5] D. Eppstein, Z. Galil, and R. Giancalco: "Speeding up Dynamic Programming", 29th IEEE Symposium on Foundations of Computer Science, White Plains, New York, pp. 488-496, 1988.
[6] A. Bar-Noy, M. J. Golin, and Y. Zhang: "Online Dynamic Programming Speedups", Theory of Computing Systems, Vol.45, No.33, pp.429-445, 2009.

X(i,j) = min_{i≦s<j} { X(i,s) + X(s+1,j) } + w(i,j) 型のDPは，wがMongeかつ単調なら O(n^2) で計算可能．

[7] D. E. Knuth: "Optimum binary search trees", Acta Infomatica, Vol.1, pp.14-25, 1971.
[8] F. F> Yao: "Efficient dynamic programming using quadrangle inequalities", Proceedings of 12th Annual ACM Symposium on Theory of Computing, pp.429-435, 1980.

X(i,j,p) = min_{i≦s<j} { X(i,s,p) + X(s+1,j,p-1) } + w(i,j) 型のDPは，wがMongeかつ単調なら O(n^2 p) で計算可能

[9] A. Borchers and P. Gupta: "Extending the quadrangle inequality to speed-up dynamic programming", Information Processing Letters 49, pp.287-290, 1994.

その他，Monge性に関する全体的なサーベイは以下を参考にするのが良いと思います（DPの話題は少ないですが……）．

[10] R. E. Burkard, B. Klinz, and R. Rudolf: "Perspective of monge properties in optimization", Discrete Applied Mathematics, Vol. 70, No. 2, pp.95-161, 1996.

今回は[8]で提案されたテクニックを紹介します．このテクニックは「Knuth-Yao speedup」という名前で知られているもので，「Mongeだと早く解ける」の最も基本的な例です．

Knuth-Yao speedup

Knuth-Yao speedupは，「O(n^3) DP が O(n^2) に落ちる」型の加速です．元々は最適二分探索木問題に対してKnuthが提案した手法[7]を，Monge性が鍵であるとYao[8]が見抜いた，という歴史的な経緯になっています．最適二分探索木の加速についてはCormen-Leiserson-Rivest-SteinのアルゴリズムイントロダクションのDPの章の演習に出ているので，知っている人も多いかと思います．

Knuth-Yao speedupのテクニックは，以下の3つの命題から構成されています．

命題１．畳込みのspeedup

２変数関数 f, g について，その畳込みが

　　(f*g)(i,j) := min_{i≦s<j} { f(i,s) + g(s+1,j) }

で定義される．このとき，f, g がMongeのとき，(f*g)もMongeとなる．さらに，K(i,j) を右辺の min を達成する s とする．すなわち

　　K(i,j) := argmin { f(i,s) + g(s+1,j) }

とする（最大値が複数ある場合は一番右をとる）．このとき K(i,j) は単調増加する：

　　K(i,j) ≦ K(i,j+1) ≦ K(i+1,j+1)

命題２．Monge性の遺伝

　　X(i,j) = min_{i≦s<j} { X(i,s) + X(s+1,j) } + w(i,j)

で定まる X は，重み関数 w が次の２つの条件をみたすときMonge．

w(i,j) はMonge
w(i,j) は単調，すなわち w(i,j) ≦ w(k,l)　if　[i,j] ⊆ [k,l]

命題３．Knuth-Yao speedup

　　X(i,j) = min { X(i,s) + X(s+1,j) } + w(i,j)

型のDPは，命題２の条件をみたすとき O(n^2) で解ける．

Knuth-Yao speedup の O(n^2) というのは，X(i,j), X(i+1,j+1) が計算されているとき，X(i,j+1) を計算するには K の単調性から s の走る範囲を限定できる，というロジックです（上のDPのテーブルを対角線から順番に右上に埋めていくイメージ）．具体的にコードを見たほうがこの界隈の人は理解しやすいと思うので，後ろの例題に対するコードを参考にしてください．

以下命題１，２の証明を行います．たいして難しくないので自分で紙に書くとすぐに理解できると思います．３は１，２の系です．

命題１の証明

Mongeになることは省略（2の証明と全く同じ）．

K(i,j) = s, K(i,j+1) = t として (f*g)(i,j) + (f*g)(i,j+1) を書くと

　　(f*g)(i,j) + (f*g)(i,j+1) = f(i,s) + f(i,t) + g(s+1,j) + g(t+1,j+1)

となり，Monge性を使うと

　　≧ f(i,min{s,t}) + f(i,max{s,t}) + g(min{s,t}+1,j) + g(max{s,t}+1,j+1)

となるが，右辺の形が (f*g)(i,j) + (f*g)(i,j+1) の min の内側の項の形をしているので，左辺が最小であることより min{s,t} も (f*g)(i,j) を達成し，max{s,t} も (f*g)(i,j+1) を達成することがわかる．いま t はそのようなものの中で一番右側にとったので max{s,t} ≦ t，したがって s ≦ t．K(i+1,j) 側も同様に示される．

命題２の証明

|i-l| のサイズに関する帰納法で，いまの |i-l| より小さいところでは成り立っているとする．このとき，

　　X(i,l) = X(i,s) + X(s+1,l) + w(i,l), 　X(j,k) = X(i,t) + X(t+1,k) + w(j,k)

と書いて足し合わせ，Monge性を縦ごとに使うと（サイズが小さい区間に関するMongeなので帰納法が適用可能）

　　X(i,l)+X(j,k) ≧ X(i,min{s,t}) + X(i,max{s,t}) + X(min{s,t}+1,k) + X(max{s,t}+1,l) + w(i,k) + w(j,l)

右辺は X(i,k) + X(j,l) のminの中身の形をしているので，minが走ると，もっと小さくなる：

　　X(i,l)+X(j,k) ≧ X(i,k) + X(j,l)

注：Yaoの論文では，1,2の証明を i,j,k,l と s,t の位置関係の場合分けでゴリゴリやっていますが，こちらの証明のほうがはるかにシンプルだし，分かりよいと思います．この手の最小元の和に劣モジュラ性を使って何かを言うタイプの証明は，劣モジュラ業界では標準的です．

ここまで一般論でした．以下では具体例でどのように Knuth-Yao speedup を使うかを説明します．

適用例：最適二分探索木問題

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1245

0 < 1 < ... < n-1 を要素としてもつ二分探索木を構成したい．各キー j にアクセスする頻度 f(j) が与えられるので，コスト：Σdepth(j)×f(j) が最小となるような二分探索木を求めよ（コストのみ）

＃扱いやすいように，根の深さを 1 とします（このほうがKnuth-Yao的に説明が楽なので）．最終的に得られた解を根の深さ 0 に修正するためには，Σf(j) を引いてやればいけます．

この問題に対する素直なDPは，i, .., j-1 を要素とする二分探索木のコストを X(i,j) と定義して，どれを根にするかで min を取る，すなわち

　　X(i,j) = min { X(i,s) + X(s+1,j) } + w(i,j), 　X(i,i) = 0

だと思います．ここでw(i,j)は根を通る頻度で w(i,j) := f(i) + ... + f(j-1) です，最終的に求めたいものは X(0,n) です．このDPはそのままだと O(n^3) ですが，重み関数が Monge なのが自明（不等式でなく等式で成立）なので，Knuth-Yao speedup が使えて，O(n^2) で解けます．

以下に speedup を適用したものと，speedup を適用しないもののソースコードを示します．書き換わった部分に注目すると，Knuth-Yao speedup の使い方がわかるかと思います．

O(n^3)解：Knuth-Yao speedup適用前

// 21 lines
int optimalBST(int a[], int n) {
  static int W[MAXSIZE][MAXSIZE];
  static int X[MAXSIZE][MAXSIZE];
  for (int i = 0; i < n; ++i) {
    W[i][i] = 0;
    for (int j = i; j < n; ++j) 
      W[i][j+1] = W[i][j] + a[j];
  }
  for (int i = 0; i <= n; ++i) {
    for (int j = 0; j <= n; ++j) 
      X[i][j] = 99999999;
    X[i][i] = 0;
  }
  for (int w = 1; w <= n; ++w) 
    for (int i = 0, j; (j = i+w) <= n; ++i) 
      for (int r = i; r+1 <= j; ++r) {
        int c = X[i][r] + X[r+1][j] + W[i][j];
        if (X[i][j] > c) X[i][j] = c;
      }
  return X[0][n];
}

O(n^2)解：Knuth-Yao speedup適用後

// 23 lines
int optimalBST_KY(int a[], int n) {
  static int W[MAXSIZE][MAXSIZE];
  static int X[MAXSIZE][MAXSIZE];
  static int K[MAXSIZE][MAXSIZE]; // +
  for (int i = 0; i < n; ++i) {
    W[i][i] = 0;
    for (int j = i; j < n; ++j) 
      W[i][j+1] = W[i][j] + a[j];
  }
  for (int i = 0; i <= n; ++i) {
    for (int j = 0; j <= n; ++j)
      X[i][j] = 99999999;
    X[i][i] = 0;
    K[i][i] = i; // +
  }
  for (int w = 1; w <= n; ++w) 
    for (int i = 0, j; (j = i+w) <= n; ++i) 
      for (int r = K[i][j-1]; r <= K[i+1][j]; ++r) { // c
        int c = X[i][r] + X[r+1][j] + W[i][j]; 
        if (X[i][j] > c) { X[i][j] = c; K[i][j] = r; } // c
      }
  return X[0][n];
}

課題：連鎖集合積問題

集合 S1, ..., Sn が与えられ，これらの直積 S1×...×Sn を計算することを考えます．集合の直積 S1×S2 を行うには計算コストが |S1|×|S2| かかるとすると（全要素対の数），直積計算のカッコのつけかた次第で計算コストに違いが発生します．

各集合のサイズ |S1|, ..., |Sn| が与えられたときの最適計算コストを求めなさい．

連鎖行列積問題のバリエーションですが，コスト関数が違うので Knuth-Yao speedup が適用できます（Monge性の証明にはa,b>1のとき(a-1)(b-1)≧ 0を使います）．逆に，連鎖行列積問題には Knuth-Yao speedup が適用できないことは重要です．

ちなみにYao[8]のモチベーションとして連鎖行列積はあったようですが，うまくいかないという結論でした．その4年後に Hu-Shing(1984) が連鎖行列積 O(n log n) を証明しています．ちなみに自分は未だにHu-Shingは理解できていません．長すぎる上に読みにくいですわアレ．

発展課題：一般化ハノイの塔

「ハノイの塔」の問題を，次のように一般化します．

柱は「開始の柱」と「終了の柱」と「自由に使って良い柱×p」の合計 p+2 本．普通のハノイは p = 1．

各ディスクを移動させるのにかかる時間 t1, ..., tn が決まっている．通常のハノイは tj = 1

このときに，すべてのディスクを開始の柱から終了の柱に動かすまでの最短時間を求めなさい．

この問題は，ナイーブなDPで O(n^3 p) で解けますが，実は Knuth-Yao speedup の拡張版が適用できて，O(n^2 p) で解けます[9]．厳密な証明はさておき O(n^3 p) のDPを書いてみて，適当に弄って O(n^2 p) にしても解けていることを確認すると，なかなか楽しいかと思います．

ちなみに柱の数が一般で，tj=1のケースについては，Frame-Stewartのアルゴリズムというものが最適だと予想されています（問題がとっつきやすいので，正しいと「証明」した論文がいくつもあるけれど，いずれもミスがあったりするので，きっと現在でもOpen Problem）．

来週も同じ系統の話題を扱います．

コメントを書く

spaghetti_source2012/09/24 08:23１つだけ補足：記事ではMongeは min-max 束の劣モジュラだと説明したけれど，f(i,j) = f([i,j]) という区間の関数の優モジュラという見方もできます（cf. https://topcoder-g-hatena-ne-jp.jag-icpc.org/iwiwi/20120701/1341149838）．
ただ，上の論文の結果の幾つかが min-max 束の劣モジュラ性の直接的な帰結だったりするので（例：「Monge → 貪欲が最適解」は，ポリマトロイド上の貪欲法だから），自分の認識では，劣モと思うほうが自然だろうと思っています．

Thomastub2018/04/27 03:34cialis side effects sore legs
<a href="http://lzdwqokfs.com/">cialis 5mg price in india</a>
cialis soft tabs online
<a href="http://lzdwqokfs.com/">cialis 5 mg daily price</a>
cialis 5mg tablets bedwetting
http://lzdwqokfs.com/
price comparison for cialis 20 mg

JeffreyRenia2018/04/28 00:41viagra and cialis dosage strength comparison
<a href="http://lzqwqokfs.com/">viagra cost vs cialis cost</a>
cialis professional 40 mg reviews
<a href="http://lzqwqokfs.com/">prices for cialis 5mg</a>
safe sites for generic cialis
http://lzqwqokfs.com/
cialis maximum dosage per week

JeffreyRenia2018/04/28 00:52daily 5mg cialis prices
<a href="http://wzqwqzkfs.com/">cialis 5 mg coupon lilly</a>
cialis prices in usa
<a href="http://wzqwqzkfs.com/">cialis dosing options</a>
cialis dosage chart
http://wzqwqzkfs.com/
hearing loss cialis 5 mg dose

Payday Express 2018/10/14 04:15credit loans guaranteed approval <a href="https://creditloansguaranteedapproval.com/">payday loan california</a> legit payday loans online <a href=https://creditloansguaranteedapproval.com/>poor credit loans guaranteed approval</a>

izizoojocaxaw2019/06/08 11:21http://mewkid.net/buy-amoxicillin/ - Buy Amoxicillin Online <a href="http://mewkid.net/buy-amoxicillin/">Amoxicillin 500mg Capsules</a> lvn.egpr.topcoder-g-hatena-ne-jp.jag-icpc.org.qbb.hf http://mewkid.net/buy-amoxicillin/

onulepurao2019/06/08 11:47http://mewkid.net/buy-amoxicillin/ - Amoxicilline 500 Mg Online <a href="http://mewkid.net/buy-amoxicillin/">Buy Amoxicillin Online</a> bye.bmib.topcoder-g-hatena-ne-jp.jag-icpc.org.crm.ej http://mewkid.net/buy-amoxicillin/

ofineazaqaoho2019/07/23 08:59http://mewkid.net/order-amoxicillin/ - Amoxicillin Online <a href="http://mewkid.net/order-amoxicillin/">Buy Amoxicillin Online</a> ikw.kzoa.topcoder-g-hatena-ne-jp.jag-icpc.org.gtd.cz http://mewkid.net/order-amoxicillin/

asidvifilez2019/07/23 09:46http://mewkid.net/order-amoxicillin/ - Amoxicillin 500mg Capsules <a href="http://mewkid.net/order-amoxicillin/">Online Amoxicillin</a> prx.vzlq.topcoder-g-hatena-ne-jp.jag-icpc.org.fwp.gv http://mewkid.net/order-amoxicillin/

2012-09-10

値の差分表現

15:06

昨日のは，まるっきり既出でした（iwiさんに教えてもらいました．ありがとうございます）： http://poj.org/problem?id=3580

一般的なので，同じ構造を使う問題があるとは思っていましたが，まさかそのままデータ構造を問う形での出題があるとは思っていませんでした．解説もあるよ：http://poj.org/showcontest?contest_id=1290

しかも，この問題に対する主流の解法が，自分の予定していた解法よりも実装容易だったので，来週まで待たずに解説を張ってしまいます．これから解答を作る予定だった方は，すみません．来週はストックを前倒して別のものを書きます．

想定解法

「値の差分表現」とよばれる技法を使うのが想定でした．これはリンク・カット木の実装の際によく使われるもので，たとえば以下の資料にかいてあります．

平衡二分探索木（挿入・削除がない場合は，区分木でOK）を使います．ノードにもたせる値を

struct Node {
  Node *ch[2];
  int δcost;
  int δmin;
};

のようにします．ここでδcost が値の差分表現と呼ばれるもので，本来のノードのもつ値が根までのδcostの経路和になるように定めます： cost(u) = Σ[v=n～root] δcost(v) ．区間への値の足しこみは，δcostに値を加えれば，そこを経路としてもつ点すべてに値をくわえたことになります．cost(u) の取得は，経路を手繰りながら値を足していきます．

δmin は，そのノード以下の最小値 min(u) に対して min(u) = δmin(u) - cost(u) となるように定めます．min(u) = min { cost(u), min(left), min(right) } の関係式に δmin の定義を入れると δminの更新式が得られます：δmin(u) = min { 0, δmin(left)+δcost(u), δmin(right)+δcost(u) （符号は定義の仕方でいろいろ），あとは，これにしたがって更新していくだけです．

平衡二分探索木の回転が問題で，δcost の更新に工夫が要ります．回転時に関わるノードについて，回転前後で cost(u) 不変の条件から δcost の更新式が得られるので，それにしたがって更新します．

別解法

冒頭で述べた問題に対する講評を見ると，こちらの解法が主流のようで，実際，実装も容易なので紹介します．一言でいえば，addクエリを遅延評価します．

二分木のノード u 以下すべてに x を足しこむ関数は

  add(u, x) = { cost(u) += x; add(left,x); add(right,x); }

として定義できますが，これを（普通の言語で）そのまま書くと u 以下のノード数に比例した時間がかかってしまいます．しかし，実際に cost の値が必要になるまで add の伝播を遅延させれば計算量の問題がなくなります．

実際の実装では

struct Node {
  Node *ch[2];
  int cost;
  int min;
  int δcost;
};

のように，通常の値 cost, min を保持しつつ，さらに遅延評価用に差分の値 δcost を保持します．そして必要な場合だけ δcost を反映させていきます．

こちらの実装では，回転操作で悩むことがありません．関係ありそうなところのδcostをすべて評価してしまえば普通の回転と同じです．この点で差分表現を用いる解法よりも若干実装容易といえます．

コメントを書く

iwiwi2012/09/11 00:00区分木では，値の差分表現の方が僕は好きでそっちをよく使います．平衡二分探索木だと，仰る通り回転で訳が分からなくなるので遅延評価を使います．余談ですが，そういったクエリを抜きにしても回転は頭がこんがらがるので，回転抜きで平衡二分探索木が作れると友人から聞いて以降それをよく使っています．（ここで触れています http://www.slideshare.net/iwiwi/2-12188757）スケープゴート木も回転が要りませんが，あれは split/merge が出来ないのでコンテストでは使用場所が制限されてしまいます．

spaghetti_source2012/09/11 10:22merge-splitベースのtreapですね．あれは素晴らしい．自分は上からのアクセスで済む場合はmerge-split，下からアクセスする必要があれば回転ベースでやっています．scapegoatはそれらと比べてたいして実装が軽くないし，そもそも平衡できる程度の木に使うのは負けた気がして嫌です．笑

2012-09-09

次回予告

00:01

次回は次の問題に答えるテクニックを紹介します．興味のある人は考えてみてください．ネタバレ禁止とかは特に無いので，解答を思いついた方は是非トラックバックでも飛ばしてください（＝宣伝活動）．

ちなみに：問題１は多くの人が解けると思います．事前知識なしで問題２を思いついた方は自慢できます．１・２は実装量はたいしたことはありません．

問題１（簡単）

n 個の数が与えられる．クエリとして

get(i): i 番目の数を返す
addRange(i, j, x): i～j 番目の数に x を足す

がたくさん飛んでくるので，答えよ．

問題２（普通）

n 個の数が与えられる．クエリとして

get(i): i 番目の数を返す
addRange(i, j, x): i～j 番目の数に x を足す
minRange(i, j): i～j 番目の数の中で最小の値を返す

がたくさん飛んでくるので，答えよ．

問題３（難）

n 個の数が与えられる．クエリとして

get(i): i 番目の数を返す
addRange(i, j, x): i～j 番目の数に x を足す
minRange(i, j): i～j 番目の数の中で最小の値を返す
insert(i, x): i 番目に新たに数 x を挿入する
remove(i): i 番目の数を削除する

がたくさん飛んでくるので，答えよ．

コメントを書く

iwiwi2012/09/10 10:29http://poj.org/problem?id=3580 これに含まれていると思いますし，同様に普通の平衡二分探索木でできると思います．もしもっとマニアックなデータ構造じゃないと出来ない問題にしたいなら，もっと変なクエリが必要だと思います．

spaghetti_source2012/09/10 13:50既出だとは思っていましたが，まさかそのままより一般の問題があるとは思っていませんでした．

想定は普通の平衡二分探索木で，回転時に適切な更新を要するアレでしたが，addを遅延評価するのが主流みたいで，確かにそのほうが実装容易ですね．ぐぬぬ．

2012-09-08

Dynamic k-d Tree

08:13

前回のあらすじ：バランスが壊れたらぶっ壊して作りなおすと amortized O(log n)．

Scapegoat Treeでは，単純な二分探索木に破壊と再生テクニックを導入して計算量を低下させていたが，破壊と再生が本当に役立つのは

木だが，回転操作は難しい
一方，ゼロからバランスしたものを作るのはわりと楽

という構造が相手のときだと思う．このようなデータ構造の代表にk-d木があるので，今回はk-d木を破壊と再生で平衡化する手法を説明する．なお，これは前回文献として紹介したOvermars(1983)に載っている内容なので，歴史的にはScapegoat Tree(Andersson(1989), Galperin-Rivest(1993)) よりも古い．

k-d木は深さごとに軸が変わる二分探索木のことで，空間からの点の探索などに使われる．この上で「二分探索木の回転」みたいな操作をやろうとすると，うんざりできる程度にはややこしいことに気づく．一方で，ゼロから完全平衡したk-d木を作るのは難しくなくて，軸に応じた中央値をとって左右を再帰的に構成するだけでいける．計算量は中央値を O(n) でとって f(n) = 2 f(n/2) + O(n) の f(n) = O(n log n)．以下にその実装例を示す（クエリなし．つくるだけ）．

// 29 lines
const int D = 2;
struct kdTree {
  struct Node {
    int x, y;
    Node *ch[2];
    Node(int x, int y) : x(x), y(y) { ch[0] = ch[1] = 0; }
  } *r;
  struct Compare {
    int d;
    Compare(int d) : d(d) { }
    bool operator()(Node *i, Node *j) {
      return d == 0 ? (i->x < j->x) : (i->y < j->y);
    }
  };
  Node *build(Node **b, Node **e, int d) {
    if (e - b <= 0) return 0;
    Node **m = b + (e - b) / 2;
    nth_element(b, m, e, Compare(d)); 
    (*m)->ch[0] = build(b, m, (d+1)%D);
    (*m)->ch[1] = build(m+1, e, (d+1)%D);
    return *m;
  }
  kdTree(int p[][2], int n) {
    Node *node[n];
    for (int i = 0; i < n; ++i) 
      node[i] = new Node(p[i][0], p[i][1]);
    r = build(node, node+n, 0);
  }
};

さて，ここからがポイント．まずは平衡化を後回しにして要素の追加と削除を入れていく．

追加は普通の二分探索木と同じでよい．要素の追加は葉にしか発生しないので，特に難しいことはない．削除は問題で，中間ノードが消えると以降のk-d条件が意味不明になってしまう．そこで削除は「削除したマーク」をつけて以降無視する，という実装をとる．これは破壊と再生テクニックのときに使うテクニックでもあった．

// 53 lines = 29 + 24 
const int D = 2;
struct kdTree {
  struct Node {
    int x, y;
    bool removed;
    Node *ch[2];
    Node(int x, int y) : x(x), y(y), removed(false) { ch[0] = ch[1] = 0; }
  } *r;
//
// ...omit...
//
  Node *insert(Node *t, Node *p, int d) {
    if (!t) return p;
    int b = !Compare(d)(p, t); 
    t->ch[b] = insert(t->ch[b], p, (d+1)%D);
    return t;
  }
  void insert(int x, int y) { r = insert(r, new Node(x,y), 0); }

  Node *find(Node *t, Node *p, int d) {
    if (!t) return 0;
    Node *f = 0;
    if (!t->removed && t->x == p->x && t->y == p->y) f = t;
    if (!f && !Compare(d)(p,t)) f = find(t->ch[1], p, (d+1)%D);
    if (!f && !Compare(d)(t,p)) f = find(t->ch[0], p, (d+1)%D);
    return f;
  }
  Node *find(int x, int y) { Node n(x,y); return find(r, &n, 0); }

  void remove(int x, int y) { 
    Node *f = find(x, y);
    if (!f) return;
    f->removed = true;
  }
};

そして最後にこれを平衡化しよう．remove のときは remove されたノード数を覚えておいて，しきい値を超えたら Global Rebuilding するだけでよい．insert は Partial Rebuilding をしなければならないので，そのために各ノードにサイズ（自分以下の子の数）と，高さを追加情報として覚えさせる．そして insert が実行されたらに挿入パス上のノードにおいて log(サイズ) と高さを比較して必要なら Partial Rebuilding する．

全体のソースコードは次のようになる．計算量は若干の注意が必要で，Scapegoat Tree のときは Rebuilding が O(n) でできたので n 回にならすと O(1) になり，無視して O(log n) と見積もっていた．この場合は Rebuilding に O(n log n) かかるので，ならして O(log n) になるから，あわせて O(log n) となる．

// 78 lines = 53 + 25
const int D = 2;
struct kdTree {
  int removed;
  struct Node {
    int x, y;
    bool removed;
    Node *ch[2];
    int size, ht;
    Node(int x, int y) : x(x), y(y), removed(false) { ch[0] = ch[1] = 0; }
  } *r;
  int size(Node *t) { return t ? t->size : 0; }
  int ht(Node *t) { return t ? t->ht : 0; }
  Node *update(Node *t) {
    if (!t) return t;
    t->size = 1 + size(t->ch[0]) + size(t->ch[1]);
    t->ht = 1 + max(ht(t->ch[0]), ht(t->ch[1]));
    return t;
  }
  struct Compare {
    int d;
    Compare(int d) : d(d) { }
    bool operator()(Node *i, Node *j) {
      return d == 0 ? (i->x < j->x) : (i->y < j->y);
    }
  };
  Node *build(Node **b, Node **e, int d) {
    if (e - b <= 0) return 0;
    Node **m = b + (e - b) / 2;
    nth_element(b, m, e, Compare(d)); 
    (*m)->ch[0] = build(b, m, (d+1)%D);
    (*m)->ch[1] = build(m+1, e, (d+1)%D);
    return update(*m);
  }
  Node **flatten(Node *r, Node **buf) {
    if (!r) return buf;
    buf = flatten(r->ch[0], buf);
    if (!r->removed) *(buf++) = r;
    return flatten(r->ch[1], buf);
  }
  Node *rebuild(Node *r, int d) {
    Node *b[size(r)], **e = flatten(r, b);
    removed -= size(r) - (e - b);
    return build(b, e, d);
  }
  kdTree(int p[][2], int n) : removed(0) {
    Node *node[n];
    for (int i = 0; i < n; ++i) 
      node[i] = new Node(p[i][0], p[i][1]);
    r = build(node, node+n, 0);
  }
  Node *insert(Node *t, Node *p, int d) {
    if (!t) return update(p);
    int b = !Compare(d)(p, t); 
    t->ch[b] = insert(t->ch[b], p, (d+1)%D);
    t = update(t);
    if (3 * log(size(t)) < ht(t)) t = rebuild(t, d);
    return t;
  }
  void insert(int x, int y) { r = insert(r, new Node(x,y), 0); }

  Node *find(Node *t, Node *p, int d) {
    if (!t) return 0;
    Node *f = 0;
    if (!t->removed && t->x == p->x && t->y == p->y) f = t;
    if (!f && !Compare(d)(p,t)) f = find(t->ch[1], p, (d+1)%D);
    if (!f && !Compare(d)(t,p)) f = find(t->ch[0], p, (d+1)%D);
    return f;
  }
  Node *find(int x, int y) { Node n(x,y); return find(r, &n, 0); }

  void remove(int x, int y) { 
    Node *f = find(x, y);
    if (!f) return;
    f->removed = true;
    ++removed;
    if (removed*2 > r->size) r = rebuild(r, 0);
  }
};

コメントを書く

Quick Loans 2018/07/29 09:19loans <a href="http://directlending.cars">loan bad credit</a> loans <a href=http://directlending.cars>online loans for bad credit</a>

Online Lenders 2018/07/29 13:37loans <a href="http://directlending.cars">ace cash express</a> loans <a href=http://directlending.cars>loan for bad credit</a>

Antenoaltederse2018/07/30 05:37cheapest car insurance <a href="https://wecarinsurance.us.com/">car insurance companies</a> car insurance companies <a href="https://wecarinsurance.us.com/">amica car insurance</a> | https://wecarinsurance.us.com/ - cheap auto insurance https://wecarinsurance.us.com/ - the general car insurance florida

JougAugmems2018/07/31 08:57casino bonus <a href="https://onlinecasinoflow.com/">free online casino slots</a> tropicana online casino <a href="https://onlinecasinoflow.com/">real money casino</a> | https://onlinecasinoflow.com/ - borgata online casino https://onlinecasinoflow.com/ - online casino bonus

abnoliinown2018/07/31 09:02foxwoods online casino <a href="https://onlinecasino888.us.org/">play casino</a> tropicana online casino <a href="https://onlinecasino888.us.org/">online casino gambling</a> | https://onlinecasino888.us.org/ - online casino gambling https://onlinecasino888.us.org/ - casino bonus

Mypetrommenty2018/07/31 09:05casino online slots <a href="https://onlinecasinoplay777.us.org/">play casino</a> online casino gambling <a href="https://onlinecasinoplay777.us.org/">casino games</a> | https://onlinecasinoplay777.us.org/ - best online casinos https://onlinecasinoplay777.us.org/ - mgm online casino

MesePrappyskype2018/07/31 09:33online casinos <a href="https://onlinecasinodd.com/">foxwoods online casino</a> slots for real money <a href=" https://onlinecasinodd.com/">casino blackjack</a> | https://onlinecasinodd.com/ - play casino https://onlinecasinodd.com/ - virgin online casino

JenoSeeri2018/07/31 09:42caesars online casino <a href="https://onlinecasinobiggs.com/">online casino real money</a> online gambling <a href=" https://onlinecasinobiggs.com/ ">betfair online casino</a> | https://onlinecasinobiggs.com/ - casino games https://onlinecasinobiggs.com/ - best online casino

Antenoaltederse2018/07/31 10:14betfair online casino <a href="https://onlinecasinospark.com/">zone online casino</a> foxwoods online casino <a href="https://onlinecasinospark.com/">online gambling casino</a> | https://onlinecasinospark.com/ - virgin online casino https://onlinecasinospark.com/ - casino real money

JougAugmems2018/07/31 10:32slots for real money <a href="https://onlinecasinoflow.com/">online casinos for us players</a> casino games <a href="https://onlinecasinoflow.com/">real money casino</a> | https://onlinecasinoflow.com/ - free online casino https://onlinecasinoflow.com/ - casino real money

abnoliinown2018/07/31 10:38empire city online casino <a href="https://onlinecasino888.us.org/">zone online casino</a> betfair online casino <a href="https://onlinecasino888.us.org/">casino games</a> | https://onlinecasino888.us.org/ - online casino gambling https://onlinecasino888.us.org/ - free online casino slots

Mypetrommenty2018/07/31 10:40play online casino <a href="https://onlinecasinoplay777.us.org/">casino blackjack</a> parx online casino <a href="https://onlinecasinoplay777.us.org/">online gambling casino</a> | https://onlinecasinoplay777.us.org/ - empire city online casino https://onlinecasinoplay777.us.org/ - borgata online casino

JenoSeeri2018/07/31 11:15foxwoods online casino <a href="https://onlinecasinobiggs.com/">caesars online casino</a> online casino real money <a href=" https://onlinecasinobiggs.com/ ">zone online casino</a> | https://onlinecasinobiggs.com/ - casino bonus https://onlinecasinobiggs.com/ - casino bonus

Antenoaltederse2018/07/31 11:45betfair online casino <a href="https://onlinecasinospark.com/">free online casino</a> real casino <a href="https://onlinecasinospark.com/">casino games</a> | https://onlinecasinospark.com/ - play online casino https://onlinecasinospark.com/ - foxwoods online casino

abnoliinown2018/07/31 12:13online casinos <a href="https://onlinecasino888.us.org/">real money casino</a> real money casino <a href="https://onlinecasino888.us.org/">online gambling</a> | https://onlinecasino888.us.org/ - online casino gambling https://onlinecasino888.us.org/ - tropicana online casino

Mypetrommenty2018/07/31 12:14free online casino slots <a href="https://onlinecasinoplay777.us.org/">empire city online casino</a> online casinos <a href="https://onlinecasinoplay777.us.org/">online casinos for us players</a> | https://onlinecasinoplay777.us.org/ - online casino games https://onlinecasinoplay777.us.org/ - free online casino slots

MesePrappyskype2018/07/31 12:41empire city online casino <a href="https://onlinecasinodd.com/">slots for real money</a> free online casino slots <a href=" https://onlinecasinodd.com/">virgin online casino</a> | https://onlinecasinodd.com/ - slots for real money https://onlinecasinodd.com/ - casino games

JenoSeeri2018/07/31 12:50online casinos <a href="https://onlinecasinobiggs.com/">slots for real money</a> real casino <a href=" https://onlinecasinobiggs.com/ ">play casino</a> | https://onlinecasinobiggs.com/ - mgm online casino https://onlinecasinobiggs.com/ - online casino games

Antenoaltederse2018/07/31 13:17foxwoods online casino <a href="https://onlinecasinospark.com/">real money casino</a> best online casino <a href="https://onlinecasinospark.com/">borgata online casino</a> | https://onlinecasinospark.com/ - tropicana online casino https://onlinecasinospark.com/ - empire city online casino

JougAugmems2018/07/31 13:40online casino slots <a href="https://onlinecasinoflow.com/">free online casino</a> online casino bonus <a href="https://onlinecasinoflow.com/">best online casinos</a> | https://onlinecasinoflow.com/ - online casinos for us players https://onlinecasinoflow.com/ - online casino games

abnoliinown2018/07/31 13:47empire city online casino <a href="https://onlinecasino888.us.org/">free online casino</a> free online casino <a href="https://onlinecasino888.us.org/">foxwoods online casino</a> | https://onlinecasino888.us.org/ - casino blackjack https://onlinecasino888.us.org/ - caesars online casino

Mypetrommenty2018/07/31 13:49online casino bonus <a href="https://onlinecasinoplay777.us.org/">mgm online casino</a> slots for real money <a href="https://onlinecasinoplay777.us.org/">online gambling</a> | https://onlinecasinoplay777.us.org/ - real casino https://onlinecasinoplay777.us.org/ - online casino real money

MesePrappyskype2018/07/31 14:16betfair online casino <a href="https://onlinecasinodd.com/">online casino gambling</a> betfair online casino <a href=" https://onlinecasinodd.com/">caesars online casino</a> | https://onlinecasinodd.com/ - online casino real money https://onlinecasinodd.com/ - online gambling

JenoSeeri2018/07/31 14:24casino real money <a href="https://onlinecasinobiggs.com/">casino play</a> online casino games <a href=" https://onlinecasinobiggs.com/ ">free online casino slots</a> | https://onlinecasinobiggs.com/ - best online casinos https://onlinecasinobiggs.com/ - real money casino

Antenoaltederse2018/07/31 14:49online casino sites <a href="https://onlinecasinospark.com/">casino real money</a> online casino slots <a href="https://onlinecasinospark.com/">casino blackjack</a> | https://onlinecasinospark.com/ - online casino sites https://onlinecasinospark.com/ - mgm online casino

JougAugmems2018/07/31 15:13foxwoods online casino <a href="https://onlinecasinoflow.com/">real money casino</a> best online casino <a href="https://onlinecasinoflow.com/">online casino slots</a> | https://onlinecasinoflow.com/ - casino online slots https://onlinecasinoflow.com/ - online casino slots

abnoliinown2018/07/31 15:23free online casino slots <a href="https://onlinecasino888.us.org/">slots for real money</a> play casino <a href="https://onlinecasino888.us.org/">free online casino slots</a> | https://onlinecasino888.us.org/ - casino blackjack https://onlinecasino888.us.org/ - zone online casino

Mypetrommenty2018/07/31 15:24tropicana online casino <a href="https://onlinecasinoplay777.us.org/">empire city online casino</a> online gambling <a href="https://onlinecasinoplay777.us.org/">zone online casino</a> | https://onlinecasinoplay777.us.org/ - casino games https://onlinecasinoplay777.us.org/ - zone online casino

MesePrappyskype2018/07/31 15:48slots for real money <a href="https://onlinecasinodd.com/">online gambling casino</a> parx online casino <a href=" https://onlinecasinodd.com/">online casino sites</a> | https://onlinecasinodd.com/ - casino blackjack https://onlinecasinodd.com/ - free online casino

JenoSeeri2018/07/31 15:58online gambling casino <a href="https://onlinecasinobiggs.com/">slots for real money</a> real money casino <a href=" https://onlinecasinobiggs.com/ ">online casino gambling</a> | https://onlinecasinobiggs.com/ - tropicana online casino https://onlinecasinobiggs.com/ - betfair online casino

abnoliinown2018/07/31 16:58parx online casino <a href="https://onlinecasino888.us.org/">empire city online casino</a> casino online slots <a href="https://onlinecasino888.us.org/">online casino slots</a> | https://onlinecasino888.us.org/ - foxwoods online casino https://onlinecasino888.us.org/ - parx online casino

Mypetrommenty2018/07/31 17:00borgata online casino <a href="https://onlinecasinoplay777.us.org/">online casino gambling</a> casino games <a href="https://onlinecasinoplay777.us.org/">casino bonus</a> | https://onlinecasinoplay777.us.org/ - casino bonus https://onlinecasinoplay777.us.org/ - empire city online casino

MesePrappyskype2018/07/31 17:22caesars online casino <a href="https://onlinecasinodd.com/">casino blackjack</a> online casino slots <a href=" https://onlinecasinodd.com/">zone online casino</a> | https://onlinecasinodd.com/ - online casino gambling https://onlinecasinodd.com/ - casino real money

JenoSeeri2018/07/31 17:31online gambling casino <a href="https://onlinecasinobiggs.com/">online casino games</a> online casino sites <a href=" https://onlinecasinobiggs.com/ ">online casino games</a> | https://onlinecasinobiggs.com/ - borgata online casino https://onlinecasinobiggs.com/ - casino real money

Antenoaltederse2018/07/31 17:55online casino sites <a href="https://onlinecasinospark.com/">parx online casino</a> slots for real money <a href="https://onlinecasinospark.com/">foxwoods online casino</a> | https://onlinecasinospark.com/ - slots for real money https://onlinecasinospark.com/ - online casinos

JougAugmems2018/07/31 18:25casino real money <a href="https://onlinecasinoflow.com/">best online casino</a> empire city online casino <a href="https://onlinecasinoflow.com/">play casino</a> | https://onlinecasinoflow.com/ - mgm online casino https://onlinecasinoflow.com/ - betfair online casino

Mypetrommenty2018/07/31 18:38online casino sites <a href="https://onlinecasinoplay777.us.org/">tropicana online casino</a> casino online slots <a href="https://onlinecasinoplay777.us.org/">real casino</a> | https://onlinecasinoplay777.us.org/ - online casino sites https://onlinecasinoplay777.us.org/ - best online casino

abnoliinown2018/07/31 18:38casino play <a href="https://onlinecasino888.us.org/">casino bonus</a> foxwoods online casino <a href="https://onlinecasino888.us.org/">casino real money</a> | https://onlinecasino888.us.org/ - best online casino https://onlinecasino888.us.org/ - casino play

MesePrappyskype2018/07/31 18:58online casinos <a href="https://onlinecasinodd.com/">foxwoods online casino</a> free online casino <a href=" https://onlinecasinodd.com/">caesars online casino</a> | https://onlinecasinodd.com/ - casino games https://onlinecasinodd.com/ - online casino real money

JenoSeeri2018/07/31 19:04casino bonus <a href="https://onlinecasinobiggs.com/">casino bonus</a> online casino bonus <a href=" https://onlinecasinobiggs.com/ ">parx online casino</a> | https://onlinecasinobiggs.com/ - online casinos for us players https://onlinecasinobiggs.com/ - free online casino slots

Antenoaltederse2018/07/31 19:27online casino slots <a href="https://onlinecasinospark.com/">mgm online casino</a> real money casino <a href="https://onlinecasinospark.com/">online casino games</a> | https://onlinecasinospark.com/ - casino bonus https://onlinecasinospark.com/ - free online casino

abnoliinown2018/07/31 20:16online casino real money <a href="https://onlinecasino888.us.org/">foxwoods online casino</a> online casinos for us players <a href="https://onlinecasino888.us.org/">best online casino</a> | https://onlinecasino888.us.org/ - casino real money https://onlinecasino888.us.org/ - parx online casino

Mypetrommenty2018/07/31 20:16online gambling casino <a href="https://onlinecasinoplay777.us.org/">online gambling</a> empire city online casino <a href="https://onlinecasinoplay777.us.org/">online casinos</a> | https://onlinecasinoplay777.us.org/ - online casino gambling https://onlinecasinoplay777.us.org/ - free online casino

MesePrappyskype2018/07/31 20:32casino bonus <a href="https://onlinecasinodd.com/">online casinos for us players</a> zone online casino <a href=" https://onlinecasinodd.com/">parx online casino</a> | https://onlinecasinodd.com/ - online casino gambling https://onlinecasinodd.com/ - online casino sites

JenoSeeri2018/07/31 20:38online casino real money <a href="https://onlinecasinobiggs.com/">mgm online casino</a> parx online casino <a href=" https://onlinecasinobiggs.com/ ">mgm online casino</a> | https://onlinecasinobiggs.com/ - online casino bonus https://onlinecasinobiggs.com/ - mgm online casino

BladeBlersnap2018/07/31 20:44atkins diet first 14 days <a href="https://ketodietmax24.com/">fasting diet</a> gluten free diet <a href="https://ketodietmax24.com/">keto diet plan</a> | https://ketodietmax24.com/ - hcg diet https://ketodietmax24.com/ - mediterranean diet plan

GraroKewToole2018/07/31 20:44ketogenic diet plan <a href="https://ketodietus.com/">dash diet</a> ketogenic diet food list <a href="https://ketodietus.com/">weight watchers</a> | https://ketodietus.com/ - ketosis diet https://ketodietus.com/ - keto diet food list

drovoxofe2018/07/31 20:57ketogenic diet <a href="https://ketodietstar.com/">hcg diet</a> shepherds diet <a href="https://ketodietstar.com/">keto diet recipes</a> | https://ketodietstar.com/ - ketogenic diet food list https://ketodietstar.com/ - dash diet

Psywozyseetrops2018/07/31 20:57gluten free diet <a href="https://ketodiet24now.com/">apple cider vinegar diet</a> gerd diet <a href="https://ketodiet24now.com/">mediterranean diet</a> | https://ketodiet24now.com/ - egg diet https://ketodiet24now.com/ - mayo clinic diet

Antenoaltederse2018/07/31 21:02play online casino <a href="https://onlinecasinospark.com/">casino blackjack</a> slots for real money <a href="https://onlinecasinospark.com/">online gambling</a> | https://onlinecasinospark.com/ - online casino real money https://onlinecasinospark.com/ - casino online slots

Cevetsunemnisee2018/07/31 21:18posh casino online <a href="https://unitedonlinecasino.gb.net/">play online casino</a> paradise casino <a href="https://unitedonlinecasino.gb.net/">posh casino</a> | https://unitedonlinecasino.gb.net/ - bonus casino https://unitedonlinecasino.gb.net/ - foxwoods online casino

Freergyabesty2018/07/31 21:26mediterranean diet <a href="https://yourdiet24.com/">fasting diet</a> ketogenic diet food list <a href="https://yourdiet24.com/">keto diet</a> | https://yourdiet24.com/ - ketone diet https://yourdiet24.com/ - apple cider vinegar diet

ascevesaica2018/07/31 21:28vinegar diet <a href="https://ketodietix.com/">ketone diet</a> diet doctor <a href="https://ketodietix.com/">ketogenic diet plan</a> | https://ketodietix.com/ - dukan diet https://ketodietix.com/ - ketogenic diet food list

Hoalloffpleaway2018/07/31 21:29best online casinos <a href="https://bestonlinecasino.gb.net/">online gambling sites</a> maryland live casino online <a href="https://bestonlinecasino.gb.net/">twin river online casino</a> | https://bestonlinecasino.gb.net/ - real casino https://bestonlinecasino.gb.net/ - online casinos for us players

unsulneve2018/07/31 21:33online gambling <a href="https://slotsonlinecasino.gb.net/">tropicana online casino</a> borgata online casino <a href="https://slotsonlinecasino.gb.net/">hollywood casino online</a> | https://slotsonlinecasino.gb.net/ - betfair online casino https://slotsonlinecasino.gb.net/ - potawatomi casino

JougAugmems2018/07/31 21:35online casinos for us players <a href="https://onlinecasinoflow.com/">online casino gambling</a> mgm online casino <a href="https://onlinecasinoflow.com/">caesars online casino</a> | https://onlinecasinoflow.com/ - casino games https://onlinecasinoflow.com/ - best online casino

aspivamit2018/07/31 21:38best diet for weight loss <a href="https://weightlosstix.com/">isogenics weight loss program</a> weight loss recipes <a href="https://weightlosstix.com/">topamax for weight loss</a> | https://weightlosstix.com/ - weight loss plateau https://weightlosstix.com/ - truvision weight loss

Pearacagelp2018/07/31 21:43topamax for weight loss <a href="https://weightlossy24.com/">best weight loss pills</a> quick weight loss <a href="https://weightlossy24.com/">hypnosis for weight loss</a> | https://weightlossy24.com/ - ketogenic diet for weight loss https://weightlossy24.com/ - weight loss pills

ArcareappedgE2018/07/31 21:45free online slots no download no registration <a href="https://onlinecasinoslotsy.us.org/">free slots online no download no registration</a> play free slots for fun <a href="https://onlinecasinoslotsy.us.org/">free online slots no download no registration</a> | https://onlinecasinoslotsy.us.org/ - da vinci diamonds free online slots https://onlinecasinoslotsy.us.org/ - online slots

abnoliinown2018/07/31 21:52casino play <a href="https://onlinecasino888.us.org/">online casinos</a> online casino real money <a href="https://onlinecasino888.us.org/">online casinos for us players</a> | https://onlinecasino888.us.org/ - parx online casino https://onlinecasino888.us.org/ - play online casino

ArcareappedgE2018/07/31 21:53stn play online casino <a href="https://usaonlinecasino.gb.net/">virgin online casino nj</a> best online casino <a href="https://usaonlinecasino.gb.net/">virgin online casino nj</a> | https://usaonlinecasino.gb.net/ - best online casino https://usaonlinecasino.gb.net/ - high 5 casino

Vierrurpirm2018/07/31 21:53caesar casino online slot games <a href="https://onlinecasinoamerica.gb.net/">hyper casinos</a> parx casino <a href="https://onlinecasinoamerica.gb.net/">foxwoods online casino</a> | https://onlinecasinoamerica.gb.net/ - hyper casinos https://onlinecasinoamerica.gb.net/ - casino slots

tiniograsiovork2018/07/31 21:54medical weight loss <a href="https://weightlosseo.com/">chrissy metz weight loss</a> weight loss programs <a href="https://weightlosseo.com/">healthy recipes for weight loss</a> | https://weightlosseo.com/ - best foods for weight loss https://weightlosseo.com/ - best foods for weight loss

EnrignVar2018/07/31 21:54breakfast smoothies for weight loss <a href="https://weightlosskeyz.com/">isogenics weight loss program</a> weight loss plans <a href="https://weightlosskeyz.com/">apple cider vinegar weight loss</a> | https://weightlosskeyz.com/ - best weight loss supplements https://weightlosskeyz.com/ - weight loss smoothie recipes

Illecyscoolen2018/07/31 22:04fortune bay casino <a href="https://onlinecasinousa.gb.net/">foxwoods online casino</a> gambling online <a href="https://onlinecasinousa.gb.net/">muckleshoot casino</a> | https://onlinecasinousa.gb.net/ - casino real money https://onlinecasinousa.gb.net/ - mystic lake casino

Psywozyseetrops2018/07/31 22:05casino real money <a href="https://onlinecasinoally.com/">online casino real money</a> best online casinos <a href="https://onlinecasinoally.com/">casino slot</a> | https://onlinecasinoally.com/ - casino slots https://onlinecasinoally.com/ - gsn casino

MesePrappyskype2018/07/31 22:05real money casino <a href="https://onlinecasinodd.com/">online casino sites</a> online casino sites <a href=" https://onlinecasinodd.com/">borgata online casino</a> | https://onlinecasinodd.com/ - betfair online casino https://onlinecasinodd.com/ - online casino sites

GraroKewToole2018/07/31 22:06brat diet <a href="https://ketodietus.com/">shepherds diet</a> gout diet <a href="https://ketodietus.com/">gout diet</a> | https://ketodietus.com/ - apple cider vinegar diet https://ketodietus.com/ - 30 day keto meal plan

BladeBlersnap2018/07/31 22:06apple cider vinegar diet <a href="https://ketodietmax24.com/">diet doctor</a> fasting diet <a href="https://ketodietmax24.com/">gout diet</a> | https://ketodietmax24.com/ - anti inflammatory diet https://ketodietmax24.com/ - atkins diet first 14 days

Cevetsunemnisee2018/07/31 22:11cashman casino slots free <a href="https://onlinecasino777.gb.net/">free slots no download no registration</a> online slots real money <a href="https://onlinecasino777.gb.net/">free online slots no download</a> | https://onlinecasino777.gb.net/ - turning stone online slots https://onlinecasino777.gb.net/ - free online slots

Pipsymoms2018/07/31 22:24weight loss soup <a href="https://weightlosskeyz.com/">healthy snacks for weight loss</a> weight loss motivation <a href="https://weightlosskeyz.com/">chrissy metz weight loss</a> | https://weightlosskeyz.com/ - weight loss doctors near me https://weightlosskeyz.com/ - truvision weight loss

Grielpdriella2018/07/31 22:24meal plans for weight loss <a href="https://weightlossy24.com/">best weight loss pills</a> thrive weight loss <a href="https://weightlossy24.com/">melissa mccarthy weight loss</a> | https://weightlossy24.com/ - best diet for weight loss https://weightlossy24.com/ - weight loss surgery

drovoxofe2018/07/31 22:24ketogenic diet food list <a href="https://ketodietstar.com/">liquid diet</a> gluten free diet <a href="https://ketodietstar.com/">anti inflammatory diet</a> | https://ketodietstar.com/ - brat diet https://ketodietstar.com/ - mayo clinic diet

Psywozyseetrops2018/07/31 22:24alkaline diet <a href="https://ketodiet24now.com/">alkaline diet</a> dukan diet <a href="https://ketodiet24now.com/">low carb diet</a> | https://ketodiet24now.com/ - renal diet https://ketodiet24now.com/ - liquid diet

Illecyscoolen2018/07/31 22:30slot games <a href="https://onlinecasinoslotsplay.us.org/">casino games slots free</a> hot shot casino slots <a href="https://onlinecasinoslotsplay.us.org/">free online slots no download no registration</a> | https://onlinecasinoslotsplay.us.org/ - hollywood casino free slots https://onlinecasinoslotsplay.us.org/ - hot shot casino slots

GraroKewToole2018/07/31 22:31playmgm nj casino online <a href="https://onlinecasinosiri.com/">posh casino online</a> chumba casino <a href="https://onlinecasinosiri.com/">hallmark online casino</a> | https://onlinecasinosiri.com/ - casino bonus https://onlinecasinosiri.com/ - casino games no download no registration

FarAdaky2018/07/31 22:32caesars casino online <a href="https://onlinecasinoplayusa.us.org/">casino real money</a> casinos online <a href="https://onlinecasinoplayusa.us.org/">huuuge casino slots</a> | https://onlinecasinoplayusa.us.org/ - grand falls casino https://onlinecasinoplayusa.us.org/ - online gambling sites

drovoxofe2018/07/31 22:33hollywood casino play4fun <a href="https://onlinecasinotouch.com/">stn play online casino</a> foxwoods casino online <a href="https://onlinecasinotouch.com/">casinos in iowa</a> | https://onlinecasinotouch.com/ - vegas slots casino online https://onlinecasinotouch.com/ - slots casino games

DerPrurce2018/07/31 22:34stn play online casino <a href="https://onlinecasinogamess.us.org/">casino bonus</a> doubledown casino facebook <a href="https://onlinecasinogamess.us.org/">bonus casino</a> | https://onlinecasinogamess.us.org/ - bigfish casino online games https://onlinecasinogamess.us.org/ - caesar casino online slot games

Vierrurpirm2018/07/31 22:36free slots vegas world <a href="https://onlinecasinostates.gb.net/">free vegas slots online</a> free slots no download <a href="https://onlinecasinostates.gb.net/">cashman casino slots</a> | https://onlinecasinostates.gb.net/ - casino slots free games https://onlinecasinostates.gb.net/ - free slots online no download no registration

Hoalloffpleaway2018/07/31 22:39turning stone online slots <a href="https://casinoslotsgames.us.org/">slots online</a> free slot machine games <a href="https://casinoslotsgames.us.org/">free slot machine games</a> | https://casinoslotsgames.us.org/ - free vegas slots online https://casinoslotsgames.us.org/ - free slot machine games

BladeBlersnap2018/07/31 22:46foxwoods resort casino <a href="https://onlinecasinopalm.com/">online casinos</a> online casino bonus <a href="https://onlinecasinopalm.com/">twin river online casino</a> | https://onlinecasinopalm.com/ - foxwoods casino online https://onlinecasinopalm.com/ - posh casino online

Freergyabesty2018/07/31 22:46diet <a href="https://yourdiet24.com/">ketone diet</a> anti inflammatory diet <a href="https://yourdiet24.com/">mediterranean diet</a> | https://yourdiet24.com/ - shepherds diet https://yourdiet24.com/ - 30 day keto meal plan

ascevesaica2018/07/31 22:4730 day keto meal plan <a href="https://ketodietix.com/">paleo diet food list</a> mediterranean diet recipes <a href="https://ketodietix.com/">atkins diet first 14 days</a> | https://ketodietix.com/ - brat diet https://ketodietix.com/ - egg diet

Cevetsunemnisee2018/07/31 22:49doubledown casino <a href="https://unitedonlinecasino.gb.net/">parx casino</a> slots for real money <a href="https://unitedonlinecasino.gb.net/">gsn casino</a> | https://unitedonlinecasino.gb.net/ - vegas casino online https://unitedonlinecasino.gb.net/ - chinook winds casino

unsulneve2018/07/31 22:49slots games <a href="https://onlinecasinoslotsgames.us.org/">free slot games with no download</a> free online slots no download no registration <a href="https://onlinecasinoslotsgames.us.org/">hot shot casino slots</a> | https://onlinecasinoslotsgames.us.org/ - free slot games https://onlinecasinoslotsgames.us.org/ - hollywood casino free slots

Hoalloffpleaway2018/07/31 22:50real money casino <a href="https://bestonlinecasino.gb.net/">betfair casino online nj</a> tropicana online casino nj <a href="https://bestonlinecasino.gb.net/">vegas world casino games</a> | https://bestonlinecasino.gb.net/ - hallmark online casino https://bestonlinecasino.gb.net/ - slots for real money

aspivamit2018/07/31 22:59optivia weight loss <a href="https://weightlosstix.com/">topiramate for weight loss</a> fast weight loss <a href="https://weightlosstix.com/">saxenda for weight loss</a> | https://weightlosstix.com/ - weight loss tea https://weightlosstix.com/ - weight loss challenge

Pearacagelp2018/07/31 23:03dogs wife beth weight loss <a href="https://weightlossy24.com/">weight loss tips</a> protein shakes for weight loss <a href="https://weightlossy24.com/">weight loss foods</a> | https://weightlossy24.com/ - quick weight loss diet https://weightlossy24.com/ - quick weight loss diet

unsulneve2018/07/31 23:03sugarhouse casino online <a href="https://slotsonlinecasino.gb.net/">online casinos for us players</a> harrah online casino <a href="https://slotsonlinecasino.gb.net/">casino play</a> | https://slotsonlinecasino.gb.net/ - doubledown casino promo codes https://slotsonlinecasino.gb.net/ - high five casino slots

EsonZoobbyido2018/07/31 23:04doubleu casino on facebook <a href="https://onlinecasinobestplay.us.org/">virgin casino online nj</a> cashman casino <a href="https://onlinecasinobestplay.us.org/">high 5 casino</a> | https://onlinecasinobestplay.us.org/ - hollywood casino online slots https://onlinecasinobestplay.us.org/ - san manuel casino

injepecife2018/07/31 23:04dakota sioux casino <a href="https://onlinecasinoxplay.us.org/">online casino real money</a> gossip online casino <a href="https://onlinecasinoxplay.us.org/">casino real money</a> | https://onlinecasinoxplay.us.org/ - casino game https://onlinecasinoxplay.us.org/ - doubledown casino

JougAugmems2018/07/31 23:08online casinos for us players <a href="https://onlinecasinoflow.com/">empire city online casino</a> mgm online casino <a href="https://onlinecasinoflow.com/">play online casino</a> | https://onlinecasinoflow.com/ - online casino sites https://onlinecasinoflow.com/ - online casino games

tiniograsiovork2018/07/31 23:21abby lee miller weight loss <a href="https://weightlosseo.com/">weight watchers</a> weight loss shakes <a href="https://weightlosseo.com/">protein shakes for weight loss</a> | https://weightlosseo.com/ - mama june weight loss https://weightlosseo.com/ - meal replacement shakes for weight loss

EnrignVar2018/07/31 23:21medi weight loss program <a href="https://weightlosskeyz.com/">weight loss</a> weight loss doctors near me <a href="https://weightlosskeyz.com/">weight loss recipes</a> | https://weightlosskeyz.com/ - smoothie recipes for weight loss https://weightlosskeyz.com/ - dogs wife beth weight loss

ArcareappedgE2018/07/31 23:22playmgm nj casino online <a href="https://usaonlinecasino.gb.net/">doubledown casino facebook</a> gsn casino games <a href="https://usaonlinecasino.gb.net/">chinook winds casino</a> | https://usaonlinecasino.gb.net/ - online casino slots https://usaonlinecasino.gb.net/ - bovada casino

Vierrurpirm2018/07/31 23:22gambling sites <a href="https://onlinecasinoamerica.gb.net/">snoqualmie casino</a> prairie meadows casino <a href="https://onlinecasinoamerica.gb.net/">royal river casino</a> | https://onlinecasinoamerica.gb.net/ - slots casino games https://onlinecasinoamerica.gb.net/ - bonus casino

Psywozyseetrops2018/07/31 23:28gossip online casino <a href="https://onlinecasinoally.com/">hollywood casino online</a> casino real money <a href="https://onlinecasinoally.com/">online casino games free</a> | https://onlinecasinoally.com/ - slots for real money https://onlinecasinoally.com/ - chumba casino

abnoliinown2018/07/31 23:28borgata online casino <a href="https://onlinecasino888.us.org/">play online casino</a> online casino slots <a href="https://onlinecasino888.us.org/">online casino slots</a> | https://onlinecasino888.us.org/ - free online casino slots https://onlinecasino888.us.org/ - casino online slots

Illecyscoolen2018/07/31 23:28bovada casino <a href="https://onlinecasinousa.gb.net/">jackpot party casino</a> casino bonus <a href="https://onlinecasinousa.gb.net/">casinos in iowa</a> | https://onlinecasinousa.gb.net/ - gossip online casino https://onlinecasinousa.gb.net/ - ignition casino

BladeBlersnap2018/07/31 23:28mediterranean diet plan <a href="https://ketodietmax24.com/">gerd diet</a> dash diet <a href="https://ketodietmax24.com/">diabetes diet</a> | https://ketodietmax24.com/ - keto diet plan for beginners https://ketodietmax24.com/ - whole 30 diet

GraroKewToole2018/07/31 23:30ketosis diet <a href="https://ketodietus.com/">dukan diet</a> diet pills <a href="https://ketodietus.com/">dash diet</a> | https://ketodietus.com/ - dash diet https://ketodietus.com/ - fodmap diet

Cevetsunemnisee2018/07/31 23:31free slots games online <a href="https://onlinecasino777.gb.net/">casino slots</a> hot shot casino slots <a href="https://onlinecasino777.gb.net/">da vinci diamonds free online slots</a> | https://onlinecasino777.gb.net/ - casino slots free games https://onlinecasino777.gb.net/ - hot shot casino slots

MesePrappyskype2018/07/31 23:39online gambling casino <a href="https://onlinecasinodd.com/">foxwoods online casino</a> best online casino <a href=" https://onlinecasinodd.com/">free online casino</a> | https://onlinecasinodd.com/ - online gambling casino https://onlinecasinodd.com/ - online casino bonus

JenoSeeri2018/07/31 23:43casino play <a href="https://onlinecasinobiggs.com/">real casino</a> real casino <a href=" https://onlinecasinobiggs.com/ ">free online casino slots</a> | https://onlinecasinobiggs.com/ - real money casino https://onlinecasinobiggs.com/ - online casinos

Grielpdriella2018/07/31 23:46metformin for weight loss <a href="https://weightlossy24.com/">weight loss</a> weight loss soup <a href="https://weightlossy24.com/">melissa mccarthy weight loss</a> | https://weightlossy24.com/ - figure weight loss https://weightlossy24.com/ - juicing recipes for weight loss

drovoxofe2018/07/31 23:49gout diet <a href="https://ketodietstar.com/">apple cider vinegar diet</a> liquid diet <a href="https://ketodietstar.com/">paleo diet food list</a> | https://ketodietstar.com/ - shepherds diet https://ketodietstar.com/ - fasting diet

Illecyscoolen2018/07/31 23:50free casino slots games <a href="https://onlinecasinoslotsplay.us.org/">free casino slots no download</a> free slots casino games <a href="https://onlinecasinoslotsplay.us.org/">free slots games</a> | https://onlinecasinoslotsplay.us.org/ - free casino slots https://onlinecasinoslotsplay.us.org/ - vegas slots online free

GraroKewToole2018/07/31 23:53casino blackjack <a href="https://onlinecasinosiri.com/">online casino slots no download</a> real casino slots <a href="https://onlinecasinosiri.com/">doubledown casino</a> | https://onlinecasinosiri.com/ - gsn casino https://onlinecasinosiri.com/ - zone online casino vegas world

ascevesaica2018/07/31 23:54stn play online casino <a href="https://onlinecasinounit.com/">gambling online</a> choctaw casino durant oklahoma <a href="https://onlinecasinounit.com/">fantasy springs resort casino</a> | https://onlinecasinounit.com/ - bovada casino https://onlinecasinounit.com/ - online casino real money

drovoxofe2018/07/31 23:56morongo casino <a href="https://onlinecasinotouch.com/">winstar world casino</a> penny slots <a href="https://onlinecasinotouch.com/">bovada casino</a> | https://onlinecasinotouch.com/ - online casino https://onlinecasinotouch.com/ - prairie meadows casino

Vierrurpirm2018/07/31 23:57slots online free <a href="https://onlinecasinostates.gb.net/">free online slots no download no registration</a> vegas slots online free <a href="https://onlinecasinostates.gb.net/">vegas casino slots</a> | https://onlinecasinostates.gb.net/ - free games for casino slots hollywood https://onlinecasinostates.gb.net/ - online casino slots

Hoalloffpleaway2018/07/31 23:59turning stone online slots <a href="https://casinoslotsgames.us.org/">slots for free</a> slot machines <a href="https://casinoslotsgames.us.org/">hollywood casino online slots</a> | https://casinoslotsgames.us.org/ - online slots free https://casinoslotsgames.us.org/ - online casino slots no download

FarAdaky2018/08/01 00:01turning stone casino <a href="https://onlinecasinoplayusa.us.org/">casino game</a> doubledown casino <a href="https://onlinecasinoplayusa.us.org/">real casino slots</a> | https://onlinecasinoplayusa.us.org/ - foxwoods resort casino https://onlinecasinoplayusa.us.org/ - real casino slots

DerPrurce2018/08/01 00:03hallmark casino online <a href="https://onlinecasinogamess.us.org/">parx casino online</a> gsn casino slots <a href="https://onlinecasinogamess.us.org/">online casino games free</a> | https://onlinecasinogamess.us.org/ - casino games https://onlinecasinogamess.us.org/ - casino games

goassyliaibia2018/08/01 00:06empire casino online <a href="https://onlinecasinogamesplay.us.org/">high five casino slots</a> hallmark casino online <a href="https://onlinecasinogamesplay.us.org/">online casinos for us players</a> | https://onlinecasinogamesplay.us.org/ - choctaw casino https://onlinecasinogamesplay.us.org/ - hollywood casino online facebook

Antenoaltederse2018/08/01 00:08mgm online casino <a href="https://onlinecasinospark.com/">online casino gambling</a> online casino gambling <a href="https://onlinecasinospark.com/">tropicana online casino</a> | https://onlinecasinospark.com/ - online casino gambling https://onlinecasinospark.com/ - zone online casino

Freergyabesty2018/08/01 00:11shepherds diet <a href="https://yourdiet24.com/">keto diet</a> mediterranean diet <a href="https://yourdiet24.com/">diet coke</a> | https://yourdiet24.com/ - paleo diet food list https://yourdiet24.com/ - hcg diet

ascevesaica2018/08/01 00:11military diet <a href="https://ketodietix.com/">30 day keto meal plan</a> mediterranean diet <a href="https://ketodietix.com/">mediterranean diet</a> | https://ketodietix.com/ - ketone diet https://ketodietix.com/ - dash diet

unsulneve2018/08/01 00:11free slot games online <a href="https://onlinecasinoslotsgames.us.org/">free online slots no download</a> free casino slots <a href="https://onlinecasinoslotsgames.us.org/">free slots games</a> | https://onlinecasinoslotsgames.us.org/ - slot games free https://onlinecasinoslotsgames.us.org/ - vegas free slots

BladeBlersnap2018/08/01 00:12bigfish casino online games <a href="https://onlinecasinopalm.com/">casino slots</a> seneca casino online games <a href="https://onlinecasinopalm.com/">gossip online casino</a> | https://onlinecasinopalm.com/ - foxwoods casino online slots https://onlinecasinopalm.com/ - online gambling

Hoalloffpleaway2018/08/01 00:12best online casino <a href="https://bestonlinecasino.gb.net/">resorts online casino nj</a> foxwoods online casino <a href="https://bestonlinecasino.gb.net/">potawatomi casino</a> | https://bestonlinecasino.gb.net/ - jackpot party casino slots on facebook https://bestonlinecasino.gb.net/ - double down casino

Freergyabesty2018/08/01 00:14seneca casino online games <a href="https://onlinecasinoassist.com/">treasure island casino minnesota</a> online casinos for us players <a href="https://onlinecasinoassist.com/">gsn casino slots</a> | https://onlinecasinoassist.com/ - hollywood casino online facebook https://onlinecasinoassist.com/ - harrah online casino

aspivamit2018/08/01 00:17red mountain weight loss <a href="https://weightlosstix.com/">weight loss motivation</a> optivia weight loss <a href="https://weightlosstix.com/">weight loss foods</a> | https://weightlosstix.com/ - isogenics weight loss program https://weightlosstix.com/ - weight loss meal plan

Cevetsunemnisee2018/08/01 00:19tropicana online casino nj <a href="https://unitedonlinecasino.gb.net/">hollywood casino play4fun</a> big fish casino slots <a href="https://unitedonlinecasino.gb.net/">gsn casino games</a> | https://unitedonlinecasino.gb.net/ - parx casino online https://unitedonlinecasino.gb.net/ - prairie meadows casino

Pearacagelp2018/08/01 00:22melissa mccarthy weight loss <a href="https://weightlossy24.com/">abby lee miller weight loss</a> juicing for weight loss <a href="https://weightlossy24.com/">meal plans for weight loss</a> | https://weightlossy24.com/ - quick weight loss https://weightlossy24.com/ - medi weight loss

ArcareappedgE2018/08/01 00:22play slots <a href="https://onlinecasinoslotsy.us.org/">online casino slots</a> free slot play no download <a href="https://onlinecasinoslotsy.us.org/">online casino slots no download</a> | https://onlinecasinoslotsy.us.org/ - hollywood casino online slots free https://onlinecasinoslotsy.us.org/ - online slots real money

unsulneve2018/08/01 00:32dakota sioux casino <a href="https://slotsonlinecasino.gb.net/">rock n cash casino slots</a> choctaw casino durant oklahoma <a href="https://slotsonlinecasino.gb.net/">gambling games</a> | https://slotsonlinecasino.gb.net/ - real money casino https://slotsonlinecasino.gb.net/ - real casino

EsonZoobbyido2018/08/01 00:36online casino slots <a href="https://onlinecasinobestplay.us.org/">vegas world casino slots</a> gsn casino <a href="https://onlinecasinobestplay.us.org/">rock n cash casino slots</a> | https://onlinecasinobestplay.us.org/ - caesars casino online https://onlinecasinobestplay.us.org/ - muckleshoot casino

injepecife2018/08/01 00:37winstar world casino <a href="https://onlinecasinoxplay.us.org/">world class casino slots masque</a> gsn casino <a href="https://onlinecasinoxplay.us.org/">betfair casino online nj</a> | https://onlinecasinoxplay.us.org/ - winstar casino https://onlinecasinoxplay.us.org/ - online casino gambling

biondirE2018/08/01 00:37casino play <a href="https://bestonlinecasinogames.us.org/">real casino slots</a> four winds casino <a href="https://bestonlinecasinogames.us.org/">winstar casino</a> | https://bestonlinecasinogames.us.org/ - hyper casinos https://bestonlinecasinogames.us.org/ - penny slots

JougAugmems2018/08/01 00:39real money casino <a href="https://onlinecasinoflow.com/">parx online casino</a> casino real money <a href="https://onlinecasinoflow.com/">online casino slots</a> | https://onlinecasinoflow.com/ - online casinos https://onlinecasinoflow.com/ - free online casino

EnrignVar2018/08/01 00:46apple cider vinegar for weight loss <a href="https://weightlosskeyz.com/">weight loss pills</a> apple cider vinegar weight loss <a href="https://weightlosskeyz.com/">shark tank weight loss</a> | https://weightlosskeyz.com/ - weight loss plans https://weightlosskeyz.com/ - weight loss soup

tiniograsiovork2018/08/01 00:47figure weight loss <a href="https://weightlosseo.com/">best weight loss shakes</a> weight loss programs <a href="https://weightlosseo.com/">weight loss tips</a> | https://weightlosseo.com/ - healthy smoothies for weight loss https://weightlosseo.com/ - alli weight loss

Vierrurpirm2018/08/01 00:49bovada blackjack <a href="https://onlinecasinoamerica.gb.net/">seneca niagara casino</a> doubleu casino <a href="https://onlinecasinoamerica.gb.net/">prairie meadows casino</a> | https://onlinecasinoamerica.gb.net/ - parx casino online https://onlinecasinoamerica.gb.net/ - cashman casino

ArcareappedgE2018/08/01 00:49jack online casino <a href="https://usaonlinecasino.gb.net/">chumba casino</a> casino game <a href="https://usaonlinecasino.gb.net/">mgm online casino</a> | https://usaonlinecasino.gb.net/ - online gambling sites https://usaonlinecasino.gb.net/ - plainridge casino

Psywozyseetrops2018/08/01 00:50online casino bonus <a href="https://onlinecasinoally.com/">hollywood online casino</a> online casino slots no download <a href="https://onlinecasinoally.com/">zone online casino log in</a> | https://onlinecasinoally.com/ - chinook winds casino https://onlinecasinoally.com/ - slots casino games

Cevetsunemnisee2018/08/01 00:51slot games free <a href="https://onlinecasino777.gb.net/">free slots vegas world</a> slots online free <a href="https://onlinecasino777.gb.net/">free penny slots</a> | https://onlinecasino777.gb.net/ - free vegas slots online casino https://onlinecasino777.gb.net/ - cashman casino slots free

Illecyscoolen2018/08/01 00:52jackpot party casino facebook <a href="https://onlinecasinousa.gb.net/">casinos near me</a> real money casino <a href="https://onlinecasinousa.gb.net/">doubleu casino on facebook</a> | https://onlinecasinousa.gb.net/ - casino game https://onlinecasinousa.gb.net/ - bovada casino

BladeBlersnap2018/08/01 00:53vinegar diet <a href="https://ketodietmax24.com/">mediterranean diet plan</a> keto diet plan <a href="https://ketodietmax24.com/">diet</a> | https://ketodietmax24.com/ - renal diet https://ketodietmax24.com/ - dukan diet

GraroKewToole2018/08/01 00:53mediterranean diet plan <a href="https://ketodietus.com/">diet pills</a> keto diet plan <a href="https://ketodietus.com/">whole 30 diet</a> | [url=https://ketodietus.com/]alkaline diet[/url] [url=https://ketodietus.com/]keto diet food list[/url]

abnoliinown2018/08/01 01:07best online casinos <a href="https://onlinecasino888.us.org/">online casino slots</a> casino bonus <a href="https://onlinecasino888.us.org/">tropicana online casino</a> | https://onlinecasino888.us.org/ - empire city online casino https://onlinecasino888.us.org/ - casino blackjack

Mypetrommenty2018/08/01 01:07casino bonus <a href="https://onlinecasinoplay777.us.org/">foxwoods online casino</a> play online casino <a href="https://onlinecasinoplay777.us.org/">casino real money</a> | https://onlinecasinoplay777.us.org/ - online casino slots https://onlinecasinoplay777.us.org/ - betfair online casino

Grielpdriella2018/08/01 01:09healthy snacks for weight loss <a href="https://weightlossy24.com/">chrissy metz weight loss before and after</a> golo weight loss <a href="https://weightlossy24.com/">optifast weight loss program</a> | https://weightlossy24.com/ - shark tank weight loss https://weightlossy24.com/ - best weight loss pills

Pipsymoms2018/08/01 01:09low calorie recipes for weight loss <a href="https://weightlosskeyz.com/">figure weight loss</a> medi weight loss program <a href="https://weightlosskeyz.com/">apple cider vinegar weight loss</a> | https://weightlosskeyz.com/ - fast weight loss https://weightlosskeyz.com/ - chrissy metz weight loss

Illecyscoolen2018/08/01 01:10free slots online <a href="https://onlinecasinoslotsplay.us.org/">vegas slots online</a> slots games <a href="https://onlinecasinoslotsplay.us.org/">real casino slots</a> | https://onlinecasinoslotsplay.us.org/ - hollywood casino online slots https://onlinecasinoslotsplay.us.org/ - casino slots free games

drovoxofe2018/08/01 01:1330 day keto meal plan <a href="https://ketodietstar.com/">cabbage soup diet</a> brat diet <a href="https://ketodietstar.com/">paleo diet food list</a> | https://ketodietstar.com/ - whole 30 diet https://ketodietstar.com/ - alkaline diet

Psywozyseetrops2018/08/01 01:13keto diet food list <a href="https://ketodiet24now.com/">mediterranean diet recipes</a> gluten free diet <a href="https://ketodiet24now.com/">mediterranean diet</a> | https://ketodiet24now.com/ - fasting diet https://ketodiet24now.com/ - diet plans

MesePrappyskype2018/08/01 01:13mgm online casino <a href="https://onlinecasinodd.com/">casino online slots</a> real casino <a href=" https://onlinecasinodd.com/">real casino</a> | https://onlinecasinodd.com/ - foxwoods online casino https://onlinecasinodd.com/ - tropicana online casino

GraroKewToole2018/08/01 01:16online casino <a href="https://onlinecasinosiri.com/">seneca niagara casino</a> bigfish casino online games <a href="https://onlinecasinosiri.com/">hollywood casino</a> | https://onlinecasinosiri.com/ - gambling games https://onlinecasinosiri.com/ - foxwoods casino online slots

ascevesaica2018/08/01 01:16winstar world casino <a href="https://onlinecasinounit.com/">real money casino</a> prairie meadows casino <a href="https://onlinecasinounit.com/">double down casino</a> | https://onlinecasinounit.com/ - huge casino slots https://onlinecasinounit.com/ - real money casino

JenoSeeri2018/08/01 01:17casino real money <a href="https://onlinecasinobiggs.com/">mgm online casino</a> mgm online casino <a href=" https://onlinecasinobiggs.com/ ">real casino</a> | https://onlinecasinobiggs.com/ - real casino https://onlinecasinobiggs.com/ - zone online casino

Vierrurpirm2018/08/01 01:17cashman casino slots <a href="https://onlinecasinostates.gb.net/">free online slots no download no registration</a> free games for casino slots hollywood <a href="https://onlinecasinostates.gb.net/">hollywood casino free slots online</a> | https://onlinecasinostates.gb.net/ - slots online https://onlinecasinostates.gb.net/ - free vegas slots online casino

Hoalloffpleaway2018/08/01 01:18free slot games with no download <a href="https://casinoslotsgames.us.org/">slot machines</a> free online slots games <a href="https://casinoslotsgames.us.org/">slots games</a> | https://casinoslotsgames.us.org/ - online slots free https://casinoslotsgames.us.org/ - best online slots

drovoxofe2018/08/01 01:18hollywood casino online <a href="https://onlinecasinotouch.com/">three rivers casino</a> vegas casino online <a href="https://onlinecasinotouch.com/">codeshareonline doubledown casino</a> | https://onlinecasinotouch.com/ - playmgm nj casino online https://onlinecasinotouch.com/ - bovada casino

FarAdaky2018/08/01 01:29mystic lake casino <a href="https://onlinecasinoplayusa.us.org/">casino blackjack</a> four winds casino <a href="https://onlinecasinoplayusa.us.org/">hollywood casino online slots</a> | https://onlinecasinoplayusa.us.org/ - rivers casino https://onlinecasinoplayusa.us.org/ - royal river casino

goassyliaibia2018/08/01 01:33online casino real money <a href="https://onlinecasinogamesplay.us.org/">best online casinos</a> hallmark online casino <a href="https://onlinecasinogamesplay.us.org/">mystic lake casino</a> | https://onlinecasinogamesplay.us.org/ - hyper casinos https://onlinecasinogamesplay.us.org/ - gsn casino on facebook

Freergyabesty2018/08/01 01:35diet doctor <a href="https://yourdiet24.com/">diet plans</a> liquid diet <a href="https://yourdiet24.com/">apple cider vinegar diet</a> | https://yourdiet24.com/ - apple cider vinegar diet https://yourdiet24.com/ - egg diet

aspivamit2018/08/01 01:38medi weight loss clinic <a href="https://weightlosstix.com/">prescription weight loss medication</a> best weight loss program <a href="https://weightlosstix.com/">weight loss plans</a> | https://weightlosstix.com/ - best weight loss shakes https://weightlosstix.com/ - healthy lunch ideas for weight loss

ascevesaica2018/08/01 01:38keto diet plan <a href="https://ketodietix.com/">apple cider vinegar diet</a> diverticulitis diet <a href="https://ketodietix.com/">anti inflammatory diet</a> | https://ketodietix.com/ - ketone diet https://ketodietix.com/ - hcg diet

Hoalloffpleaway2018/08/01 01:38online gambling casino <a href="https://bestonlinecasino.gb.net/">choctaw casino</a> doubledown casino facebook <a href="https://bestonlinecasino.gb.net/">huge casino slots</a> | https://bestonlinecasino.gb.net/ - free online casino https://bestonlinecasino.gb.net/ - posh casino online

BladeBlersnap2018/08/01 01:39online casino gambling <a href="https://onlinecasinopalm.com/">chinook winds casino</a> casinos in iowa <a href="https://onlinecasinopalm.com/">doubledown casino</a> | https://onlinecasinopalm.com/ - hollywood casino play4fun https://onlinecasinopalm.com/ - casinos online

Freergyabesty2018/08/01 01:39vegas world casino games <a href="https://onlinecasinoassist.com/">resorts online casino nj</a> online casinos for us players <a href="https://onlinecasinoassist.com/">penny slots</a> | https://onlinecasinoassist.com/ - posh casino https://onlinecasinoassist.com/ - cherokee casino

Pearacagelp2018/08/01 01:42weight loss shakes <a href="https://weightlossy24.com/">unexplained weight loss</a> healthy smoothies for weight loss <a href="https://weightlossy24.com/">weight loss shakes</a> | https://weightlossy24.com/ - weight loss meal plan https://weightlossy24.com/ - beth chapman weight loss

ArcareappedgE2018/08/01 01:43free casino slot games <a href="https://onlinecasinoslotsy.us.org/">slot games</a> slots games <a href="https://onlinecasinoslotsy.us.org/">gsn casino slots</a> | https://onlinecasinoslotsy.us.org/ - free online slots games https://onlinecasinoslotsy.us.org/ - slot games

Cevetsunemnisee2018/08/01 01:48online slot machines <a href="https://unitedonlinecasino.gb.net/">online casino no deposit bonus</a> ilani casino <a href="https://unitedonlinecasino.gb.net/">slots casino games</a> | https://unitedonlinecasino.gb.net/ - hollywood casino online slots https://unitedonlinecasino.gb.net/ - play casino

IrogsgeageSoaph2018/08/01 22:25foxwoods online casino <a href="https://onlinecasinokle.com/">casino online slots</a> casino games | https://onlinecasinokle.com/ - casino online slots

2012-09-01

Scapegoat Tree

09:51

// Scapegoat Tree
// - insert  : O(log n) amortized !!don't insert same key!!
// - remove  : O(log n) amortized
// - find_key: O(log n) 
//
const int MAXSIZE = 1000;
int N = 1;
int ch[2][MAXSIZE];
int key[MAXSIZE];
int ndel, del[MAXSIZE];
int size[MAXSIZE], ht[MAXSIZE]; // including 'deleted' node
int update(int i) {
  if (!i) return i;
  size[i] = 1 + size[ch[0][i]] + size[ch[1][i]];
  ht[i]   = 1 + max(ht[ch[0][i]], ht[ch[1][i]]);
  return i;
}
int newnode(int k) {
  key[N] = k;
  ch[0][N] = ch[1][N] = 0;
  del[N] = 0;
  return update(N++);
}
int *flatten(int i, int *buf) {
  if (!i) return buf;
  buf = flatten(ch[0][i], buf);
  if (!del[i]) *buf++ = i;
  return flatten(ch[1][i], buf);
}
int makeBST(int *l, int *r) {
  if (r - l == 0) return 0;
  int *m = l+(r-l)/2;
  ch[0][*m] = makeBST(l, m);
  ch[1][*m] = makeBST(m+1, r);
  return update(*m);
}
int rebuild(int i) {
  static int buf[MAXSIZE];
  return makeBST(buf, flatten(i, buf));
}
const double beta = 3;
int insert(int i, int k) {
  if (!i) return newnode(k);
  int b = (k >= key[i]);
  ch[b][i] = insert(ch[b][i], k);
  update(i);
  return ht[i]>beta*log(size[i]) ? rebuild(i) : i;
}
int find_key(int i, int k) {
  if (!i || (!del[i] && k == key[i])) return i;
  return find_key(ch[k>=key[i]][i], k);
}
int remove(int i, int k) {
  del[find_key(i, k)] = 1, ++ndel;
  if (size[i] < 2*ndel) i = rebuild(i), ndel = 0;
  return i;
}

注意：上の実装は，本来の（Andersson, Galperin-Rivestの）「スケープゴート木」とは思想レベルで違いがあると思う．末尾の歴史的背景を参照．

スケープゴート木（Scapegoat Tree）は平衡二分探索木の一種．普通の平衡二分探索木は回転操作やマージ基準で平衡を保つものだけど，スケープゴート木は「平衡状態（log(木のサイズ)≒木の高さ）でなくなったら，ぶっ壊して再構築する」というアグレッシブな平衡化手法（rebuild）をとる．再構築する際にO(n)かかるので１操作あたりの最悪計算量ではO(log n)は達成できないけれど，amortized（n回の操作平均）の意味ではO(log n)を達成する．

remove: Global Rebuilding

removeではノードを検索して「削除した」というマークを張るだけで，実際にはなにもせず，検索の際はそのノードを無いものとして扱う．そして，木全体のノードの半分に「削除した」マークがついたら木全体をrebuildする．このようにバランスが崩れたら全体をまるごと作りなおすテクニックをGlobal Rebuildingという．

removeの計算量は次のように評価できる：rebuildが行われた直後から次のrebuildまでに必要なremoveの回数を数えるとn/2回．すなわちn操作するのにO(n)時間．よって１回あたりにならすとbuildがamortized定数時間となり，結局１操作あたり検索の分でO(log n)となる．

insert: Partial Rebuilding

続いてinsert．まず，Global Rebuildingは適用できないことに注意しよう．rebuild直後から考えて最小値を連続で突っ込まれると数回で平衡状態が崩れてしまうので，そのたびにGlobal Rebuildingすると amortized O(n) になってしまう．

ところがこの状況をよく見ると，全体より先に部分木で平衡が壊れている部分が現れることがわかる．そこでinsertでは「挿入した点から再帰的に平衡が壊れている点を探してそこ以下をrebuild」とする．これをPartial Rebuildingという．

insertの計算量の厳密な見積りは大変なので，雰囲気のみ示す．木全体にrebuildが行われた直後から次の全体rebuildまでに必要なinsertの回数を数える（部分木のrebuildは無視）．左の子だけに要素を挿入されるのが最悪ケースで，そのとき全体のrebuildの前に左の子のrebuildが発生するはず，と考えると，結局「左の子が一様に深くなるまで」が必要なinsertの回数になる．これはO(n)回なので，結局根に対するrebuildはamortized定数時間になる．これが全ての点について言えるので結局O(log n)が操作時間になる．

厳密な証明には，木全体が再構築される条件が本当に上で良いのかということと，１回の挿入で部分再構築が何度も起きないことを示す必要がある（前者を示せば後者は自動的に従う）．

歴史的背景

ところでスケープゴート木はAndersson(1989)とGalperin-Rivest(1993)が初出だが，非平衡データ構造を破壊と再生で平衡化するテクニックはそれよりもかなり昔から知られていて，体系的な教科書すらそれ以前に出ている（M. H. Overmars: The Design of Dynamic Data Structures, LNCS 156, 1983）．

これを踏まえてスケープゴート木の何が新しかったかというのを考えると，おそらく平衡に関する情報をノードに持たせなくてよいという情報量の問題なのだと思う（Andersson「The obtained class of trees, general balanced trees, may be maintained at a logarithmic amortized cost with no balance information stored in the nodes」，Galperin-Rivest「Scapegoat trees, unlike most balanced-tree schemes, do not require keeping extra data (e.g. “colors” or “weights”) in the tree nodes」.）

この点で，冒頭の実装は高さを陽に管理しているので，思想的にスケープゴート木ではきっと無い．本来は再帰で降りるときに高さを計算し，rebuildが発生したらその点より上でのrebuildが発生しないようにするのだが，陽に管理したほうが実装量的に楽なのでそうしている．

教科書やWeb上の解説記事ではこのあたりを区別していないものが結構見受けられるのだが，実際はどうなっているのだろう．

続く予定．

コメントを書く

spaghetti_source2012/09/06 17:02実用上は問題ないが，removedの処理がうさんくさい．flattenのときに何個削ったかを数えるのが良い．はず．