Struct nekolib::ds::rs_dict::RsDict

pub struct RsDict { /* private fields */ }

rank/select 辞書。

要素が 0/1 からなる配列で、任意区間の 0/1 の個数を数えられる。

Idea

要素数 $n$ のビット配列に対して、rank/select のクエリはそれぞれ $n+1$ 通りしかないので、それらを $O(n)$ 時間で前計算しておけば、$3n+O(1)$ words で $O(1)$ query time を実現できる¹。

しかし、wavelet matrix などに用いる際はこれを 64 本持ったりする必要があることから、 空間を削減できた方がうれしそうなので、$6n/w+O(1)$ words, $O(\log(w))$ query time の方法を用いた²。

rank については、$w$ bits ごとに求めた個数の累積和 ($n/w$ words) を用いる。 端数については word size の popcount を行う³。

select については 0 と 1 に対して用意する必要があり、以下では 1 のみ述べるが、 0 についても mutatis mutandis でできる。 まず、1 の $w$ 個おきの出現箇所を求める (at most $n/w$ words)。このうち、幅が $w^2$ 以上であるものを “疎” と呼び、そうでないところを “密” と呼ぶ。 疎である区間は高々 $n/w^2$ 個しかないので、その出現位置を陽に持っても $n/w$ words で抑えられる。また、密である区間については、区間幅が $w^2$ 未満なので、 クエリごとに二分探索しても $\log(w)$ time で抑えられる。

Complexity

$O(n)$ preprocess, $O(n/w)$ space, $O(\log(w))$ query time.

---

1. $\mathtt{rank}_1$ の結果から $\mathtt{rank}_0$ の結果を求めることは可能だが、 $\mathtt{select}_1$ の結果から $\mathtt{select}_0$ の結果を求めることはできない。 ↩

2. やや複雑なので、もしかすると愚直の方がよい可能性もあるかも？ 実測しましょう。 ↩

3. $O(\log(w))$ time の方法は実装していません。.count_ones() の実測が遅いようなら考えます。ここを $O(1)$ time と見なしていいかはわかりません。 簡潔データ構造の文脈では、「どうせ表引きできるので…」となっていそうです。 ↩

Implementations

impl RsDict

pub fn rank(&self, end: usize, x: u64) -> usize

pub fn select(&self, x: u64, k: usize) -> Option<usize>

Trait Implementations

impl Clone for RsDict

fn clone(&self) -> RsDict

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Count<u64> for RsDict

fn count(&self, r: impl RangeBounds<usize>, x: u64) -> usize

impl Debug for RsDict

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl FindNth<u64> for RsDict

fn find_nth( &self, r: impl RangeBounds<usize>, x: u64, n: usize ) -> Option<usize>

impl From<Vec<bool, Global>> for RsDict

fn from(buf: Vec<bool>) -> Self

Converts to this type from the input type.