永続 Deque・分割連結可能な列

data_structure/persistent_deque.hpp · GitHub で見る

共通ページ

両端の追加・削除に加え、添字アクセス、一点代入、途中への挿入・削除、列の分割・連結を行います。同じ列を自分自身と連結することもできます。区間積には永続セグメント木、区間更新には永続遅延セグメント木を使います。

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

int main() {
	PersistentDeque<int> deque;
	auto v0 = deque.build({1, 2, 3});
	auto v1 = deque.push_front(v0, 0);
	auto v2 = deque.set(v0, 1, 9);
	auto [left, right] = deque.split(v1, 2);
	auto v3 = deque.concat(right, left);
	assert(deque.to_vector(v3) == (std::vector<int>{2, 3, 0, 1}));
	assert(deque.get(v0, 1) == 2 && deque.get(v2, 1) == 9);
}

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

操作	内容	計算量
`build(a)`	`vector<T>` から版を作る。初期版は引き続き空列	\(O(n)\)
`size(root)` / `empty(root)`	要素数／空か	\(O(1)\)
`get(root,p)`	位置 `p` の要素	\(O(\log n)\)
`front(root)` / `back(root)`	先頭／末尾要素。非空が必要	\(O(\log n)\)
`push_front(root,x)` / `push_back(root,x)`	先頭／末尾に追加した版	\(O(\log n)\)
`pop_front(root)` / `pop_back(root)`	先頭／末尾を削除した版。非空が必要	\(O(\log n)\)
`set(root,p,x)`	位置 `p` を置換した版	\(O(\log n)\)
`insert(root,p,x)`	位置 `p` の直前に挿入した版。末尾なら `p = size(root)`	\(O(\log n)\)
`erase(root,l,r)`	半開区間 `[l,r)` を削除した版	\(O(\log n)\)
`split(root,p)`	`[0,p)` と `[p,n)` の 2 つのルート	\(O(\log n)\)
`concat(left,right)`	2 つの版をこの順に連結した版	\(O(\log(n+m))\)
`to_vector(root)`	要素順に `vector<T>` に変換	\(O(n)\)
`node_count()`	全版で作成したノード数	\(O(1)\)

添字は 0 始まり、get・set は 0 <= p < n、split・insert は 0 <= p <= n、erase は 0 <= l <= r <= n とします。連結後も長さは INT_MAX 以下にしてください。T はデフォルト構築・コピー・代入できる型です。

構築は \(O(n)\)、各更新・分割・添字アクセスは \(O(\log n)\)、連結は \(O(\log(n+m))\) 時間です。各更新の追加領域は \(O(\log n)\)、連結では \(O(\log(n+m))\) です。時間には領域確保の償却計算量を含みます。空列・長さ 1 の操作は定数時間です。読み取りはノードを作りません。

依存ライブラリ

Persistent Rope Core

検証コード

test/persistent_deque.test.cpp

コード

#line 1 "data_structure/persistent_deque.hpp"

#line 1 "components/persistent_rope.hpp"

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

