簡潔ビットベクトル
(DataStructure/SuccintBitVector.hpp)

• View this file on GitHub
• Last update: 2021-03-01 23:06:36+09:00
• Include: #include "DataStructure/SuccintBitVector.hpp"
• Link: https://tkmst201.github.io/Library/DataStructure/SuccintBitVector.hpp

概要

ビット列を扱うデータ構造です。
長さ $N$ のビット列に対し事前計算 $\Theta(N)$ で、ある位置までに存在する $1$ (または $0$ ) の個数を $\Theta(1)$ 、先頭から $i$ 番目の $1$ (または $0$ ) の位置を $\mathcal{O}(\log{N})$ で求めることができます。

• SuccintBitVector(size_t n)
  • $\Theta(n)$ 要素数 $n$ で初期化
• SuccintBitVector(const std::vector<uint8> & bits)
  • $\Theta(|$bits$|)$ ビット列 bits で初期化
• void build()
  • 時間: $\Theta(N)$ 空間: $N + o(N)$ 事前計算を行う。rank、select を使用する前に呼ぶ
• size_t size()
  • $\Theta(1)$ ビット列の長さ $N$ を返す
• void set(size_t i)
  • $\Theta(1)$ $B_i = 1$
• void reset(size_t i)
  • $\Theta(1)$ $B_i = 0$
• bool access(size_t i)
  • $\Theta(1)$ $B_i$ を返す
• uint32_t rank1(size_t i)
  • $\Theta(1)$ $B_0, \ldots, B_{i-1}$ に存在する $1$ の個数を返す
• uint32_t rank0(size_t i)
  • $\Theta(1)$ $B_0, \ldots, B_{i-1}$ に存在する $0$ の個数を返す
• size_t select1(size_t k)
  • $\mathcal{O}(\log{N})$ 先頭から $k$ 番目の $1$ の位置を 1-indexed で返す。そのような位置が存在しなければ $N + 1$ を返す
• size_t select0(size_t k)
  • $\mathcal{O}(\log{N})$ 先頭から $k$ 番目の $0$ の位置を 1-indexed で返す。そのような位置が存在しなければ $N + 1$ を返す

コンストラクタ

SuccintBitVector(size_t n)

要素数 $n$ で初期化します。 はじめ、すべてのビットは $0$ です。

計算量

• $\Theta(n)$

---

SuccintBitVector(const std::vector & bits)

ビット列 bits で初期化します。

計算量

• $\Theta(|$bits$|)$

---

メンバ関数

以下、長さ $N$ のビット列 $B_0, B_1, \ldots, B_{N-1}$ を対象とします。

---

void build()

事前計算を行います。 rank 、select を呼ぶ前に必ず呼んでください。

計算量

• 時間: $\Theta(N)$
• 空間: $N + o(N)$ [bit]

---

size_t size()

ビット列の長さ $N$ を返します。

計算量

• $\Theta(1)$

---

void set(size_t i)

$B_i$ を $1$ に変更します。 build の後に呼んだ場合のその後の動作は未定義です。

制約

• $0 \leq i < N$

計算量

• $\Theta(1)$

---

void reset(size_t i)

$B_i$ を $0$ に変更します。 build の後に呼んだ場合のその後の動作は未定義です。

制約

• $0 \leq i < N$

計算量

• $\Theta(1)$

---

bool access(size_t i)

$B_i$ を返します。

制約

• $0 \leq i < N$

計算量

• $\Theta(1)$

---

uint32_t rank1(size_t i)

$B_0, \ldots, B_{i-1}$ に存在する $1$ の個数を返します。 ただし、$i = 0$ のときは $0$ を返します。

制約

• $0 \leq i \leq N$

計算量

• $\Theta(1)$

---

uint32_t rank0(size_t i)

$B_0, \ldots, B_{i-1}$ に存在する $0$ の個数を返します。 ただし、$i = 0$ のときは $0$ を返します。

制約

• $0 \leq i \leq N$

計算量

• $\Theta(1)$

---

size_t select1(size_t k)

先頭から $k$ 番目の $1$ の位置を 1-indexed で返します。 $k = 0$ または、そのような位置が存在しなければ $N + 1$ を返します。

制約

• $0 \leq k$

計算量

• $\mathcal{O}(\log{N})$

---

size_t select0(size_t k)

先頭から $k$ 番目の $0$ の位置を 1-indexed で返します。 $k = 0$ または、そのような位置が存在しなければ $N + 1$ を返します。

制約

• $0 \leq k$

計算量

