class

NgLib::WaveletMatrix(T)

Inherits Indexable < Enumerable < Iterable < Reference < Object

非負整数列 $A$ に対して、順序に関する様々なクエリに答えます。

ジェネリクス T は #[] などでの返却値の型を指定するものであって、数列の値は非負整数でなければならないことに注意してください。

基本的には CompressedWaveletMatrix の方が高速です。

Constructors

new(values : Array(T))

非負整数列 $A$ を values によって構築します。

WaveletMatrix.new([1, 3, 2, 5])

Source

new(n : Int, & : Int32 -> T)

長さ $n$ の非負整数列 $A$ を構築します。

WaveletMatrix.new(10) { |i| (5 - i) ** 2 }

Source

Instance methods

count(range : Range(Int | Nil, Int | Nil), bound : Range(T | Nil, T | Nil)) : Int32

range の表す区間に含まれる要素の中で bound が表す範囲の値の個数を返します。

Source

count(range : Range(Int | Nil, Int | Nil), item : T)

range の表す区間に含まれる要素の中で item の個数を返します。

Source

count(item : T)

item の個数を返します。

計算量は対数オーダーです。

Source

count_less_eq(range : Range(Int | Nil, Int | Nil), upper_bound) : Int32

range の表す区間に含まれる要素のうち、upper_bound 未満の値の個数を返します。

存在しない場合は nil を返します。

Source

kth_largest(range : Range(Int | Nil, Int | Nil), kth : Int)

range の表す区間に含まれる要素のうち、kth 番目に大きい値を返します。

wm = WaveletMatrix.new([1, 3, 2, 5])
wm.kth_largest(1..2, 0) # => 3
wm.kth_largest(1..2, 1) # => 2

Source

kth_largest(kth : Int32)

kth 番目に大きい値を返します。

wm = WaveletMatrix.new([1, 3, 2, 5])
wm.kth_smallest(0) # => 5
wm.kth_smallest(1) # => 3
wm.kth_smallest(2) # => 2
wm.kth_smallest(3) # => 1

Source

kth_smallest(range : Range(Int | Nil, Int | Nil), kth : Int)

range の表す区間に含まれる要素のうち、kth 番目に小さい値を返します。

wm = WaveletMatrix.new([1, 3, 2, 5])
wm.kth_smallest(1..2, 0) # => 2
wm.kth_smallest(1..2, 1) # => 3

Source

kth_smallest(kth : Int32)

kth 番目に小さい値を返します。

wm = WaveletMatrix.new([1, 3, 2, 5])
wm.kth_smallest(0) # => 1
wm.kth_smallest(1) # => 2
wm.kth_smallest(2) # => 3
wm.kth_smallest(3) # => 5

Source

next_value(range : Range(Int | Nil, Int | Nil), lower_bound) : T | Nil

range の表す区間に含まれる要素のうち、lower_bound 以上の値の最小値を返します。

存在しない場合は nil を返します。

Source

prev_value(range : Range(Int | Nil, Int | Nil), upper_bound) : T | Nil

range の表す区間に含まれる要素のうち、upper_bound 未満の値の最大値を返します。

存在しない場合は nil を返します。

Source

size(*args, **options)

Source

size(*args, **options, &)

Source

unsafe_fetch(index : Int)

$A$ の index 番目の要素を取得します。

wm = WaveletMatrix.new([1, 3, 2, 5])
wm.unsafe_fetch(0) # => 1
wm.unsafe_fetch(1) # => 3
wm.unsafe_fetch(2) # => 2
wm.unsafe_fetch(3) # => 5

Source