ds/bit_vector.hpp

• View this file on GitHub
• Last update: 2024-07-27 02:46:37+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/library_checker/datastructure/point_add_rectangle_sum_wm_abel.test.cpp
• test/library_checker/datastructure/point_add_rectangle_sum_wm_mono.test.cpp
• test/library_checker/datastructure/range_kth_smallest_wavelet.test.cpp
• test/library_checker/datastructure/rectangle_sum_wm.test.cpp
• test/library_checker/datastructure/rectangle_sum_wm_abel.test.cpp
• test/library_checker/string/prefix_substring_lcs.test.cpp
• test/mytest/wavelet_matrix.test.cpp
• test/yukicoder/1332.test.cpp
• test/yukicoder/1600_2.test.cpp
• test/yukicoder/1625_2.test.cpp
• test/yukicoder/1919_2.test.cpp
• test/yukicoder/2065.test.cpp
• test/yukicoder/919.test.cpp
• test/yukicoder/924.test.cpp
• test_atcoder/abc127f_1.test.cpp
• test_atcoder/abc324g.test.cpp

Code

struct Bit_Vector {
  int n;
  vc<pair<u64, u32>> dat;
  Bit_Vector(int n) : n(n) { dat.assign((n + 127) >> 6, {0, 0}); }
  void set(int i) { dat[i >> 6].fi |= u64(1) << (i & 63); }
  void reset() { fill(all(dat), pair<u64, u32>{0, 0}); }
  void build() {
    FOR(i, len(dat) - 1) dat[i + 1].se = dat[i].se + popcnt(dat[i].fi);
  }
  // [0, k) 内の 1 の個数
  int count_prefix(int k, bool f = true) {
    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;
  vc<pair<u64, u32>> dat;
  Bit_Vector(int n) : n(n) { dat.assign((n + 127) >> 6, {0, 0}); }
  void set(int i) { dat[i >> 6].fi |= u64(1) << (i & 63); }
  void reset() { fill(all(dat), pair<u64, u32>{0, 0}); }
  void build() {
    FOR(i, len(dat) - 1) dat[i + 1].se = dat[i].se + popcnt(dat[i].fi);
  }
  // [0, k) 内の 1 の個数
  int count_prefix(int k, bool f = true) {
    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