完全永続配列
(DataStructure/PersistentArray.hpp)

View this file on GitHub
Last update: 2021-03-04 18:57:20+09:00
Include: #include "DataStructure/PersistentArray.hpp"
Link: https://tkmst201.github.io/Library/DataStructure/PersistentArray.hpp

概要

完全永続配列です。
内部を $M$ 分木、アクセスする添字を $k$ とすると、過去の任意の状態の参照を $\mathcal{O}(\log_M{k})$ 、更新を $\mathcal{O}(M \log_M{k})$ で行えます。

PersistentArray(const T & def_val = 0)
- $\Theta(1)$ 要素数無限の Array を作成
PersistentArray set(size_t k, const T & x)
- $時間/空間 \mathcal{O}(M \log_M{k})$ $A_k$ に $x$ を代入
void destructive_set(size_t k, const T & x)
- $時間/空間 \mathcal{O}(M \log_M{k})$ $A_k$ に $x$ を破壊的に代入
const T & get(size_t k)
- $\mathcal{O}(\log_M{k})$ $A_k$ を返す

コンストラクタ

保持したい値の型を $T$ とし、内部を $M$ 分木で管理します。

制約

$M > 1$

PersistentArray(const T & def_val = 0)

要素数無限の Array を作成します。初期値は def_val です。

計算量

$\Theta(1)$

メンバ関数

以下、配列 $A_0, A_1, \ldots$ を対象とします。

PersistentArray set(size_t k, const T & x)

$A_k$ に $x$ を代入した Array を返します。

制約

$0 \leq k$

時間/空間計算量

$\mathcal{O}(M \log_M{k})$

void destructive_set(size_t k, const T & x)

$A_k$ に $x$ を破壊的に代入します。 set よりも高速に動作します。
この関数を呼んだ後で同一の履歴ツリーに含まれる別の状態にアクセスしたときの動作は未定義です。

制約

$0 \leq k$

時間/空間計算量

$\mathcal{O}(M \log_M{k})$

const T & get(size_t k)

$A_k$ を返す。

制約

$0 \leq k$

計算量

$\mathcal{O}(\log_M{k})$

使用例

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

int main() {
	using pa = PersistentArray<int, 3>;
	
	pa ary1;
	cout << ary1.get(10) << endl; // 0
	
	pa ary2 = ary1.set(1, 5);
	pa ary3 = ary1.set(1, 6);
	cout << ary1.get(1) << ", " << ary2.get(1) << ", " << ary3.get(1) << endl; // 0, 5, 6
	
	pa ary4 = ary3.set(3, 7);
	cout << ary1.get(3) << ", " << ary3.get(3) << ", " << ary4.get(3) << endl; // 0, 0, 7
	
	cout << ary1.get(1) << ", " << ary3.get(1) << ", " << ary4.get(1) << endl; // 0, 6, 6
	ary4.destructive_set(1, -100);
	// undefined, undefined, -100
	cout << ary1.get(1) << ", " << ary3.get(1) << ", " << ary4.get(1) << endl;
}

解説

添字の大きさ順にノードを並べる必要はないので、添字を m 進表記したときの下の桁から見ていき要素を並べるようにしています。
これにより要素数を事前に指定する必要が無くなっています。

参考

2020/04/10: https://trap.jp/post/663/
2020/09/25: https://qiita.com/hotman78/items/9c643feae1de087e6fc5

Required by

完全永続 Union Find (DataStructure/PersistentUnionFind.hpp)

Verified with

Test/PersistentUnionFind.test.cpp

Code

#ifndef INCLUDE_GUARD_PERSISTENT_ARRAY_HPP
#define INCLUDE_GUARD_PERSISTENT_ARRAY_HPP

#include <memory>
#include <utility>

/**
 * @brief https://tkmst201.github.io/Library/DataStructure/PersistentArray.hpp
 */
template<typename T, int M>
struct PersistentArray {
	static_assert(M > 1);
	
	using value_type = T;
	using const_reference = const value_type &;
	using size_type = std::size_t;
	
private:
	struct Node;
	using sptr_type = std::shared_ptr<Node>;
	using node_ptr = Node *;
	using const_ptr = const Node *;
	struct Node {
		sptr_type childs[M];
		value_type val;
		Node(const_reference val) : val(val) {}
	};
	
private:
	sptr_type root;
	value_type def_val;
	
private:
	PersistentArray(const sptr_type & root, const_reference def_val) : root(root), def_val(def_val) {}
	
public:
	explicit PersistentArray(const_reference def_val = 0) : root(nullptr), def_val(def_val) {}
	
