Rank/Select Dictionary
(data-structure/bit_vector.hpp)

View this file on GitHub
Last update: 2024-01-08 02:22:28+09:00
Include: #include "data-structure/bit_vector.hpp"

Description

完備辞書 (fully indexable dictionary)，または rank/select 辞書は，ビット列を扱うデータ構造である．rank 操作 ($k$ 番目までの1の個数) と select 操作 ($k$ 番目の1の位置) を提供する．

本来完備辞書は簡潔データ構造であるが，この実装ではコンパクト表現を採用している．競技プログラミングにおいてはコンパクト表現で十分であることと，コンパクト表現の方が実装が簡単であり，実測では高速であったことが理由である．コンパクト表現なら単純な累積和でも同じことを実現できるが，こちらの実装の方が省メモリである．

Operations

BitVector(vector<bool> v)
- ビット列 v の完備辞書を構築する
- 時間計算量: $O(n)$
bool operator[](int k)
- $k$ 番目のビットを取得する
- 時間計算量: $O(1)$
int rank(int k)
- 区間 $[0, k)$ 中の1の数を返す
- 時間計算量: $O(1)$
int select(int k)
- rank(i) = k となる最初の $i$ を返す
- 時間計算量: $O(\log n)$

Reference

Required by

Wavelet Matrix (data-structure/wavelet_matrix.hpp)

Verified with

Code

#pragma once
#include <bit>
#include <cstdint>
#include <numeric>
#include <vector>

class BitVector {
   public:
    BitVector() = default;
    explicit BitVector(const std::vector<bool>& v) {
        const int n = v.size() / sz + 1;
        data.resize(n);
        sum.resize(n + 1);
        for (int i = 0; i < (int)v.size(); ++i)
            data[i / sz] |= v[i] << (i % sz);
        for (int i = 0; i < n; ++i)
            sum[i + 1] = sum[i] + std::popcount(data[i]);
    }

    bool operator[](int k) const { return data[k / sz] >> (k % sz) & 1; }

    int rank(int k, bool b) const {
        int mask = (1U << (k % sz)) - 1;
        int r = sum[k / sz] + std::popcount(data[k / sz] & mask);
        return b ? r : k - r;
    }

    int select(int k, bool b) const {
        int lb = 0, ub = data.size();
        while (ub - lb > 1) {
            int m = std::midpoint(lb, ub);
            if (rank(m, b) <= k)
                lb = m;
            else
                ub = m;
        }
        return lb;
    }

   private:
    static constexpr int sz = 32;

    std::vector<uint32_t> data;
    std::vector<int> sum;
};

#line 2 "data-structure/bit_vector.hpp"
#include <bit>
#include <cstdint>
#include <numeric>
#include <vector>

class BitVector {
   public:
    BitVector() = default;
    explicit BitVector(const std::vector<bool>& v) {
        const int n = v.size() / sz + 1;
        data.resize(n);
        sum.resize(n + 1);
        for (int i = 0; i < (int)v.size(); ++i)
            data[i / sz] |= v[i] << (i % sz);
        for (int i = 0; i < n; ++i)
            sum[i + 1] = sum[i] + std::popcount(data[i]);
    }

    bool operator[](int k) const { return data[k / sz] >> (k % sz) & 1; }

    int rank(int k, bool b) const {
        int mask = (1U << (k % sz)) - 1;
        int r = sum[k / sz] + std::popcount(data[k / sz] & mask);
        return b ? r : k - r;
    }

    int select(int k, bool b) const {
        int lb = 0, ub = data.size();
        while (ub - lb > 1) {
            int m = std::midpoint(lb, ub);
            if (rank(m, b) <= k)
                lb = m;
            else
                ub = m;
        }
        return lb;
    }

   private:
    static constexpr int sz = 32;

    std::vector<uint32_t> data;
    std::vector<int> sum;
};

Rank/Select Dictionary (data-structure/bit_vector.hpp)