wat-arrayはwavelet木と呼ばれるデータ構造を利用することにより、配列上の様々な処理を効率的に行うことができるC++ライブラリです。例えば、
- 任意の連続した範囲内にある最大値 /最小値 / k番目に大きい値, またそれらの出現位置、頻度
- 任意の連続した範囲内にある指定した文字cの出現回数、c未満/より大きい文字の出現回数
- 任意の文字のi番目の出現位置
といったものを求めることが全て範囲長、入力長に対して定数時間で行うことができます。
wat-array : wavelet木を利用した高速配列処理ライブラリ : Preferred Research