template<class T, auto weight> class PersistentRope {
	struct Node {
		std::uint64_t size;
		int left, right, height;
		T value;
	};
	std::vector<Node> nodes_{{0, 0, 0, 0, T{}}};
	int height(int v) const { return nodes_[v].height; }
	int append(Node node) {
		assert(nodes_.size() < std::size_t(std::numeric_limits<int>::max()));
		nodes_.push_back(std::move(node));
		return static_cast<int>(nodes_.size()) - 1;
	}
	int branch(int a, int b) {
		if (!a) return b;
		if (!b) return a;
		assert(size(a) <= std::numeric_limits<std::uint64_t>::max() - size(b));
		return append({size(a) + size(b), a, b, std::max(height(a), height(b)) + 1, T{}});
	}
	int balance(int a, int b) {
		if (height(a) > height(b) + 1) {
			int left = nodes_[a].left, right = nodes_[a].right;
			if (height(left) >= height(right)) return branch(left, branch(right, b));
			int middle_left = nodes_[right].left, middle_right = nodes_[right].right;
			return branch(branch(left, middle_left), branch(middle_right, b));
		}
		if (height(b) > height(a) + 1) {
			int left = nodes_[b].left, right = nodes_[b].right;
			if (height(right) >= height(left)) return branch(branch(a, left), right);
			int middle_left = nodes_[left].left, middle_right = nodes_[left].right;
			return branch(branch(a, middle_left), branch(middle_right, right));
		}
		return branch(a, b);
	}

public:
	std::uint64_t size(int v) const { return nodes_[v].size; }
	std::size_t storage_nodes() const { return nodes_.size() - 1; }
	bool leaf(int v) const { return v && !nodes_[v].left; }
	T value(int v) const { assert(leaf(v)); return nodes_[v].value; }
	int make(T value) {
		auto length = std::uint64_t(weight(value));
		assert(length);
		return append({length, 0, 0, 1, std::move(value)});
	}
	int join(int a, int b) {
		if (!a || !b) return a ? a : b;
		if (height(a) > height(b) + 1) {
			int left = nodes_[a].left, right = nodes_[a].right;
			return balance(left, join(right, b));
		}
		if (height(b) > height(a) + 1) {
			int left = nodes_[b].left, right = nodes_[b].right;
			return balance(join(a, left), right);
		}
		return branch(a, b);
	}
	int build(const std::vector<T> &values) {
		auto visit = [&](auto &&self, std::size_t l, std::size_t r) -> int {
			if (l == r) return 0;
			if (r - l == 1) return make(values[l]);
			auto m = l + (r - l) / 2;
			int a = self(self, l, m), b = self(self, m, r);
			return branch(a, b);
		};
		return visit(visit, 0, values.size());
	}
	template<class Splitter> std::pair<int, int> split(int v, std::uint64_t p, const Splitter &splitter) {
		assert(p <= size(v));
		if (!p) return {0, v};
		if (p == size(v)) return {v, 0};
		int left = nodes_[v].left, right = nodes_[v].right;
		if (!left) {
			T value = nodes_[v].value;
			auto [a, b] = splitter(value, p);
			int l = make(std::move(a)), r = make(std::move(b));
			return {l, r};
		}
		auto k = size(left);
		if (p == k) return {left, right};
		if (p < k) {
			auto [a, b] = split(left, p, splitter);
			return {a, join(b, right)};
		}
		auto [a, b] = split(right, p - k, splitter);
		return {join(left, a), b};
	}
	int replace(int v, std::uint64_t p, T value) {
		assert(p < size(v));
		int a = nodes_[v].left, b = nodes_[v].right;
		if (!a) { assert(std::uint64_t(weight(value)) == size(v)); return make(std::move(value)); }
		if (p < size(a)) a = replace(a, p, std::move(value));
		else b = replace(b, p - size(a), std::move(value));
		return branch(a, b);
	}
	template<class Splitter> int insert(int v, std::uint64_t p, T value, const Splitter &splitter) {
		assert(p <= size(v));
		if (!v) return make(std::move(value));
		int a = nodes_[v].left, b = nodes_[v].right;
		if (!a) {
			if (!p) return branch(make(std::move(value)), v);
			if (p == size(v)) return branch(v, make(std::move(value)));
			auto [left, right] = split(v, p, splitter);
			int middle = make(std::move(value));
			return join(join(left, middle), right);
		}
		if (p <= size(a)) a = insert(a, p, std::move(value), splitter);
		else b = insert(b, p - size(a), std::move(value), splitter);
		return balance(a, b);
	}
	template<class Splitter> int erase(int v, std::uint64_t l, std::uint64_t r, const Splitter &splitter) {
		assert(l <= r && r <= size(v));
		if (l == r) return v;
		if (!l && r == size(v)) return 0;
		int a = nodes_[v].left, b = nodes_[v].right;
		if (!a) {
			if (!l) return split(v, r, splitter).second;
			if (r == size(v)) return split(v, l, splitter).first;
			auto [left, rest] = split(v, l, splitter);
			int right = split(rest, r - l, splitter).second;
			return join(left, right);
		}
		auto k = size(a);
		if (r <= k) a = erase(a, l, r, splitter);
		else if (l >= k) b = erase(b, l - k, r - k, splitter);
		else {
			a = erase(a, l, k, splitter);
			b = erase(b, 0, r - k, splitter);
		}
		return join(a, b);
	}

T front(int v) const { assert(v); while (nodes_[v].left) v = nodes_[v].left; return value(v); }
	T back(int v) const { assert(v); while (nodes_[v].right) v = nodes_[v].right; return value(v); }
	std::pair<T, int> pop_front(int v) {
		assert(v);
		int left = nodes_[v].left, right = nodes_[v].right;
		if (!left) return {value(v), 0};
		auto [value, rest] = pop_front(left);
		return {std::move(value), join(rest, right)};
	}
	std::pair<int, T> pop_back(int v) {
		assert(v);
		int left = nodes_[v].left, right = nodes_[v].right;
		if (!right) return {0, value(v)};
		auto [rest, value] = pop_back(right);
		return {join(left, rest), std::move(value)};
	}
	std::pair<T, std::uint64_t> at(int v, std::uint64_t p) const {
		assert(p < size(v));
		while (int left = nodes_[v].left) {
			int right = nodes_[v].right;
			auto length = size(left);
			if (p < length) v = left;
			else p -= length, v = right;
		}
		return {value(v), p};
	}
	template<class Visitor> void for_each(int v, const Visitor &visitor) const {
		if (!v) return;
		if (leaf(v)) { visitor(value(v)); return; }
		for_each(nodes_[v].left, visitor);
		for_each(nodes_[v].right, visitor);
	}
	int copy_from(const PersistentRope &other, int root) {
		assert(this != &other);
		std::vector<int> mapped(other.nodes_.size(), 0);
		auto visit = [&](auto &&self, int v) -> int {
			if (!v || mapped[v]) return mapped[v];
			auto x = other.nodes_[v];
			if (x.left) {
				x.left = self(self, x.left);
				x.right = self(self, x.right);
			}
			return mapped[v] = append(std::move(x));
		};
		return visit(visit, root);
	}
};

