class NgLib::SuccinctBitVector
- NgLib::SuccinctBitVector
- Reference
- Object
Overview
SuccinctBitVector は簡易ビットベクトル（簡易辞書、Succinct Indexable Dictionary）を提供するクラスです。
前計算 $O(n / 32)$ で次の操作が $O(1)$ くらいでできます。
.[i]# => $i$ 番目のビットにアクセスする （$O(1)$）.sum(r)# => $[0, r)$ にある $1$ の個数を求める （$O(1)$）.kth_bit_index(k)# => $k$ 番目に現れる $1$ の位置を求める （$O(\log{n})$）
例えばこの問題が解けます → D - Sleep Log
Defined in:
nglib/data_structure/succinct_bit_vector.crConstructors
-
.new(n : Int)
長さ $n$ のビット列を構築します。
-
.new(n : Int, &)
長さ $n$ のビット列を構築します。
Instance Method Summary
-
#[](range : Range(Int | Nil, Int | Nil)) : UInt32
rangeの範囲の総和を返します。 -
#[](i) : UInt32
$i$ 番目のビットを返します。
-
#build
総和が計算できるようにデータ構造を構築します。
- #count_ones(range : Range(Int | Nil, Int | Nil)) : Int32
- #count_ones : Int32
- #count_zeros(range : Range(Int | Nil, Int | Nil)) : Int32
- #count_zeros : Int32
-
#kth_bit_index(k) : UInt32
$k$ 番目に出現する $1$ の位置を求めます。
-
#reset(i : Int)
左から $i$ 番目のビットを 0 にします。
-
#set(i : Int)
左から $i$ 番目のビットを 1 にします。
- #size : UInt32
-
#sum(l, r) : UInt32
$[l, r)$ の総和を返します。
-
#sum(range : Range(Int | Nil, Int | Nil))
rangeの範囲で総和を返します。 -
#sum(r) : UInt32
$[0, r)$ の総和を返します。
-
#sum
$[0, n)$ の総和を返します。
Constructor Detail
長さ $n$ のビット列を構築します。
ブロックでは $i$ 番目のビットの値を返してください。
計算量は $O(n)$ です。
Instance Method Detail
def kth_bit_index(k) : UInt32
#
$k$ 番目に出現する $1$ の位置を求めます。
言い換えると、$sum(i) = k$ となるような最小の $i$ を返します。
存在しない場合は nil を返します。
本当は $O(1)$ にできるらしいですが、面倒なので $O(\log{n})$ です。