競プロで使うビットベクトル

はじめに

JOIの春合宿で簡潔データ構造の講義があり、競プロ界隈でも簡潔データ構造の機運が高まっているため(本当か？)、競プロで便利なビットベクトルの実装について書きます。

本記事で紹介する実装では、以下の性能を実現します。

bit列の長さをNとしたとき

空間    ：6*N bit

構築    ：O(N)

access：O(1)

rank    ：O(loglogN)

select  ：O(loglogN)

簡潔(N+o(N)bit)を諦めた理由として以下が挙げられます。

１．実装が重くなる

２．空間の定数倍がきついので、10^5程度だと言うほど省メモリでない

３．時間の定数倍が重い

この記事ではcompactで効率の良い構造を目指します。

selectについて実用レベルな定数時間の実装が難しかったためO(loglogN)で妥協しましたが、上手い実装を知っている方がいらっしゃったら教えて頂きたいです。

実装

Nbit分はそのままのbit列を持ちます。これにより定数時間のaccessを実現します。

さらにNbitはrankやselectで使う累積和を持ちます。ここで注意するのは、全てのインデックスに対して累積和を持つとNlogNbit必要になってしまうことです。よって、列をlogN個づつに区切り各ブロックについて「列の先頭からそのブロックの頭までの1の数」を保持します。これによりNbitを達成します。

さて、ここまででrankがO(loglogN)で実行可能です。

累積和でブロックをはみ出さないギリギリの所まで求めた後、端数の部分をbit列に対してbitmaskとpopcountを行い計算します。popcountはO(loglogN)です。

※以下は1をselectする場合についての説明で、0もselectするためにもう2*Nbitのデータを持つ必要があります。

rankとは違い１ブロックにlogN個の１が入るように適当に分割し、それらのブロックの開始位置を配列で持ちます。ブロックは多くてもN/logN個なのでこの配列はNbitまでしか使用しません。

そして、サイズがlog^2Nを超えたブロックについてはブロック内の1の位置を単純に保持しておくことが出来ます(１つの位置を保持するのにlogNbit掛かるため)。よって、selectの際に求める場所に対応するブロックが疎ならこれを用いて計算します。

サイズがそれ以下のブロックについては、rankの際に用いた累積和のテーブルを用いて二分探索を行います。そのような密なブロックはサイズがlog^2N以下であることが保証されているので、累積和では計算できないlogNサイズのブロックに到達するまでにO(loglogN)回の計算を行い、そこからはbit演算でselectを行えばよいです。これもO(loglogN)なので全体でO(loglogN)でselectを行うことが出来ます。

いきなりrank用のテーブルで二分探索を行っても大して時間はかからない等の話はありますが、単純な計算回数なら半分程度になるので及第点でしょう。ランダムな(0,1が同程度の割合で出現する)bit列ならば二分探索の部分がほとんど不要なので、かなり高速になることが期待できます。

残念なお知らせ

競プロでビットベクトルを最もよく使うのはおそらくWaveletMatrixですが、これは基本的にrankしか使わないためselectを必死になって速くしてもあまり意味がありません(悲しい)。N=10^15が当たり前になってきたら日の目を見ることもあるかも。

実装例

つらい