#line 6 "data_structure/persistent_deque.hpp"
#include <cstddef>
#line 10 "data_structure/persistent_deque.hpp"

template <class T>
class PersistentDeque {
	static int weight(const T &) { return 1; }
	PersistentRope<T, weight> rope;
	void check([[maybe_unused]] int root) const { assert(0 <= root && static_cast<std::size_t>(root) <= rope.storage_nodes()); }
	static std::pair<T, T> split_value(const T &value, std::uint64_t) { assert(false); return {value, value}; }
  public:
	using value_type = T;
	using root_type = int;
	root_type initial_root() const { return 0; }
	int size(root_type root) const { check(root); assert(rope.size(root) <= std::uint64_t(std::numeric_limits<int>::max())); return static_cast<int>(rope.size(root)); }
	bool empty(root_type root) const { return size(root) == 0; }
	root_type build(const std::vector<T> &a) { assert(a.size() <= static_cast<std::size_t>(std::numeric_limits<int>::max())); return rope.build(a); }
	T get(root_type root, int p) const { assert(0 <= p && p < size(root)); return rope.at(root, p).first; }
	T front(root_type root) const { check(root); assert(!empty(root)); return rope.front(root); }
	T back(root_type root) const { check(root); assert(!empty(root)); return rope.back(root); }
	std::pair<root_type, root_type> split(root_type root, int p) {
		assert(0 <= p && p <= size(root));
		return rope.split(root, p, split_value);
	}
	root_type concat(root_type left, root_type right) {
		assert(size(left) <= std::numeric_limits<int>::max() - size(right));
		return rope.join(left, right);
	}
	root_type push_front(root_type root, T value) { return concat(rope.make(std::move(value)), root); }
	root_type push_back(root_type root, T value) { return concat(root, rope.make(std::move(value))); }
	root_type pop_front(root_type root) { check(root); assert(!empty(root)); return rope.pop_front(root).second; }
	root_type pop_back(root_type root) { check(root); assert(!empty(root)); return rope.pop_back(root).first; }
	root_type insert(root_type root, int p, T value) {
		assert(0 <= p && p <= size(root) && size(root) < std::numeric_limits<int>::max());
		return rope.insert(root, p, std::move(value), split_value);
	}
	root_type erase(root_type root, int l, int r) {
		assert(0 <= l && l <= r && r <= size(root));
		return rope.erase(root, l, r, split_value);
	}
	root_type set(root_type root, int p, T value) {
		assert(0 <= p && p < size(root));
		return rope.replace(root, p, std::move(value));
	}
	std::vector<T> to_vector(root_type root) const {
		std::vector<T> result;
		result.reserve(size(root));
		rope.for_each(root, [&](const T &x) { result.push_back(x); });
		return result;
	}
	std::size_t node_count() const { return rope.storage_nodes(); }
};

