検証済み · 最終更新 2026-07-17 · GitHub

完備辞書

lib/internal/internal_bit_vector.hpp

インクルード

#include "internal/internal_bit_vector.hpp"

内部実装

直接使うことは想定していないが、公開 API の基底として現れる。

名前	説明
`bit_vector`	完備辞書

このヘッダを使うライブラリ（3）

区間 [l, r) について sum(min(A_i, x)) / sum(max(A_i, x)) を求める lib/data_structure/range_min_max_sum.hpp
ウェーブレット行列 lib/data_structure/wavelet_matrix.hpp
キー区間に含まれる重みの総和も扱うウェーブレット行列 lib/data_structure/wavelet_matrix_rectangle_sum.hpp

検証プログラム（5）

test/aoj/challenge/2270.test.cpp test/aoj/challenge/2270.test.cpp
test/yosupo/data_structure/range_kth_smallest.test.cpp test/yosupo/data_structure/range_kth_smallest.test.cpp
test/yosupo/data_structure/rectangle_sum.test.cpp test/yosupo/data_structure/rectangle_sum.test.cpp
test/yosupo/data_structure/static_range_frequency.test.cpp test/yosupo/data_structure/static_range_frequency.test.cpp
test/yukicoder/2065.test.cpp test/yukicoder/2065.test.cpp

実装

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

namespace internal {

/// @brief 完備辞書
/// @see https://ei1333.github.io/library/structure/wavelet/succinct-indexable-dictionary.hpp
struct bit_vector {
    bit_vector() = default;
    bit_vector(unsigned int _length)
        : length(_length), blocks((_length + 31) >> 5), bit((_length + 31) >> 5), sum((_length + 31) >> 5) {}

    void set(unsigned int k) { bit[k >> 5] |= 1u << (k & 31); }

    void build() {
        sum[0] = 0;
        for (unsigned int i = 1; i < blocks; ++i) { sum[i] = sum[i - 1] + std::popcount(bit[i - 1]); }
    }

    bool operator[](unsigned int k) const { return bit[k >> 5] >> (k & 31) & 1; }

    unsigned int rank(unsigned int k) const {
        return sum[k >> 5] + std::popcount(bit[k >> 5] & ((1u << (k & 31)) - 1));
    }
    unsigned int rank(bool val, unsigned int k) const { return val ? rank(k) : k - rank(k); }

    unsigned int select(unsigned int k) const {
        unsigned int sl = 0, sr = blocks + 1;
        while (sr - sl > 1) {
            unsigned int m = (sl + sr) >> 1;
            if (sum[m] < k) sl = m;
            else sr = m;
        }
        k -= sum[sl];
        unsigned int bl = 0, br = 32;
        while (br - bl > 1) {
            unsigned int m = (bl + br) >> 1;
            if ((unsigned int)std::popcount(bit[sl] & ((1u << m) - 1)) < k) bl = m;
            else br = m;
        }
        return (sl << 5) + bl;
    }

  private:
    unsigned int length, blocks;
    std::vector<unsigned int> bit, sum;
};

}  // namespace internal

bundled

#line 2 "lib/internal/internal_bit_vector.hpp"
#include <bit>
#include <vector>

namespace internal {

/// @brief 完備辞書
/// @see https://ei1333.github.io/library/structure/wavelet/succinct-indexable-dictionary.hpp
struct bit_vector {
    bit_vector() = default;
    bit_vector(unsigned int _length)
        : length(_length), blocks((_length + 31) >> 5), bit((_length + 31) >> 5), sum((_length + 31) >> 5) {}

    void set(unsigned int k) { bit[k >> 5] |= 1u << (k & 31); }

    void build() {
        sum[0] = 0;
        for (unsigned int i = 1; i < blocks; ++i) { sum[i] = sum[i - 1] + std::popcount(bit[i - 1]); }
    }

    bool operator[](unsigned int k) const { return bit[k >> 5] >> (k & 31) & 1; }

    unsigned int rank(unsigned int k) const {
        return sum[k >> 5] + std::popcount(bit[k >> 5] & ((1u << (k & 31)) - 1));
    }
    unsigned int rank(bool val, unsigned int k) const { return val ? rank(k) : k - rank(k); }

    unsigned int select(unsigned int k) const {
        unsigned int sl = 0, sr = blocks + 1;
        while (sr - sl > 1) {
            unsigned int m = (sl + sr) >> 1;
            if (sum[m] < k) sl = m;
            else sr = m;
        }
        k -= sum[sl];
        unsigned int bl = 0, br = 32;
        while (br - bl > 1) {
            unsigned int m = (bl + br) >> 1;
            if ((unsigned int)std::popcount(bit[sl] & ((1u << m) - 1)) < k) bl = m;
            else br = m;
        }
        return (sl << 5) + bl;
    }

  private:
    unsigned int length, blocks;
    std::vector<unsigned int> bit, sum;
};

}  // namespace internal