• $\mathcal{O}(\log{N})$

---

使用例

#include <bits/stdc++.h>
#include "DataStructure/SuccintBitVector.hpp"
using namespace std;

int main() {
	SuccintBitVector bit(10);
	bit.set(0);
	bit.set(4);
	bit.set(6);
	bit.set(8);
	bit.set(9);
	
	cout << bit.access(9) << endl; // 1
	bit.reset(9);
	cout << bit.access(9) << endl; // 0
	bit.set(9);
	
	for (int i = 0; i < 10; ++i) cout << bit.access(i); cout << endl; // 1000101011
	
	bit.build(); // 忘れずに呼ぶ
	
	/*
		i = 0 : rank0 = 0, rank1 = 0
		i = 1 : rank0 = 0, rank1 = 1
		i = 2 : rank0 = 1, rank1 = 1
		i = 3 : rank0 = 2, rank1 = 1
		i = 4 : rank0 = 3, rank1 = 1
		i = 5 : rank0 = 3, rank1 = 2
		i = 6 : rank0 = 4, rank1 = 2
		i = 7 : rank0 = 4, rank1 = 3
		i = 8 : rank0 = 5, rank1 = 3
		i = 9 : rank0 = 5, rank1 = 4
		i = 10 : rank0 = 5, rank1 = 5
	*/
	for (int i = 0; i <= 10; ++i) cout << "i = " << i << " : rank0 = " << bit.rank0(i) << ", rank1 = " << bit.rank1(i) << endl;
	
	/*
		i = 0 : select0 = 0, select1 = 0
		i = 1 : select0 = 2, select1 = 1
		i = 2 : select0 = 3, select1 = 5
		i = 3 : select0 = 4, select1 = 7
		i = 4 : select0 = 6, select1 = 9
		i = 5 : select0 = 8, select1 = 10
		i = 6 : select0 = 11, select1 = 11
	*/
	for (int i = 0; i <= 6; ++i) cout << "i = " << i << " : select0 = " << bit.select0(i) << ", select1 = " << bit.select1(i) << endl;
}

TODO

TODO: $\Theta(1)$ rank を調べる

参考

2020/09/03: https://misteer.hatenablog.com/entry/bit-vector
2020/09/03: https://miti-7.hatenablog.com/entry/2018/04/15/155638

Required by

• Wavelet Matrix (DataStructure/WaveletMatrix.hpp)

Verified with

• Test/WaveletMatrix.next_prev_value.test.cpp
• Test/WaveletMatrix.quantile.test.cpp
• Test/WaveletMatrix.range_frequency.test.cpp
• Test/WaveletMatrix.select.range_k.test.cpp

Code

#ifndef INCLUDE_GUARD_SUCCINT_BIT_VECTOR_HPP
#define INCLUDE_GUARD_SUCCINT_BIT_VECTOR_HPP

#include <vector>
#include <cstdint>
#include <algorithm>
#include <cassert>

/**
 * @brief https://tkmst201.github.io/Library/DataStructure/SuccintBitVector.hpp
 */
struct SuccintBitVector {
	using size_type = std::size_t;
	using uint32 = std::uint32_t;
	
private:
	using uint8 = std::uint8_t;
	
	static constexpr size_type LARGE = 8;
	static constexpr size_type SMALL = 3;
	
private:
	size_type n;
	std::vector<uint8> bits;
	std::vector<uint32> large;
	std::vector<uint8> small;
	
public:
	explicit SuccintBitVector(size_type n)
		: n(n), bits(n == 0 ? 0 : ((n - 1) >> SMALL) + 1, 0u) {}
	
	explicit SuccintBitVector(const std::vector<uint8> & bits)
		: n(bits.size() << SMALL), bits(bits) {}
	
	void build() {
		large.assign(((n - 1) >> LARGE) + 1, 0);
		small.assign(((n - 1) >> SMALL) + 1, 0);
		for (uint32 i = 0, lidx = 0; i < bits.size(); i += 1u << (LARGE - SMALL), ++lidx) {
			if (lidx > 0) large[lidx] = large[lidx - 1] + small[i - 1] + pop_count(bits[i - 1]);
			small[i] = 0;
			for (uint32 j = i + 1; j < std::min<uint32>(bits.size(), i + (1u << (LARGE - SMALL))); ++j) {
				small[j] = small[j - 1] + pop_count(bits[j - 1]);
			}
		}
	}
	
	size_type size() const noexcept {
		return n;
	}
	