#ifndef PERSISTENT_DEQUE_HPP
#define PERSISTENT_DEQUE_HPP

#include "../components/persistent_rope.hpp"
#include <cassert>
#include <cstddef>
#include <limits>
#include <utility>
#include <vector>

template <class T>
class PersistentDeque {
	static int weight(const T &) { return 1; }
	PersistentRope<T, weight> rope;
	void check([[maybe_unused]] int root) const { assert(0 <= root && static_cast<std::size_t>(root) <= rope.storage_nodes()); }
	static std::pair<T, T> split_value(const T &value, std::uint64_t) { assert(false); return {value, value}; }
  public:
	using value_type = T;
	using root_type = int;
	root_type initial_root() const { return 0; }
	int size(root_type root) const { check(root); assert(rope.size(root) <= std::uint64_t(std::numeric_limits<int>::max())); return static_cast<int>(rope.size(root)); }
	bool empty(root_type root) const { return size(root) == 0; }
	root_type build(const std::vector<T> &a) { assert(a.size() <= static_cast<std::size_t>(std::numeric_limits<int>::max())); return rope.build(a); }
	T get(root_type root, int p) const { assert(0 <= p && p < size(root)); return rope.at(root, p).first; }
	T front(root_type root) const { check(root); assert(!empty(root)); return rope.front(root); }
	T back(root_type root) const { check(root); assert(!empty(root)); return rope.back(root); }
	std::pair<root_type, root_type> split(root_type root, int p) {
		assert(0 <= p && p <= size(root));
		return rope.split(root, p, split_value);
	}
	root_type concat(root_type left, root_type right) {
		assert(size(left) <= std::numeric_limits<int>::max() - size(right));
		return rope.join(left, right);
	}
	root_type push_front(root_type root, T value) { return concat(rope.make(std::move(value)), root); }
	root_type push_back(root_type root, T value) { return concat(root, rope.make(std::move(value))); }
	root_type pop_front(root_type root) { check(root); assert(!empty(root)); return rope.pop_front(root).second; }
	root_type pop_back(root_type root) { check(root); assert(!empty(root)); return rope.pop_back(root).first; }
	root_type insert(root_type root, int p, T value) {
		assert(0 <= p && p <= size(root) && size(root) < std::numeric_limits<int>::max());
		return rope.insert(root, p, std::move(value), split_value);
	}
	root_type erase(root_type root, int l, int r) {
		assert(0 <= l && l <= r && r <= size(root));
		return rope.erase(root, l, r, split_value);
	}
	root_type set(root_type root, int p, T value) {
		assert(0 <= p && p < size(root));
		return rope.replace(root, p, std::move(value));
	}
	std::vector<T> to_vector(root_type root) const {
		std::vector<T> result;
		result.reserve(size(root));
		rope.for_each(root, [&](const T &x) { result.push_back(x); });
		return result;
	}
	std::size_t node_count() const { return rope.storage_nodes(); }
};

#endif

#line 1 "data_structure/persistent_deque.hpp"



#line 1 "components/persistent_rope.hpp"



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

