Wavelet TreeのTop-Kの改善 - 気ままなブログWavelet Treeは強力なデータ構造ですが、ひとつどうしても気になる点があります。それは、Top-Kの列挙です。文字列本で紹介されているGreedyな方法は、結果がK件しか必要ないにもかかわらず、計算時間がけっこうかかります。他の操作は、最悪値の計算量が小さく、安心して使えるのに対して、Top-Kだけは、少し注意する必要があります。そのことは、文字列本にも書いてあって、最悪計算量も明示してあります。 その最悪計算量ですが、要素間の頻度に大きな偏りがある場合は、無断な節点を調べずに済み、計算量はO(klogσ)に近づくとあります。つまり、ある区間内の数値に偏りがあると、問題ないということです。 1 2 3 4 2 3 4 3 4 4上記のような場合だと、Top-1のクエリを発行すると、O(logσ)です。頻度に偏りがあると、Wavelet Treeの上段での見積もりがうまく機能するので
