完備辞書
(library/sequence/bit_dict.hpp)

• View this file on GitHub
• Last update: 2026-01-20 20:11:22+09:00
• Include: #include "library/sequence/bit_dict.hpp"

完備辞書

できること

• 01のビット列に対し、rank(1の個数計算)とselect(1の位置特定)を定数時間で行う

計算量

• access(k): $O(1)$ k番目のビットが0か1かを返す
• rank(k): $O(1)$ 範囲[0, k)内の1の個数を返す
• select(j): $O(1)$ または $O(logN)$ j番目(1-indexed)の1の位置を返す

selectについて、 $O(1)$ 実現のためには「1が100個おきにどこにあるか」を記録する別のインデックスが必要になる

使い方

// 01011 のようなビット列を構築
// 左から1, 3, 4番目を立てる
BitDict dict(100);  // 最大桁数を100で初期化
dict.set(1);
dict.set(3);
dict.set(4);
dict.build(); // set後にビルド

dict.access(3); // 1
dict.rank(4);   // 0~3文字目までの'1'の数 => 2
dict.select(2); // 2番目の'1'がある位置 => 3

Required by

• Wavelet Search Engine (library/search/binary_search/wavelet_search_engine.hpp)
• ウェーブレット行列 (library/sequence/wavelet_matrix.hpp)

Verified with

• WaveletSearchEngineのテスト (tests/search.binary_search.wavelet_search_engine.test.cpp)
• ウェーブレット行列のテスト (tests/sequence.wavelet_matrix.test.cpp)

Code

#pragma once
struct BitDict {
    using uint = uint64_t;
    int n;
    vector<uint> bit; // ビット列本体
    vector<int> sum;  // 累積和（各ワード開始時点での1の総数）
    BitDict() {}      // 空のコンストラクタ（ウェーブレット行列のvector確保用）
    // 64ビット単位で格納するため、(n/64)+1 個の要素を確保
    BitDict(int n) : n(n) { // n は扱うビット列の長さ（最大インデックス + 1）
        bit.assign((n >> 6) + 1, 0);
    }
    // k番目のビットを1にする
    void set(int k) { bit[k >> 6] |= (1ULL << (k & 63)); }
    // 累積和を構築する（setの後に必ず呼ぶ）
    void build() {
        sum.assign(bit.size() + 1, 0);
        for (int i = 0; i < (int)bit.size(); i++) {
            sum[i + 1] = sum[i] + __builtin_popcountll(bit[i]);
        }
    }
    // k番目のビットを取得
    bool access(int k) const { return (bit[k >> 6] >> (k & 63)) & 1; }
    // [0, k) 内の 1 の個数
    int rank1(int k) const {
        int idx = k >> 6;
        int offset = k & 63;
        uint mask = (1ULL << offset) - 1;
        return sum[idx] + __builtin_popcountll(bit[idx] & mask);
    }
    // [0, k) 内の 0 の個数（ウェーブレット行列で多用する）
    int rank0(int k) const { return k - rank1(k); }
    // j番目(1-indexed)の1の位置: O(log N)
    int select(int j) const {
        if (j <= 0 || j > sum.back()) return -1;
        int left = 0, right = n;
        while (right - left > 1) {
            int mid = (left + right) / 2;
            if (rank1(mid) >= j)
                right = mid;
            else
                left = mid;
        }
        return left;
    }
};

#line 2 "library/sequence/bit_dict.hpp"
struct BitDict {
    using uint = uint64_t;
    int n;
    vector<uint> bit; // ビット列本体
    vector<int> sum;  // 累積和（各ワード開始時点での1の総数）
    BitDict() {}      // 空のコンストラクタ（ウェーブレット行列のvector確保用）
    // 64ビット単位で格納するため、(n/64)+1 個の要素を確保
    BitDict(int n) : n(n) { // n は扱うビット列の長さ（最大インデックス + 1）
        bit.assign((n >> 6) + 1, 0);
    }
    // k番目のビットを1にする
    void set(int k) { bit[k >> 6] |= (1ULL << (k & 63)); }
    // 累積和を構築する（setの後に必ず呼ぶ）
    void build() {
        sum.assign(bit.size() + 1, 0);
        for (int i = 0; i < (int)bit.size(); i++) {
            sum[i + 1] = sum[i] + __builtin_popcountll(bit[i]);
        }
    }
    // k番目のビットを取得
    bool access(int k) const { return (bit[k >> 6] >> (k & 63)) & 1; }
    // [0, k) 内の 1 の個数
    int rank1(int k) const {
        int idx = k >> 6;
        int offset = k & 63;
        uint mask = (1ULL << offset) - 1;
        return sum[idx] + __builtin_popcountll(bit[idx] & mask);
    }
    // [0, k) 内の 0 の個数（ウェーブレット行列で多用する）
    int rank0(int k) const { return k - rank1(k); }
    // j番目(1-indexed)の1の位置: O(log N)
    int select(int j) const {
        if (j <= 0 || j > sum.back()) return -1;
        int left = 0, right = n;
        while (right - left > 1) {
            int mid = (left + right) / 2;
            if (rank1(mid) >= j)
                right = mid;
            else
                left = mid;
        }
        return left;
    }
};

Back to top page