template<class T, auto weight> class PersistentRope {
	struct Node {
		std::uint64_t size;
		int left, right, height;
		T value;
	};
	std::vector<Node> nodes_{{0, 0, 0, 0, T{}}};
	int height(int v) const { return nodes_[v].height; }
	int append(Node node) {
		assert(nodes_.size() < std::size_t(std::numeric_limits<int>::max()));
		nodes_.push_back(std::move(node));
		return static_cast<int>(nodes_.size()) - 1;
	}
	int branch(int a, int b) {
		if (!a) return b;
		if (!b) return a;
		assert(size(a) <= std::numeric_limits<std::uint64_t>::max() - size(b));
		return append({size(a) + size(b), a, b, std::max(height(a), height(b)) + 1, T{}});
	}
	int balance(int a, int b) {
		if (height(a) > height(b) + 1) {
			int left = nodes_[a].left, right = nodes_[a].right;
			if (height(left) >= height(right)) return branch(left, branch(right, b));
			int middle_left = nodes_[right].left, middle_right = nodes_[right].right;
			return branch(branch(left, middle_left), branch(middle_right, b));
		}
		if (height(b) > height(a) + 1) {
			int left = nodes_[b].left, right = nodes_[b].right;
			if (height(right) >= height(left)) return branch(branch(a, left), right);
			int middle_left = nodes_[left].left, middle_right = nodes_[left].right;
			return branch(branch(a, middle_left), branch(middle_right, right));
		}
		return branch(a, b);
	}

  public:
	std::uint64_t size(int v) const { return nodes_[v].size; }
	std::size_t storage_nodes() const { return nodes_.size() - 1; }
	bool leaf(int v) const { return v && !nodes_[v].left; }
	T value(int v) const { assert(leaf(v)); return nodes_[v].value; }
	int make(T value) {
		auto length = std::uint64_t(weight(value));
		assert(length);
		return append({length, 0, 0, 1, std::move(value)});
	}
	int join(int a, int b) {
		if (!a || !b) return a ? a : b;
		if (height(a) > height(b) + 1) {
			int left = nodes_[a].left, right = nodes_[a].right;
			return balance(left, join(right, b));
		}
		if (height(b) > height(a) + 1) {
			int left = nodes_[b].left, right = nodes_[b].right;
			return balance(join(a, left), right);
		}
		return branch(a, b);
	}
	int build(const std::vector<T> &values) {
		auto visit = [&](auto &&self, std::size_t l, std::size_t r) -> int {
			if (l == r) return 0;
			if (r - l == 1) return make(values[l]);
			auto m = l + (r - l) / 2;
			int a = self(self, l, m), b = self(self, m, r);
			return branch(a, b);
		};
		return visit(visit, 0, values.size());
	}
	template<class Splitter> std::pair<int, int> split(int v, std::uint64_t p, const Splitter &splitter) {
		assert(p <= size(v));
		if (!p) return {0, v};
		if (p == size(v)) return {v, 0};
		int left = nodes_[v].left, right = nodes_[v].right;
		if (!left) {
			T value = nodes_[v].value;
			auto [a, b] = splitter(value, p);
			int l = make(std::move(a)), r = make(std::move(b));
			return {l, r};
		}
		auto k = size(left);
		if (p == k) return {left, right};
		if (p < k) {
			auto [a, b] = split(left, p, splitter);
			return {a, join(b, right)};
		}
		auto [a, b] = split(right, p - k, splitter);
		return {join(left, a), b};
	}
	int replace(int v, std::uint64_t p, T value) {
		assert(p < size(v));
		int a = nodes_[v].left, b = nodes_[v].right;
		if (!a) { assert(std::uint64_t(weight(value)) == size(v)); return make(std::move(value)); }
		if (p < size(a)) a = replace(a, p, std::move(value));
		else b = replace(b, p - size(a), std::move(value));
		return branch(a, b);
	}
	template<class Splitter> int insert(int v, std::uint64_t p, T value, const Splitter &splitter) {
		assert(p <= size(v));
		if (!v) return make(std::move(value));
		int a = nodes_[v].left, b = nodes_[v].right;
		if (!a) {
			if (!p) return branch(make(std::move(value)), v);
			if (p == size(v)) return branch(v, make(std::move(value)));
			auto [left, right] = split(v, p, splitter);
			int middle = make(std::move(value));
			return join(join(left, middle), right);
		}
		if (p <= size(a)) a = insert(a, p, std::move(value), splitter);
		else b = insert(b, p - size(a), std::move(value), splitter);
		return balance(a, b);
	}
	template<class Splitter> int erase(int v, std::uint64_t l, std::uint64_t r, const Splitter &splitter) {
		assert(l <= r && r <= size(v));
		if (l == r) return v;
		if (!l && r == size(v)) return 0;
		int a = nodes_[v].left, b = nodes_[v].right;
		if (!a) {
			if (!l) return split(v, r, splitter).second;
			if (r == size(v)) return split(v, l, splitter).first;
			auto [left, rest] = split(v, l, splitter);
			int right = split(rest, r - l, splitter).second;
			return join(left, right);
		}
		auto k = size(a);
		if (r <= k) a = erase(a, l, r, splitter);
		else if (l >= k) b = erase(b, l - k, r - k, splitter);
		else {
			a = erase(a, l, k, splitter);
			b = erase(b, 0, r - k, splitter);
		}
		return join(a, b);
	}

	T front(int v) const { assert(v); while (nodes_[v].left) v = nodes_[v].left; return value(v); }
	T back(int v) const { assert(v); while (nodes_[v].right) v = nodes_[v].right; return value(v); }
	std::pair<T, int> pop_front(int v) {
		assert(v);
		int left = nodes_[v].left, right = nodes_[v].right;
		if (!left) return {value(v), 0};
		auto [value, rest] = pop_front(left);
		return {std::move(value), join(rest, right)};
	}
	std::pair<int, T> pop_back(int v) {
		assert(v);
		int left = nodes_[v].left, right = nodes_[v].right;
		if (!right) return {0, value(v)};
		auto [rest, value] = pop_back(right);
		return {join(left, rest), std::move(value)};
	}
	std::pair<T, std::uint64_t> at(int v, std::uint64_t p) const {
		assert(p < size(v));
		while (int left = nodes_[v].left) {
			int right = nodes_[v].right;
			auto length = size(left);
			if (p < length) v = left;
			else p -= length, v = right;
		}
		return {value(v), p};
	}
	template<class Visitor> void for_each(int v, const Visitor &visitor) const {
		if (!v) return;
		if (leaf(v)) { visitor(value(v)); return; }
		for_each(nodes_[v].left, visitor);
		for_each(nodes_[v].right, visitor);
	}
	int copy_from(const PersistentRope &other, int root) {
		assert(this != &other);
		std::vector<int> mapped(other.nodes_.size(), 0);
		auto visit = [&](auto &&self, int v) -> int {
			if (!v || mapped[v]) return mapped[v];
			auto x = other.nodes_[v];
			if (x.left) {
				x.left = self(self, x.left);
				x.right = self(self, x.right);
			}
			return mapped[v] = append(std::move(x));
		};
		return visit(visit, root);
	}
};