	void set(size_type i) noexcept {
		assert(i < n);
		bits[i >> SMALL] |= 1u << (i & ~(~0u << SMALL));
	}
	
	void reset(size_type i) noexcept {
		assert(i < n);
		bits[i >> SMALL] &= ~(1u << (i & ~(~0u << SMALL)));
	}
	
	bool access(size_type i) const noexcept {
		assert(i < n);
		return bits[i >> SMALL] >> (i & ~(~0u << SMALL)) & 1;
	}
	
	uint32 rank1(size_type i) const noexcept {
		assert(i <= n);
		if (i == 0) return 0;
		--i;
		return large[i >> LARGE] + small[i >> SMALL] + pop_count(bits[i >> SMALL] & ~(~0u << ((i & (~(~0u << SMALL))) + 1)));
	}
	
	uint32 rank0(size_type i) const noexcept {
		assert(i <= n);
		return i - rank1(i);
	}
	
	size_type select1(size_type k) const noexcept {
		if (k == 0) return size() + 1;
		uint32 l = 0, r = large.size();
		while (l + 1 < r) {
			const uint32 m = (l + r) >> 1;
			(large[m] < k ? l : r) = m;
		}
		uint32 cnt = large[l];
		l = l << (LARGE - SMALL); r = std::min<uint32>(small.size(), l + (1u << (LARGE - SMALL)));
		while (l + 1 < r) {
			const uint32 m = (l + r) >> 1;
			(cnt + small[m] < k ? l : r) = m;
		}
		cnt += small[l];
		const uint32 idx = l;
		l = 0; r = size() < l * (1u << SMALL) + 8 ? ((size() - 1) & ~(0u << SMALL)) + 1 : 8;
		if (cnt + pop_count(bits[idx] & ~(~0u << r)) < k) return size() + 1;
		while (l + 1 < r) {
			const uint32 m = (l + r) >> 1;
			(cnt + pop_count(bits[idx] & ~(~0u << m)) < k ? l : r) = m;
		}
		return (idx << SMALL) + r;
	}
	
	size_type select0(size_type k) const noexcept {
		if (k == 0) return size() + 1;
		uint32 l = 0, r = large.size();
		while (l + 1 < r) {
			const uint32 m = (l + r) >> 1;
			(m * (1 << LARGE) - large[m] < k ? l : r) = m;
		}
		uint32 cnt = l * (1 << LARGE) - large[l];
		l = l << (LARGE - SMALL); r = std::min<uint32>(small.size(), l + (1u << (LARGE - SMALL)));
		while (l + 1 < r) {
			const uint32 m = (l + r) >> 1;
			(cnt + (m & ~(~0u << (LARGE - SMALL))) * (1u << SMALL) - small[m] < k ? l : r) = m;
		}
		cnt += (l & ~(~0u << (LARGE - SMALL))) * (1u << SMALL) - small[l];
		const uint32 idx = l;
		l = 0; r = size() < l * (1u << SMALL) + 8 ? ((size() - 1) & ~(0u << SMALL)) + 1 : 8;
		if (cnt + pop_count(~bits[idx] & ~(~0u << r)) < k) return size() + 1;
		while (l + 1 < r) {
			const uint32 m = (l + r) >> 1;
			(cnt + pop_count(~bits[idx] & ~(~0u << m)) < k ? l : r) = m;
		}
		return (idx << SMALL) + r;
	}
	
private:
	static constexpr uint8 table[1u << (1u << SMALL)] {
		0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
		1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
		1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
		2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
		1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
		2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
		2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
		3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
	};
	
	static constexpr uint8 pop_count(uint8 x) noexcept {
		return table[x];
	}
};

#endif // INCLUDE_GUARD_SUCCINT_BIT_VECTOR_HPP

#line 1 "DataStructure/SuccintBitVector.hpp"



#include <vector>
#include <cstdint>
#include <algorithm>
#include <cassert>

/**
 * @brief https://tkmst201.github.io/Library/DataStructure/SuccintBitVector.hpp
 */
struct SuccintBitVector {
	using size_type = std::size_t;
	using uint32 = std::uint32_t;
	
private:
	using uint8 = std::uint8_t;
	
	static constexpr size_type LARGE = 8;
	static constexpr size_type SMALL = 3;
	
private:
	size_type n;
	std::vector<uint8> bits;
	std::vector<uint32> large;
	std::vector<uint8> small;
	
public:
	explicit SuccintBitVector(size_type n)
		: n(n), bits(n == 0 ? 0 : ((n - 1) >> SMALL) + 1, 0u) {}
	