	PersistentArray set(size_type k, const_reference x) const {
		const_ptr node = root.get();
		sptr_type new_root = std::make_shared<Node>(k == 0 ? x : (node ? node->val : def_val));
		node_ptr new_node = new_root.get();
		for (; k > 0; k /= M) {
			const size_type m = k % M;
			if (node) {
				for (size_type i = 0; i < M; ++i) if (i != m) new_node->childs[i] = node->childs[i];
				new_node->childs[m] = std::make_shared<Node>(k < M ? x : (node->childs[m] ? node->childs[m]->val : def_val));
				node = node->childs[m].get();
			}
			else new_node->childs[m] = std::make_shared<Node>(k < M ? x : def_val);
			new_node = new_node->childs[m].get();
		}
		if (node) for (size_type i = 0; i < M; ++i) new_node->childs[i] = node->childs[i];
		return {std::move(new_root), def_val};
	}
	
	void destructive_set(size_type k, const_reference x) {
		if (!root) root = std::make_shared<Node>(k == 0 ? x : def_val);
		node_ptr node = root.get();
		for (; k >= M; k /= M) {
			const size_type m = k % M;
			if (!node->childs[m]) node->childs[m] = std::make_shared<Node>(def_val);
			node = node->childs[m].get();
		}
		if (node->childs[k]) node->childs[k]->val = x;
		else node->childs[k] = std::make_shared<Node>(x);
	}
	
	const_reference get(size_type k) const noexcept {
		const_ptr node = root.get();
		while (k > 0 && node) {
			node = node->childs[k % M].get();
			k /= M;
		}
		return k == 0 && node ? node->val : def_val;
	}
};

#endif // INCLUDE_GUARD_PERSISTENT_ARRAY_HPP

#line 1 "DataStructure/PersistentArray.hpp"



#include <memory>
#include <utility>

/**
 * @brief https://tkmst201.github.io/Library/DataStructure/PersistentArray.hpp
 */
template<typename T, int M>
struct PersistentArray {
	static_assert(M > 1);
	
	using value_type = T;
	using const_reference = const value_type &;
	using size_type = std::size_t;
	
private:
	struct Node;
	using sptr_type = std::shared_ptr<Node>;
	using node_ptr = Node *;
	using const_ptr = const Node *;
	struct Node {
		sptr_type childs[M];
		value_type val;
		Node(const_reference val) : val(val) {}
	};
	
private:
	sptr_type root;
	value_type def_val;
	
private:
	PersistentArray(const sptr_type & root, const_reference def_val) : root(root), def_val(def_val) {}
	
public:
	explicit PersistentArray(const_reference def_val = 0) : root(nullptr), def_val(def_val) {}
	
	PersistentArray set(size_type k, const_reference x) const {
		const_ptr node = root.get();
		sptr_type new_root = std::make_shared<Node>(k == 0 ? x : (node ? node->val : def_val));
		node_ptr new_node = new_root.get();
		for (; k > 0; k /= M) {
			const size_type m = k % M;
			if (node) {
				for (size_type i = 0; i < M; ++i) if (i != m) new_node->childs[i] = node->childs[i];
				new_node->childs[m] = std::make_shared<Node>(k < M ? x : (node->childs[m] ? node->childs[m]->val : def_val));
				node = node->childs[m].get();
			}
			else new_node->childs[m] = std::make_shared<Node>(k < M ? x : def_val);
			new_node = new_node->childs[m].get();
		}
		if (node) for (size_type i = 0; i < M; ++i) new_node->childs[i] = node->childs[i];
		return {std::move(new_root), def_val};
	}
	
	void destructive_set(size_type k, const_reference x) {
		if (!root) root = std::make_shared<Node>(k == 0 ? x : def_val);
		node_ptr node = root.get();
		for (; k >= M; k /= M) {
			const size_type m = k % M;
			if (!node->childs[m]) node->childs[m] = std::make_shared<Node>(def_val);
			node = node->childs[m].get();
		}
		if (node->childs[k]) node->childs[k]->val = x;
		else node->childs[k] = std::make_shared<Node>(x);
	}
	
	const_reference get(size_type k) const noexcept {
		const_ptr node = root.get();
		while (k > 0 && node) {
			node = node->childs[k % M].get();
			k /= M;
		}
		return k == 0 && node ? node->val : def_val;
	}
};

完全永続配列 (DataStructure/PersistentArray.hpp)

概要