永続配列

data_structure/persistent_array.hpp · GitHub で見る

共通ページ

過去の配列を残したまま一点を更新します。区間積も必要なら 永続セグメント木 を使ってください。

#include "lib/data_structure/persistent_array.hpp"
#include <cassert>

int main() {
	PersistentArray<int> a(100, -1);
	auto v0 = a.initial_root();
	auto v1 = a.set(v0, 3, 10);
	auto v2 = a.set(v0, 7, 20);
	assert(a.get(v0, 3) == -1);
	assert(a.get(v1, 3) == 10 && a.get(v1, 7) == -1);
	assert(a.get(v2, 3) == -1 && a.get(v2, 7) == 20);
}

各更新は新しい root_type を返し、引数の版は変わりません。initial_root() が最初の版です。ルートをコピーするだけなら時間・追加領域ともに \(O(1)\) で、任意の過去版から分岐できます。同じオブジェクトから得たルートだけを渡してください。版ごとのノード解放は行いません。オブジェクト自体のコピーは全ノードの複製になります。

操作	内容	計算量
PersistentArray<T>(n = 0, value = T{})	長さ n、全要素 value の初期版。疎に保持する	\(O(1)\)
PersistentArray<T>(a, default_value = T{})	vector<T> から初期版を構築	\(O(n)\)
get(root,p)	版 root の位置 p の値	\(O(\log n)\)
set(root,p,x)	位置 p を x にした版	\(O(\log n)\)
set_pair(root,p,x,q,y)	p を x、q を y にした版。同じ位置なら y を使う	\(O(\log n)\)
size() / empty()	固定長／長さが 0 か	\(O(1)\)

0 <= n <= INT_MAX、0 <= p < n とします。T はコピー・代入可能な型です。デフォルト構築できない型は初期値と default_value を明示してください。default_value は内部の未作成領域の値で、配列から構築した初期版の値には影響しません。第 2 テンプレート引数 Log（既定値 3、範囲 1〜5）で分岐数を指定できます。

reserve(count) は全版を合わせたノード数を予約します。node_count() は作成済みノード数、memory_usage() は予約済みノード領域のバイト数を返します。ルートは再確保後も有効です。値のコピー・演算は定数時間とします。更新の時間には領域確保の償却計算量を含みます。

構築は長さ指定なら \(O(1)\)、配列指定なら \(O(n)\)、取得・更新は \(O(\log n)\) 時間です。更新ごとの追加領域は \(O(\log n)\) です。長さ 0・1 の操作は定数時間です。

検証コード

• test/persistent_union_find.test.cpp

コード

#ifndef PERSISTENT_ARRAY_HPP
#define PERSISTENT_ARRAY_HPP

#include <array>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <utility>
#include <vector>

template <class T, int Log = 3>
class PersistentArray {
	static_assert(1 <= Log && Log <= 5);
  public:
	using value_type = T;
	using root_type = std::uint32_t;
  private:
	struct Node { T value; std::array<root_type, 1 << Log> child{}; };
	int n_;
	root_type initial_ = 0;
	std::vector<Node> nodes;
	root_type make(Node node) {
		assert(nodes.size() < std::numeric_limits<root_type>::max());
		auto result = static_cast<root_type>(nodes.size());
		nodes.push_back(std::move(node));
		return result;
	}
	root_type clone(root_type root) {
		assert(nodes.size() < std::numeric_limits<root_type>::max());
		auto result = static_cast<root_type>(nodes.size());
		nodes.push_back(nodes[root]);
		return result;
	}
	root_type update(root_type root, unsigned p, T value) {
		if (!p) return make({std::move(value), nodes[root].child});
		auto result = clone(root), current = result;
		while (p) {
			unsigned d = p & ((1 << Log) - 1);
			p >>= Log;
			auto old = nodes[current].child[d];
			auto next = p ? clone(old) : make({std::move(value), nodes[old].child});
			nodes[current].child[d] = next;
			current = next;
		}
		return result;
	}
	root_type update_pair(root_type root, unsigned p, T a, unsigned q, T b) {
		if (p == q) return update(root, q, std::move(b));
		auto result = clone(root), current = result;
		while (p && q && (p & ((1 << Log) - 1)) == (q & ((1 << Log) - 1))) {
			unsigned d = p & ((1 << Log) - 1);
			p >>= Log, q >>= Log;
			auto next = clone(nodes[current].child[d]);
			nodes[current].child[d] = next;
			current = next;
		}
		if (!p) nodes[current].value = std::move(a);
		else {
			unsigned d = p & ((1 << Log) - 1);
			auto next = update(nodes[current].child[d], p >> Log, std::move(a));
			nodes[current].child[d] = next;
		}
		if (!q) nodes[current].value = std::move(b);
		else {
			unsigned d = q & ((1 << Log) - 1);
			auto next = update(nodes[current].child[d], q >> Log, std::move(b));
			nodes[current].child[d] = next;
		}
		return result;
	}
	root_type build(const std::vector<T> &a, std::size_t p, std::size_t step) {
		Node node{a[p], {}};
		for (int d = 0; d < (1 << Log); ++d) {
			std::size_t next = p + step * d;
			if (next < a.size() && (d || step <= (a.size() - 1 - p) / (1 << Log)))
				node.child[d] = build(a, next, step * (1 << Log));
		}
		return make(std::move(node));
	}
	void check([[maybe_unused]] root_type root) const { assert(root < nodes.size()); }
  public:
	explicit PersistentArray(int n = 0, T value = T{}) : n_(n), nodes{Node{std::move(value), {}}} { assert(n >= 0); }
	explicit PersistentArray(const std::vector<T> &a, T default_value = T{}) : PersistentArray(0, std::move(default_value)) {
		assert(a.size() <= static_cast<std::size_t>(std::numeric_limits<int>::max()));
		n_ = static_cast<int>(a.size());
		if (n_) {
			std::size_t count = a.size();
			for (auto rest = (a.size() - 1) >> Log; rest; rest >>= Log) count += rest;
			reserve(count);
			initial_ = build(a, 0, 1);
		}
	}
	int size() const { return n_; }
	bool empty() const { return !n_; }
	root_type initial_root() const { return initial_; }
	T get(root_type root, int p) const {
		check(root); assert(0 <= p && p < n_);
		while (root && p) { root = nodes[root].child[p & ((1 << Log) - 1)]; p >>= Log; }
		return nodes[root].value;
	}
	root_type set(root_type root, int p, T value) {
		check(root); assert(0 <= p && p < n_);
		return update(root, static_cast<unsigned>(p), std::move(value));
	}
	root_type set_pair(root_type root, int p, T a, int q, T b) {
		check(root); assert(0 <= p && p < n_ && 0 <= q && q < n_);
		return update_pair(root, static_cast<unsigned>(p), std::move(a), static_cast<unsigned>(q), std::move(b));
	}
	void reserve(std::size_t count) { assert(count < std::numeric_limits<root_type>::max()); nodes.reserve(count + 1); }
	std::size_t node_count() const { return nodes.size() - 1; }
	std::size_t memory_usage() const { return nodes.capacity() * sizeof(Node); }
};

#endif

Back to top page