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.cr

Constructors

• .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

Instance Method Detail