ウェーブレット行列(wavelet matrix) - Eating Your Own Cat Foodウェーブレット行列(wavelet matrix)の話です ウェーブレット行列 ウェーブレット行列で可能な操作 索引の構築 操作 access rank select quantile topk sum intersect ソース いろいろな人の実装 参考 ウェーブレット行列 例えば，T = [5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0] という配列があったとき，この配列の中で 7 番目に小さい値を求めたいとします． 最も単純なやり方は値をソートしてから T[7] にアクセスすることです（1-origin）． このような操作をいちいち行うことは，同様の操作を何回も繰り返し行いたいときには非効率です． ウェーブレット行列では，あらかじめ索引を作っておくことで，配列に対する様々な操作を効率的に行うことができます． ウェーブレット行列は内部で完備辞書(簡潔ビットベクトル
