segment tree と union find tree
早速備忘録を活用する。
今日はsegment tree と union find treeについて学んだ。
union find treeは概念的なことだけ、segment treeは実際にCodeIQというサイトのクロッシング問題で使ってみた。
segment treeの感想としては、今までは実行速度等を気にせず気ままにコーディングしていたが、実行速度の重要性をしらしめられ、その上で探索の速度を考えると素晴らしいデータ構造だなぁという感じ。
といっても実際に解いた問題では速度はあまり出ず(というかその前までで配列で解いた方のが速かった)、実際に恩恵には授かれなかったんだけども。
まぁこれは自身のコーディングやアルゴリズムの組み方に問題があるのであって、segment treeそのものはやはり素晴らしい構造である。
70万くらいの入力でも、再帰のネストは20以下くらいで収まるし。
本当素晴らしい。
union find treeはわからん。概念だけで考えると、まぁ便利なこともあるんだろうなという感じ。クラスカル法やプリム法で使うらしいが、両方まだ使ったことないのでわからん。
今度やってみよう。
以下各データ構造の持つ機能と実現方法に関してメモ
【union find tree】
ノードとノードをある条件によってツリー構造にする際、どちらかを親として、もうひとつのノードから参照出来るようにする。
1 2 3 4 5 6 7 8
とあって1 2 3と4 5 6と7 8をグループにしたい。条件は値が大きい方が子ノードとする。って時に、
1<‐2<‐3みたいな感じで*rootとかが親を指すようにして1の*rootをNULLとかにすれば実現出来る。
これによって、
1、グループの統合が楽に出来る。
2、ノード同士のグループが一緒かどうかを判定出来る。
という利点が生まれる。
一方、グループの分割とかは出来ない。
前述した繋ぎ方は単純に繋いだだけだが、いくつもノードが縦に繋がっている場合は、各ノードの*rootを一番上の*rootに書き換えることで繋ぎなおして、経路を短縮したり、長さによってランク付けをして(ノード数1ならランク1、ノード数2ならランク2)、グループを統合する際の指標に使う等の工夫が出来る。
活用法は前述したクラスカルとかプリムとかだと思う。ここはまた後日ということで。
【segment tree】
あるデータ群n[i, j]があった時、二分木の要領で分割していく。
そして、その範囲の中の最大値だったり最小値、何かしらのカウントしたいデータと範囲をノードに持たせることで、rootから値を検索した時に、一番下のノードまで行かずに途中のノードで受け止めることが出来る。
実装方法は配列で出来る。
完全二分木なので最大要素数*2-1の配列を用意し(n+n/2+n/4...=2n-1)、0をrootとして順々にノードを格納していく。
０
１ ２
３ ４ ５ ６
みたいな感じ。子ノードには2n+1と2n+2でアクセスすることが出来、親ノードには(n-1)/2でアクセス出来るため、配列だとスムーズにアクセス出来る。
なお、rootに向かってデータの範囲が広がるので、データの格納等は子ノードからrootに向かって行う。
例えば前述したツリーだと、値の格納をスタートする位置は3の段(n-1でアクセス出来る。ちなみに今回の場合だと要素数は4で配列の長さは2*4-1で7ということになる)からで、そこから(n-1)/2で上の段にアクセスして最終的にrootまでアクセスしたら終了、といった感じ。
また、範囲は半開区間で行うと良いらしい。実際に便利だとは思ったが、個人的にはきっちり範囲を区切りたいのであんまり考えたくはないが。
基本的に再帰で簡単に実装出来る。
なお、別に配列じゃなくても実装出来るとは思う。が、私が勉強した時は配列で実装されていたため、ここでは配列での実装例を挙げておく。
以上が簡単なメモ書き。もっと利点とか欠点とかあるだろうが、まだまだ勉強不足なのでこんな感じで勘弁。
ちなみに勉強時に使ったのはこれ
http://www.slideshare.net/iwiwi/ss-3578491
書いてるiwiwiさんは、プロコンの世界ではかなりすごい人で、世界で戦っている人の一人。そこまで行けるよう頑張らねば。
【追記】
segment treeの所で、ノードに範囲も持たせると書いたが、範囲をわかりやすくするために一番下の段は一から順番に並べて、ない数値の場所は0かINFにしておけば、ノードに持たせなくても再帰の引数で管理できる。
てかこっちの方が普通の使い方ぽいので、そうした方が良い気がしなくもない。
【更に追記】
追記で書いたことはむしろ必要条件。
segment treeを考える上で1~nまで並ばせないといけない。
例えば、○以上の値が出てきた回数をカウントするといったタスクの場合、範囲ごとに区分けされていることで途中の段で受け止めることが出来るが、ばらけていた場合、範囲の重複が大量発生してしまい、結局最下段まで見る必要がある。
これは普通に配列等で考えるよりも繰り返しが多くなって意味がない。
クロッシング問題で早くならなかった理由はこれだった。
また、他の注意事項として
1、ノード総数nは2のべき乗にしないと計算が合わない
これはsegment treeが完全二分木であるため。要素が9でも16として考えなくてはいけない。(この場合は配列数は2*16-1で31となる)
これ気をつけないとマジやばい。要素9とかでやると、
0
1 2
3 4 5 6
7 8 9 10 11 12 13 14
15
みたいになってしまって、9でのカウントが1のカウントが入ってるはずの場所に加算されてしまう、みたいなことになる。
2、範囲に気を付ける
「えーと1から16を見たいんだからleftを1に、rightを16にすればいいよね！」
あほ言っちゃいけない。2のべき乗で範囲を区切らないとちゃんと要素にアクセスできないため、8個の要素を見たいなら1<=x<9で1から9、16個の要素を見たいなら1<=x<17で1から17を指定しないといけない。半開区間で実装している場合は。
半開区間で処理をした方がぶっちゃけわかりやすい。前言撤回である。
再帰呼び出しの時も
saiki((left+right)/2, right);
saiki(left, (left+right)/2);
で区分けできるし。半開区間ではなく開区間でやってしまうと
saiki((left+right)/2+1, right);
saiki(left, (left+right)/2);
とか書かなきゃいけなくて実装時無駄に気を使うことになる。
まぁ普通に考えてa<=x<bとa<=x<=bだったら、前者の方が馴染みあるよね。for文とかでさ。本文書いてた時の俺は頭おかしかったんだきっと(
以上、ちゃんと実装してみて気づいた点でした。
