長さ $n$ の静的な配列 $v$ に対して色々な区間クエリを高速で捌くことが出来るデータ構造． 比較的最近（2012年）開発された． Wavelet Tree のデータの持ち方を木から行列にしたことで実装を簡単にしたもの．
実装次第で捌けるクエリのバリエーションは異なるが，この勉強会では最低限のみを扱う． 末尾に追加で出来ることをいくつか記載する．
今日の講義では一貫して $\sigma \coloneqq \lfloor\log_2 \max(v)\rfloor + 1$（つまり $\max(v)$ を表す bit 長）とします． 例えば $v=[5,4,5,5,2,1,6,5,1,3,5,0]$ の場合は $\sigma = 3$．（6 は二進法で 110 なので）
ただし $v$ はあらかじめ座圧されて非負整数列になっているとする．（従って $\sigma \lesssim \log_2 n$）
座圧
WaveletMatrix(v) : $\Theta(n\sigma)$
コンストラクタ
kth_smallest(l, r, k) : $\Theta(\sigma)$ $\Theta(\sigma)$$v[l,r)$ で（0-indexed） $k$ 番目に小さい値を求める
range_freq(l, r, u) : $\Theta(\sigma)$ $\Theta(\sigma)$$v[l,r)$ で $u$ 未満の値の個数を求める
他のクエリ
長さ $n$ の静的な bit 列 $b$ に対して以下（累積和）が出来るデータ構造
rank1(r) : $\Theta(1)$
$b[0,r)$ の $1$ の個数
rank0(r) : $\Theta(1)$
$b[0,r)$ の $0$ の個数
普通に累積和をすればもちろん作れる