ウェーブレット行列

Wavelet Matrix

参考

このあたり読むのが速い

実装時にわからなかった部分をメモしていく

完備辞書

ウェーブレット行列はこれを使って構成するらしいので、まずこっちから

概要

長さ$ N のビットベクトルB(:= 01な数列)に対して

access(i) : B[i]を得る $ O(1)

rank(b, i) : B[:i]のbの数を得る $ O(1)

select(b, i) : 先頭からi 番目のbの位置を得る $ O(\log N)

実装

rank(b, i)

配列Bに加えて、索引として

L : 長さlごとに、それより左の1の個数を記録

S : 長さsごとに、それより左の1の個数を記録。手前のLとの差分でメモする

P : 長さsのbitパターンとそのrankを記録。

を用意する。

$ l=(\log N)^2 、$ s = \frac{\log N}{2} とするとメモリ量がいい感じになる（Python的にはうまみ少ない？）

あとはbからL, Sのインデックスx, yを求めて、B[x*s:b] + [0]*nにあたるP[z]も求めて、足す感じで定数時間で求まる

select(b, i)

rank+二分探索でok

ぶっちゃけ全部単なる累積和として実装してしまっても良い。

S[i] := sum(B[:i])として、

access(i) : S[i+1] - S[i]

rank(b, i) : S[i] if b == 1 else (i - S[i])

select(b, i) : rank(b, x) <= iで二分探索

ウェーブレット行列

概要

長さ$ N 、最大値$ X の整数列Tに対して

access(i) : T[i]を得る $ O(\log X)

rank(b, i) : B[:i]のbの数を得る $ O(\log X)

select(b, i) : 先頭からi 番目のbの位置を得る $ O(\log X)

quantile(l, r, k) : T[l:r]のk番目に小さい数を得る$ O(\log X)

とかできる

# TODO