ds/bit_vector.hpp

• View this file on GitHub
• Last update: 2022-12-12 13:31:49+09:00
• Include: #include "ds/bit_vector.hpp"

Required by

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

Verified with

• test/library_checker/datastructure/range_kth_smallest_wavelet.test.cpp
• test/library_checker/datastructure/range_kth_smallest_wavelet2.test.cpp
• test/library_checker/string/prefix_substring_lcs.test.cpp
• test/mytest/wavelet_matrix.test.cpp
• test/yukicoder/1332.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 {
  vc<pair<u32, u32>> dat;
  Bit_Vector(int n) { dat.assign((n + 63) >> 5, {0, 0}); }

  void set(int i) { dat[i >> 5].fi |= u32(1) << (i & 31); }

  void build() {
    FOR(i, len(dat) - 1) dat[i + 1].se = dat[i].se + popcnt(dat[i].fi);
  }

  // [0, k) 内の 1 の個数
  int rank(int k, bool f = 1) {
    auto [a, b] = dat[k >> 5];
    int ret = b + popcnt(a & ((u32(1) << (k & 31)) - 1));
    return (f ? ret : k - ret);
  }
};

#line 1 "ds/bit_vector.hpp"
struct Bit_Vector {
  vc<pair<u32, u32>> dat;
  Bit_Vector(int n) { dat.assign((n + 63) >> 5, {0, 0}); }

  void set(int i) { dat[i >> 5].fi |= u32(1) << (i & 31); }

  void build() {
    FOR(i, len(dat) - 1) dat[i + 1].se = dat[i].se + popcnt(dat[i].fi);
  }

  // [0, k) 内の 1 の個数
  int rank(int k, bool f = 1) {
    auto [a, b] = dat[k >> 5];
    int ret = b + popcnt(a & ((u32(1) << (k & 31)) - 1));
    return (f ? ret : k - ret);
  }
};

Back to top page