cp-library
競技プログラミング用 C++ ライブラリ
更新可能ビット列の区間個数（補助部品）
components/fenwick_bitset.hpp · GitHub で見る
共通ページ
FenwickBitset(n) は長さ n の全要素が false のビット列を作ります。set(p,value) で一点を代入し、contains(p) で値、count(l,r) で半開区間 [l,r) の true の個数を返します。size() は列長です。
構築・空間は \(O(n)\)、一点代入・区間個数は \(O(\log n)\)、値の取得は \(O(1)\) です。
依存ライブラリ
コード
#ifndef FENWICK_BITSET_HPP
#define FENWICK_BITSET_HPP
#include "fenwick_sum.hpp"
#include <bit>
#include <cassert>
#include <cstdint>
#include <vector>
class FenwickBitset {
std::vector<std::uint64_t> words;
FenwickSum<int> counts;
int n = 0;
public:
explicit FenwickBitset(int size = 0) : counts(size > 0 ? (std::size_t(size) + 63) / 64 : 0), n(size) {
assert(size >= 0);
words.resize((std::size_t(size) + 63) / 64 + 1);
}
int size() const { return n; }
bool contains(int p) const {
assert(0 <= p && p < n);
return (words[p >> 6] >> (p & 63)) & 1;
}
void set(int p, bool value) {
assert(0 <= p && p < n);
std::uint64_t mask = std::uint64_t(1) << (p & 63);
if (bool(words[p >> 6] & mask) == value) return;
words[p >> 6] ^= mask;
counts.add(p >> 6, value ? 1 : -1);
}
int count(int l, int r) const {
assert(0 <= l && l <= r && r <= n);
return counts.prod(l >> 6, r >> 6)
+ std::popcount(words[r >> 6] & ((std::uint64_t(1) << (r & 63)) - 1))
- std::popcount(words[l >> 6] & ((std::uint64_t(1) << (l & 63)) - 1));
}
};
#endif
#line 1 "components/fenwick_bitset.hpp"
#line 1 "components/fenwick_sum.hpp"
#include <cassert>
#include <bit>
#include <limits>
#include <vector>
template <class T>
class FenwickSum {
std::vector<T> data;
public:
FenwickSum() = default;
explicit FenwickSum(int n) { assert(n >= 0); data.resize(n); }
explicit FenwickSum(const std::vector<T> &a) { build(a); }
void build(const std::vector<T> &a) {
assert(a.size() <= static_cast<unsigned>(std::numeric_limits<int>::max()));
data = a;
constexpr unsigned step = sizeof(T) <= 8 ? 2 : 1;
for (unsigned i = step; i <= data.size(); i += step) {
if constexpr (step == 2) data[i - 1] += data[i - 2];
unsigned p = i + (i & -i);
if (p <= data.size()) data[p - 1] += data[i - 1];
}
}
int size() const { return static_cast<int>(data.size()); }
void add(int p, const T &x) {
assert(0 <= p && p < size());
for (unsigned i = unsigned(p) + 1; i <= data.size(); i += i & -i) data[i - 1] += x;
}
void add_pair(int p, const T &x, int q, const T &y) {
assert(0 <= p && p < size() && 0 <= q && q < size());
unsigned a = unsigned(p) + 1, b = unsigned(q) + 1;
while (a != b && (a <= data.size() || b <= data.size())) {
if (a < b) data[a - 1] += x, a += a & -a;
else data[b - 1] += y, b += b & -b;
}
T both = x;
both += y;
for (; a <= data.size(); a += a & -a) data[a - 1] += both;
}
T prefix(int r) const {
assert(0 <= r && r <= size());
T result{};
for (; r; r &= r - 1) result += data[r - 1];
return result;
}
template <class Accum>
Accum prod_as(int l, int r) const {
assert(0 <= l && l <= r && r <= size());
Accum result{};
if (l == r) return result;
unsigned shared = unsigned(l) & (std::numeric_limits<unsigned>::max() << std::bit_width(unsigned(l ^ r)));
for (; unsigned(l) != shared; l &= l - 1) result -= data[l - 1];
for (; unsigned(r) != shared; r &= r - 1) result += data[r - 1];
return result;
}
T prod(int l, int r) const { return prod_as<T>(l, r); }
};
#line 7 "components/fenwick_bitset.hpp"
#include <cstdint>
#line 9 "components/fenwick_bitset.hpp"
class FenwickBitset {
std::vector<std::uint64_t> words;
FenwickSum<int> counts;
int n = 0;
public:
explicit FenwickBitset(int size = 0) : counts(size > 0 ? (std::size_t(size) + 63) / 64 : 0), n(size) {
assert(size >= 0);
words.resize((std::size_t(size) + 63) / 64 + 1);
}
int size() const { return n; }
bool contains(int p) const {
assert(0 <= p && p < n);
return (words[p >> 6] >> (p & 63)) & 1;
}
void set(int p, bool value) {
assert(0 <= p && p < n);
std::uint64_t mask = std::uint64_t(1) << (p & 63);
if (bool(words[p >> 6] & mask) == value) return;
words[p >> 6] ^= mask;
counts.add(p >> 6, value ? 1 : -1);
}
int count(int l, int r) const {
assert(0 <= l && l <= r && r <= n);
return counts.prod(l >> 6, r >> 6)
+ std::popcount(words[r >> 6] & ((std::uint64_t(1) << (r & 63)) - 1))
- std::popcount(words[l >> 6] & ((std::uint64_t(1) << (l & 63)) - 1));
}
};