#line 6 "data_structure/persistent_deque.hpp"
#include <cstddef>
#line 10 "data_structure/persistent_deque.hpp"

template <class T>
class PersistentDeque {
	static int weight(const T &) { return 1; }
	PersistentRope<T, weight> rope;
	void check([[maybe_unused]] int root) const { assert(0 <= root && static_cast<std::size_t>(root) <= rope.storage_nodes()); }
	static std::pair<T, T> split_value(const T &value, std::uint64_t) { assert(false); return {value, value}; }
  public:
	using value_type = T;
	using root_type = int;
	root_type initial_root() const { return 0; }
	int size(root_type root) const { check(root); assert(rope.size(root) <= std::uint64_t(std::numeric_limits<int>::max())); return static_cast<int>(rope.size(root)); }
	bool empty(root_type root) const { return size(root) == 0; }
	root_type build(const std::vector<T> &a) { assert(a.size() <= static_cast<std::size_t>(std::numeric_limits<int>::max())); return rope.build(a); }
	T get(root_type root, int p) const { assert(0 <= p && p < size(root)); return rope.at(root, p).first; }
	T front(root_type root) const { check(root); assert(!empty(root)); return rope.front(root); }
	T back(root_type root) const { check(root); assert(!empty(root)); return rope.back(root); }
	std::pair<root_type, root_type> split(root_type root, int p) {
		assert(0 <= p && p <= size(root));
		return rope.split(root, p, split_value);
	}
	root_type concat(root_type left, root_type right) {
		assert(size(left) <= std::numeric_limits<int>::max() - size(right));
		return rope.join(left, right);
	}
	root_type push_front(root_type root, T value) { return concat(rope.make(std::move(value)), root); }
	root_type push_back(root_type root, T value) { return concat(root, rope.make(std::move(value))); }
	root_type pop_front(root_type root) { check(root); assert(!empty(root)); return rope.pop_front(root).second; }
	root_type pop_back(root_type root) { check(root); assert(!empty(root)); return rope.pop_back(root).first; }
	root_type insert(root_type root, int p, T value) {
		assert(0 <= p && p <= size(root) && size(root) < std::numeric_limits<int>::max());
		return rope.insert(root, p, std::move(value), split_value);
	}
	root_type erase(root_type root, int l, int r) {
		assert(0 <= l && l <= r && r <= size(root));
		return rope.erase(root, l, r, split_value);
	}
	root_type set(root_type root, int p, T value) {
		assert(0 <= p && p < size(root));
		return rope.replace(root, p, std::move(value));
	}
	std::vector<T> to_vector(root_type root) const {
		std::vector<T> result;
		result.reserve(size(root));
		rope.for_each(root, [&](const T &x) { result.push_back(x); });
		return result;
	}
	std::size_t node_count() const { return rope.storage_nodes(); }
};