class NgLib:: WaveletMatrix(T)

• NgLib::WaveletMatrix(T)
• Reference
• Object

Overview

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

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

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

Included Modules

• Indexable(T)

Defined in:

Constructors

• .new (values : Array(T))

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

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

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

Instance Method Summary

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

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

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

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

• #count (item : T)

  item の個数を返します。

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

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

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

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

• #kth_largest (kth : Int32)

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

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

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

• #kth_smallest (kth : Int32)

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

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

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

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

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

• #size (*args, **options)
• #size (*args, **options, &)
• #unsafe_fetch (index : Int)

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

Constructor Detail

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

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

Instance Method Detail

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

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

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

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

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