	explicit SuccintBitVector(const std::vector<uint8> & bits)
		: n(bits.size() << SMALL), bits(bits) {}
	
	void build() {
		large.assign(((n - 1) >> LARGE) + 1, 0);
		small.assign(((n - 1) >> SMALL) + 1, 0);
		for (uint32 i = 0, lidx = 0; i < bits.size(); i += 1u << (LARGE - SMALL), ++lidx) {
			if (lidx > 0) large[lidx] = large[lidx - 1] + small[i - 1] + pop_count(bits[i - 1]);
			small[i] = 0;
			for (uint32 j = i + 1; j < std::min<uint32>(bits.size(), i + (1u << (LARGE - SMALL))); ++j) {
				small[j] = small[j - 1] + pop_count(bits[j - 1]);
			}
		}
	}
	
	size_type size() const noexcept {
		return n;
	}
	
	void set(size_type i) noexcept {
		assert(i < n);
		bits[i >> SMALL] |= 1u << (i & ~(~0u << SMALL));
	}
	
	void reset(size_type i) noexcept {
		assert(i < n);
		bits[i >> SMALL] &= ~(1u << (i & ~(~0u << SMALL)));
	}
	
	bool access(size_type i) const noexcept {
		assert(i < n);
		return bits[i >> SMALL] >> (i & ~(~0u << SMALL)) & 1;
	}
	
	uint32 rank1(size_type i) const noexcept {
		assert(i <= n);
		if (i == 0) return 0;
		--i;
		return large[i >> LARGE] + small[i >> SMALL] + pop_count(bits[i >> SMALL] & ~(~0u << ((i & (~(~0u << SMALL))) + 1)));
	}
	
	uint32 rank0(size_type i) const noexcept {
		assert(i <= n);
		return i - rank1(i);
	}
	
	size_type select1(size_type k) const noexcept {
		if (k == 0) return size() + 1;
		uint32 l = 0, r = large.size();
		while (l + 1 < r) {
			const uint32 m = (l + r) >> 1;
			(large[m] < k ? l : r) = m;
		}
		uint32 cnt = large[l];
		l = l << (LARGE - SMALL); r = std::min<uint32>(small.size(), l + (1u << (LARGE - SMALL)));
		while (l + 1 < r) {
			const uint32 m = (l + r) >> 1;
			(cnt + small[m] < k ? l : r) = m;
		}
		cnt += small[l];
		const uint32 idx = l;
		l = 0; r = size() < l * (1u << SMALL) + 8 ? ((size() - 1) & ~(0u << SMALL)) + 1 : 8;
		if (cnt + pop_count(bits[idx] & ~(~0u << r)) < k) return size() + 1;
		while (l + 1 < r) {
			const uint32 m = (l + r) >> 1;
			(cnt + pop_count(bits[idx] & ~(~0u << m)) < k ? l : r) = m;
		}
		return (idx << SMALL) + r;
	}
	
	size_type select0(size_type k) const noexcept {
		if (k == 0) return size() + 1;
		uint32 l = 0, r = large.size();
		while (l + 1 < r) {
			const uint32 m = (l + r) >> 1;
			(m * (1 << LARGE) - large[m] < k ? l : r) = m;
		}
		uint32 cnt = l * (1 << LARGE) - large[l];
		l = l << (LARGE - SMALL); r = std::min<uint32>(small.size(), l + (1u << (LARGE - SMALL)));
		while (l + 1 < r) {
			const uint32 m = (l + r) >> 1;
			(cnt + (m & ~(~0u << (LARGE - SMALL))) * (1u << SMALL) - small[m] < k ? l : r) = m;
		}
		cnt += (l & ~(~0u << (LARGE - SMALL))) * (1u << SMALL) - small[l];
		const uint32 idx = l;
		l = 0; r = size() < l * (1u << SMALL) + 8 ? ((size() - 1) & ~(0u << SMALL)) + 1 : 8;
		if (cnt + pop_count(~bits[idx] & ~(~0u << r)) < k) return size() + 1;
		while (l + 1 < r) {
			const uint32 m = (l + r) >> 1;
			(cnt + pop_count(~bits[idx] & ~(~0u << m)) < k ? l : r) = m;
		}
		return (idx << SMALL) + r;
	}
	
private:
	static constexpr uint8 table[1u << (1u << SMALL)] {
		0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
		1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
		1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
		2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
		1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
		2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
		2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
		3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
	};
	
	static constexpr uint8 pop_count(uint8 x) noexcept {
		return table[x];
	}
};

Back to top page