クエリ系、DP加速系でありがちな数値をデータ構造でO(N)からO(log n)、O(sqrt(n))にして解く系の問題のテクニックを纏める。
基本的なおはなし
C++のSTLにあるデータ構造で、競プロのオーダー落としによく使われてるのが、std::map, std::set, std::multiset, std::priority_queueである。これらの中身は基本的に(僕が覚えてる限り)平衡二分木である。この性質としては
1. 値の削除、挿入がO(log n)で行える。
2. 値の検索がO(log n)で行える。
2. 値の検索がO(log n)で行える。
である。この性質を使ってうまくオーダーを落とすと幸せになれる。特にatcoder 500 ~ 700くらい。
しかし、ここで注意すべき点としては、それ以外の操作は対数時間で行えないことである。
それを示す例をだす。
それを示す例をだす。
ABC 127 - F(600)
この問題は、詳細は個別ページを見ればわかるが、つまるところはクエリで値を挿入し、その中央値を調べたいということである。これを上のデータ構造で愚直にイテレータを回すとO(n)かかる。
なぜならば、二分木は値の検索、挿入、削除は対数時間で行える理由としてはたかだか数個の値しか操作しないことにある。前から数えてk個目というものは、順番を確定するために何度も探索しなおさないといけないので全く効率的ではない。(本来ならばO(n log n)かかる気がするけど、STLの実装でイテレータはO(n)で済ませてる気がする)
なぜならば、二分木は値の検索、挿入、削除は対数時間で行える理由としてはたかだか数個の値しか操作しないことにある。前から数えてk個目というものは、順番を確定するために何度も探索しなおさないといけないので全く効率的ではない。(本来ならばO(n log n)かかる気がするけど、STLの実装でイテレータはO(n)で済ませてる気がする)
これを改善する方法として、１つの値の挿入につき中央値周辺の数値はたかだか定数個しか変動しないことに着目すると、１つは半分より小さいデータのみ持つ二分木、もう１つは半分より大きいデータのみ持つ二分木を持てばよい。これならば、値の検索のO(log n)を定数解のみ行うのでオーダーを落とせる。
この問題に限らず、クエリによるデータ挿入時に、観測地点における変化する値の個数が定数的ならば、この考え方は使える。
