class

NgLib::SuccinctBitVector

Inherits Reference < Object

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

Constructors

new(n : Int)

長さ $n$ のビット列を構築します。

計算量は $O(n / 32)$ です。

Source
new(n : Int, &)

長さ $n$ のビット列を構築します。

ブロックでは $i$ 番目のビットの値を返してください。

計算量は $O(n)$ です。

Source

Instance methods

[](range : Range(Int | Nil, Int | Nil)) : UInt32

range の範囲の総和を返します。

Source
[](i) : UInt32

$i$ 番目のビットを返します。

Source
build

総和が計算できるようにデータ構造を構築します。

Source
count_ones(range : Range(Int | Nil, Int | Nil)) : Int32
Source
count_ones
Source
count_zeros(range : Range(Int | Nil, Int | Nil)) : Int32
Source
count_zeros
Source
kth_bit_index(k) : UInt32

$k$ 番目に出現する $1$ の位置を求めます。

言い換えると、$sum(i) = k$ となるような最小の $i$ を返します。

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

本当は $O(1)$ にできるらしいですが、面倒なので $O(\log{n})$ です。

Source
reset(i : Int)

左から $i$ 番目のビットを 0 にします。

計算量は $O(1)$ です。

Source
set(i : Int)

左から $i$ 番目のビットを 1 にします。

計算量は $O(1)$ です。

Source
size
Source
sum(l, r) : UInt32

$[l, r)$ の総和を返します。

Source
sum(range : Range(Int | Nil, Int | Nil))

range の範囲で総和を返します。

Source
sum(r) : UInt32

$[0, r)$ の総和を返します。

Source
sum

$[0, n)$ の総和を返します。

Source