完備辞書 (lib/internal/internal_bit_vector.hpp)

• View this file on GitHub
• Last update: 2025-05-22 15:08:19+09:00
• Include: #include "lib/internal/internal_bit_vector.hpp"
• Link: https://ei1333.github.io/library/structure/wavelet/succinct-indexable-dictionary.hpp

Required by

• ウェーブレット行列 (lib/data_structure/compressed_wavelet_matrix.hpp)
• ウェーブレット行列 (lib/data_structure/wavelet_matrix.hpp)
• 重み付きウェーブレット行列 (lib/data_structure/wavelet_matrix_rectangle_sum.hpp)

Verified with

• test/aoj/challenge/2270.test.cpp
• test/yosupo/data_structure/range_kth_smallest.2.test.cpp
• test/yosupo/data_structure/range_kth_smallest.test.cpp
• test/yosupo/data_structure/rectangle_sum.test.cpp
• test/yosupo/data_structure/static_range_frequency.test.cpp

Code

#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 (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

#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 (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

Back to top page