Fractional Cascading について
日本語で書かれた記事が見つからなかったのでざっくり書く
問題
vを二次元配列として、ソート済みの各配列v[i]に対してlower_boundを求めるクエリを処理する。
アルゴリズム
愚直に二分探索したら配列数をkとしてO(klog(n))となる。Fractional Cascading を用いるとO(log(n)+k)となる。
前処理をして今の二分探索の結果から次の位置を推定できるようにしていく。末尾から今探索する配列と次に探索する配列を混ぜることによって今の探索の結果から次に調べる位置が推定できるようにしていく。次の配列の全要素と混ぜると計算量が爆発するのでふたつ飛ばしに1/2個をサンプリングして混ぜる。すると混ぜるたびに半分になっていくので動的配列のときとかと同じノリで計算量が線形になる。もちろん次の正確な位置はわからなくなるのでちょっと周辺をさがす必要が出てくる。英語版wkipediaに具体例がある。
実装
参考にしたサイト
Fractional cascading - Wikipedia
あとでもうちょっと詳しくするかも
