ds/bit_vector.hpp

• View this file on GitHub
• Last update: 2024-08-08 19:22:51+09:00
• Include: #include "ds/bit_vector.hpp"

Required by

• ds/wavelet_matrix/wavelet_matrix.hpp
• ds/wavelet_matrix/wavelet_matrix_2d_range.hpp
• ds/wavelet_matrix/wavelet_matrix_old.hpp
• graph/ds/tree_wavelet_matrix.hpp
• string/prefix_substring_LCS.hpp

Verified with

• test/1_mytest/wavelet_matrix.test.cpp
• test/2_library_checker/data_structure/point_add_rectangle_sum_wm_abel.test.cpp
• test/2_library_checker/data_structure/point_add_rectangle_sum_wm_mono.test.cpp
• test/2_library_checker/data_structure/range_kth_smallest_wavelet.test.cpp
• test/2_library_checker/data_structure/rectangle_sum_wm.test.cpp
• test/2_library_checker/data_structure/rectangle_sum_wm_abel.test.cpp
• test/2_library_checker/string/prefix_substring_lcs.test.cpp
• test/3_yukicoder/1332.test.cpp
• test/3_yukicoder/1600_2.test.cpp
• test/3_yukicoder/1625_2.test.cpp
• test/3_yukicoder/1919_2.test.cpp
• test/3_yukicoder/2065.test.cpp
• test/3_yukicoder/2859.test.cpp
• test/3_yukicoder/919.test.cpp
• test/3_yukicoder/924.test.cpp
• test/5_atcoder/abc127f_1.test.cpp
• test/5_atcoder/abc324g.test.cpp

Code

struct Bit_Vector {
  int n;
  bool prepared = 0;
  vc<pair<u64, u32>> dat;
  Bit_Vector(int n) : n(n) { dat.assign((n + 127) >> 6, {0, 0}); }
  void set(int i) {
    assert(!prepared);
    dat[i >> 6].fi |= u64(1) << (i & 63);
  }
  void reset() {
    fill(all(dat), pair<u64, u32>{0, 0});
    prepared = 0;
  }
  void build() {
    prepared = 1;
    FOR(i, len(dat) - 1) dat[i + 1].se = dat[i].se + popcnt(dat[i].fi);
  }
  // [0, k) 内の 1 の個数
  bool operator[](int i) { return dat[i >> 6].fi >> (i & 63) & 1; }
  int count_prefix(int k, bool f = true) {
    assert(prepared);
    auto [a, b] = dat[k >> 6];
    int ret = b + popcnt(a & ((u64(1) << (k & 63)) - 1));
    return (f ? ret : k - ret);
  }
  int count(int L, int R, bool f = true) { return count_prefix(R, f) - count_prefix(L, f); }
  string to_string() {
    string ans;
    FOR(i, n) ans += '0' + (dat[i / 64].fi >> (i % 64) & 1);
    return ans;
  }
};

#line 1 "ds/bit_vector.hpp"
struct Bit_Vector {
  int n;
  bool prepared = 0;
  vc<pair<u64, u32>> dat;
  Bit_Vector(int n) : n(n) { dat.assign((n + 127) >> 6, {0, 0}); }
  void set(int i) {
    assert(!prepared);
    dat[i >> 6].fi |= u64(1) << (i & 63);
  }
  void reset() {
    fill(all(dat), pair<u64, u32>{0, 0});
    prepared = 0;
  }
  void build() {
    prepared = 1;
    FOR(i, len(dat) - 1) dat[i + 1].se = dat[i].se + popcnt(dat[i].fi);
  }
  // [0, k) 内の 1 の個数
  bool operator[](int i) { return dat[i >> 6].fi >> (i & 63) & 1; }
  int count_prefix(int k, bool f = true) {
    assert(prepared);
    auto [a, b] = dat[k >> 6];
    int ret = b + popcnt(a & ((u64(1) << (k & 63)) - 1));
    return (f ? ret : k - ret);
  }
  int count(int L, int R, bool f = true) { return count_prefix(R, f) - count_prefix(L, f); }
  string to_string() {
    string ans;
    FOR(i, n) ans += '0' + (dat[i / 64].fi >> (i % 64) & 1);
    return ans;
  }
};

Back to top page