どう考えてもバグっているため注意(verify用の問題が見つからず)

	#include <cassert>
	#include <cstdint>
	#include <vector>
	class BitVector {
	using uintl32 = std::uint_least32_t;
	using uint32 = std::uint_fast32_t;
	std::vector<uintl32> b, r, sh[2], sd[2];
	const uint32 size_;
	static uint32 get(const uint32 size) { return (size >> 5) + 1; }
	#ifdef __GNUC__
	static uint32 popcount32(uint32 c) { return __builtin_popcount(c); }
	#else
	static uint32 popcount32(uint32 c) {
	c = (c & 0x55555555) + (c >> 1 & 0x55555555);
	c = (c & 0x33333333) + (c >> 2 & 0x33333333);
	c = (c + (c >> 4)) & 0x0F0F0F0F;
	c += c >> 8;
	c += c >> 16;
	return c & 0x3F;
	}
	#endif
	static uint32 select32(uint32 c, uint32 k) {
	uint32 t2 = (c & 0x55555555) + (c >> 1 & 0x55555555),
	t4 = (t2 & 0x33333333) + (t2 >> 2 & 0x33333333),
	t8 = (t4 + (t4 >> 4)) & 0x0F0F0F0F,
	t16 = (t8 + (t8 >> 8)) & 0x000000FF;
	uint32 ret = 0;
	if (k >= t16) {
	k -= t16;
	ret |= 16;
	}
	t8 = t8 >> ret & 0xf;
	if (k >= t8) {
	k -= t8;
	ret |= 8;
	}
	t4 = t4 >> ret & 0x7;
	if (k >= t4) {
	k -= t4;
	ret |= 4;
	}
	t2 = t2 >> ret & 0x3;
	if (k >= t2) {
	k -= t2;
	ret |= 2;
	}
	return k >= (c >> ret & 1) ? ret + 1 : ret;
	}
	public:
	BitVector(const uint32 size)
	: b(get(size), 0),
	r(get(size), 0), sd{std::vector<uintl32>(get(size), 0),
	std::vector<uintl32>(get(size), 0)},
	size_(get(size)) {}
	void set(const uint32 index) {
	assert(index < size_ << 5);
	b[index >> 5] |= (uintl32)1 << (index & 0x1f);
	}
	void build() {
	for (uint32 i = 1; i < size_; ++i)
	r[i] = r[i - 1] + popcount32(b[i - 1]);
	for (uint32 i = 0, cnt = 0; i < size_ << 5; ++i)
	if (~b[i >> 5] >> (i & 0x1f) & 1 && !((cnt++) & 0x1f))
	sh[0].push_back(i);
	sh[0].push_back(size_ << 5);
	const uint32 s0 = sh[0].size() - 1;
	for (uint32 i = 0; i < s0; ++i) {
	const uint32 left = (sh[0][i] + 31) >> 5;
	if ((sh[0][i + 1] >> 5) - left < 32)
	continue;
	for (uint32 j = sh[0][i], cnt = 0; j < sh[0][i + 1]; ++j)
	if (~b[j >> 5] >> (j & 0x1f) & 1)
	sd[0][left + (cnt++)] = j;
	}
	for (uint32 i = 0, cnt = 0; i < size_ << 5; ++i)
	if (b[i >> 5] >> (i & 0x1f) & 1 && !((cnt++) & 0x1f))
	sh[1].push_back(i);
	sh[1].push_back(size_ << 5);
	const uint32 s1 = sh[1].size() - 1;
	for (uint32 i = 0; i < s1; ++i) {
	const uint32 left = (sh[1][i] + 31) >> 5;
	if ((sh[1][i + 1] >> 5) - left < 32)
	continue;
	for (uint32 j = sh[1][i], cnt = 0; j < sh[1][i + 1]; ++j)
	if (b[j >> 5] >> (j & 0x1f) & 1)
	sd[1][left + (cnt++)] = j;
	}
	}
	bool operator[](const uint32 index) const {
	assert(index < size_ << 5);
	return b[index >> 5] >> (index & 0x1f) & 1;
	}
	uint32 rank(const uint32 index) const {
	assert(index < size_ << 5);
	return r[index >> 5] +
	popcount32(b[index >> 5] & ((uint32)1 << (index & 0x1f)) - 1);
	}
	uint32 select(const uint32 k, const bool bit) const {
	assert(bit || k < (size_ << 5) - rank((size_ << 5) - 1));
	assert(!bit || k < rank((size_ << 5) - 1));
	const auto &head = sh[bit];
	uint32 left = head[k >> 5] + 31 >> 5, right = head[(k >> 5) + 1] >> 5;
	if (right - left >= 32)
	return sd[bit][left + (k & 0x1f)];
	left = head[k >> 5] >> 5;
	right = head[(k >> 5) + 1] + 31 >> 5;
	while (right - left != 1) {
	uint32 mid = (left + right) >> 1;
	((bit ? r[mid] : (mid << 5) - r[mid]) > k ? right : left) = mid;
	}
	return (left << 5) + select32(bit ? b[left] : ~b[left], k - r[left]);
	}
	};

view raw BitVector hosted with ❤ by GitHub