This documentation is automatically generated by online-judge-tools/verification-helper
#include "DataStructure/PersistentRedBlackTree.hpp"
完全永続赤黒木です。
可変配列を扱います。大きさ $N$ の配列の過去の任意の状態に対し、split
、 merge
、データの挿入、削除が $\mathcal{O}(\log{N})$ で行うことができます。
各操作 $\mathcal{O}(\log{N})$ の空間を消費します。
PersistentRedBlackTree()
PersistentRedBlackTree(std::vector<T> v)
v
$)$ $v$ で初期化PersistentRedBlackTree(size_t n, const T & x)
bool empty()
size_t size()
void clear()
std::vector<T> enumerate()
PersistentRedBlackTree merge(const PersistentRedBlackTree & a)
rank
$-$ a.rank
$|)$ 可変配列の末尾に a
を追加した可変配列を返すpair<PersistentRedBlackTree, PersistentRedBlackTree> split(size_t k)
PersistentRedBlackTree insert(size_t k, const T & x)
PersistentRedBlackTree erase(size_t k)
0-indexed
で $k$ 番目の要素を削除した可変配列を返すconst T & get(size_t k)
0-indexed
で $k$ 番目の要素を返す要素数 $0$ の可変配列で初期化します。
$T$ には保持したい値の型を指定します。
計算量
$v$ で初期化します。
制約
InputIterator
は Random Access Iterator
計算量
v
$)$すべての値が $x$ の要素数 $n$ の可変配列で初期化します。
制約
InputIterator
は Random Access Iterator
計算量
可変配列の要素数を $N$ とします。
根から葉までのパス上 (根含まない) にある黒ノードの個数を rank
とします。
可変配列が空なら $true$ を返します。 それ以外は $false$ を返します。
計算量
可変配列の要素数 $N$ を返します。
計算量
可変配列のすべての要素を削除します。
計算量
現在の可変配列を返します。
計算量
可変配列の末尾に a
を追加した可変配列を返します。
計算量
rank
$-$ a.rank
$|)$可変配列の先頭 $k$ 個の要素と $k + 1$ 個目の要素以降の $2$ つの可変配列に分けてこの順で返します。
制約
計算量
前に $k$ 個の要素がある位置に $x$ を挿入した可変配列を返します。
制約
計算量
先頭から 0-indexed
で $k$ 番目の要素を削除した可変配列を返します。
制約
計算量
先頭から 0-indexed
で $k$ 番目の要素を返します。
制約
計算量
#include <bits/stdc++.h>
#include "DataStructure/PersistentRedBlackTree.hpp"
using namespace std;
int main() {
PersistentRedBlackTree<int> rbt({0, 1, 2, 3, 4, 5, 6});
cout << "empty() = " << boolalpha << rbt.empty() << endl; // false
cout << "size = " << rbt.size() << endl; // 7
// 0 1 2 3 4 5 6
for (int i : rbt.enumerate()) cout << i << " "; cout << '\n';
auto rbt2 = rbt.insert(0, 100);
auto rbt3 = rbt.insert(3, 100);
auto rbt4 = rbt.insert(7, 100);
// 0 1 2 3 4 5 6
for (int i : rbt.enumerate()) cout << i << " "; cout << '\n';
// 100 0 1 2 3 4 5 6
for (int i : rbt2.enumerate()) cout << i << " "; cout << '\n';
// 0 1 2 100 3 4 5 6
for (int i : rbt3.enumerate()) cout << i << " "; cout << '\n';
// 0 1 2 3 4 5 6 100
for (int i : rbt4.enumerate()) cout << i << " "; cout << '\n';
auto rbtm = rbt3.merge(rbt4);
// 0 1 2 100 3 4 5 6 0 1 2 3 4 5 6 100
for (int i : rbtm.enumerate()) cout << i << " "; cout << '\n';
// 100 3 4 5 6 0 ( [3, 9) )
auto rbts = rbtm.split(9).first.split(3).second;
for (int i : rbts.enumerate()) cout << i << " "; cout << '\n';
cout << "get(3) = " << rbts.get(3) << endl; // 5
auto rbte = rbts.erase(3);
// 100 3 4 6 0
for (int i : rbte.enumerate()) cout << i << " "; cout << '\n';
rbt = PersistentRedBlackTree<int>();
cout << "empty() = " << boolalpha << rbt.empty() << endl; // true
// 5 5 5
for (int i : PersistentRedBlackTree<int>(3, 5).enumerate()) cout << i << " "; cout << '\n';
}
TODO: メモリプールを使って高速化
2020/08/30: https://www.ioi-jp.org/camp/2012/2012-sp-tasks/2012-sp-day4-copypaste-slides.pdf
2020/08/30: http://blog.mitaki28.info/1447078746296/
2020/08/30: http://algoogle.hadrori.jp/algorithm/rbtree_merge.html
#ifndef INCLUDE_GUARD_PERSISTENT_RED_BLACK_TREE_HPP
#define INCLUDE_GUARD_PERSISTENT_RED_BLACK_TREE_HPP
#include <cassert>
#include <memory>
#include <utility>
#include <vector>
#include <stack>
/**
* @brief https://tkmst201.github.io/Library/DataStructure/PersistentRedBlackTree.hpp
*/
template<typename T>
struct PersistentRedBlackTree {
using value_type = T;
using const_reference = const value_type &;
using size_type = std::size_t;
static constexpr bool red = true;
static constexpr bool black = false;
struct Node;
using node_ptr = std::shared_ptr<Node>;
using node_ref = const node_ptr &;
using raw_ptr = Node *;
struct Node {
value_type val;
bool color;
size_type size, rank;
node_ptr l, r;
Node(bool color, node_ref l, node_ref r)
: color(color), size(l->size + r->size), rank(l->rank + (l->color == black)), l(l), r(r) {}
Node(const_reference val) : val(val), color(black), size(1), rank(0), l(nullptr), r(nullptr) {}
};
private:
node_ptr root = nullptr;
PersistentRedBlackTree(node_ref root) : root(root) {}
static node_ptr create(bool color, node_ref l, node_ref r) {
return std::make_shared<Node>(color, l, r);
}
static node_ptr create(const_reference val) {
return std::make_shared<Node>(val);
}
public:
PersistentRedBlackTree() = default;
PersistentRedBlackTree(const std::vector<value_type> & v)
: root(v.empty() ? nullptr : build(std::begin(v), std::end(v), 30)) {}
PersistentRedBlackTree(size_type n, const_reference x)
: root(n == 0 ? nullptr : buildn(n, x, 30)) {}
bool empty() const noexcept {
return size() == 0;
}
size_type size() const noexcept {
return root ? root->size : 0;
}
void clear() {
root = nullptr;
}
std::vector<value_type> enumerate() const {
std::vector<value_type> elements;
std::stack<raw_ptr> stk;
stk.emplace(root.get());
while (!stk.empty()) {
raw_ptr q = stk.top();
stk.pop();
if (q->l) {
stk.emplace(q->r.get());
stk.emplace(q->l.get());
}
else elements.emplace_back(q->val);
}
return elements;
}
PersistentRedBlackTree merge(const PersistentRedBlackTree & a) const {
return merge(root, a.root);
}
std::pair<PersistentRedBlackTree, PersistentRedBlackTree> split(size_type k) const {
assert(k <= size());
const auto sp = split(root, k);
return {sp.first, sp.second};
}
PersistentRedBlackTree insert(size_type k, const_reference x) const {
assert(k <= size());
return insert(root, k, x);
}
PersistentRedBlackTree erase(size_type k) const {
assert(k < size());
return erase(root, k);
}
const_reference get(size_type k) const noexcept {
assert(k < size());
raw_ptr q = root.get();
while (q->l) {
if (k < q->l->size) q = (q->l).get();
else k -= q->l->size, q = (q->r).get();
}
return q->val;
}
private:
template<class InputIterator>
node_ptr build(InputIterator first, InputIterator last, int k) const {
if (first + 1 == last) return create(*first);
const auto n = last - first;
const unsigned int m = 1u << k;
if (n > m) return merge(build(first, first + m, k - 1), build(first + m, last, k - 1));
return build(first, last, k - 1);
}
node_ptr buildn(size_type n, const_reference x, int k) const {
if (n == 1) return create(x);
const unsigned int m = 1u << k;
if (n > m) return merge(buildn(m, x, k - 1), buildn(n - m, x, k - 1));
return buildn(n, x, k - 1);
}
node_ptr as_root(const node_ptr & q) const {
if (!q) return nullptr;
if (q->color == red) return create(black, q->l, q->r);
return q;
}
node_ptr merge(const node_ptr & a, const node_ptr & b) const {
if (!a) return b;
if (!b) return a;
node_ptr res = merge_sub(a, b);
res->color = black;
return res;
}
node_ptr merge_sub(const node_ptr & a, const node_ptr & b) const {
if (a->rank < b->rank) {
node_ptr c = merge_sub(a, b->l);
if (b->color == black && c->color == red && c->l->color == red) {
if (b->r->color == black) return create(black, c->l, create(red, c->r, b->r));
c->color = black;
return create(red, c, create(black, b->r->l, b->r->r));
}
return create(b->color, c, b->r);
}
else if (a->rank > b->rank) {
const node_ptr c = merge_sub(a->r, b);
if (a->color == black && c->color == red && c->r->color == red) {
if (a->l->color == black) return create(black, create(red, a->l, c->l), c->r);
c->color = black;
return create(red, create(black, a->l->l, a->l->r), c);
}
return create(a->color, a->l, c);
}
return create(red, a, b);
}
std::pair<node_ptr, node_ptr> split(const node_ptr & a, size_type k) const {
if (!a) return {nullptr, nullptr};
if (k == 0) return {nullptr, as_root(a)};
if (k == a->size) return {as_root(a), nullptr};
if (k < a->l->size) {
const auto sp = split(a->l, k);
return {as_root(sp.first), merge(sp.second, as_root(a->r))};
}
if (k > a->l->size) {
const auto sp = split(a->r, k - a->l->size);
return {merge(as_root(a->l), sp.first), as_root(sp.second)};
}
return {as_root(a->l), as_root(a->r)};
}
node_ptr insert(const node_ptr & a, size_type k, const_reference x) const {
if (!a) return create(x);
const auto sp = split(a, k);
return merge(sp.first, merge(create(x), sp.second));
}
node_ptr erase(const node_ptr & a, size_type k) const {
const auto sp = split(a, k + 1);
return merge(split(sp.first, k).first, sp.second);
}
};
#endif // INCLUDE_GUARD_PERSISTENT_RED_BLACK_TREE_HPP
#line 1 "DataStructure/PersistentRedBlackTree.hpp"
#include <cassert>
#include <memory>
#include <utility>
#include <vector>
#include <stack>
/**
* @brief https://tkmst201.github.io/Library/DataStructure/PersistentRedBlackTree.hpp
*/
template<typename T>
struct PersistentRedBlackTree {
using value_type = T;
using const_reference = const value_type &;
using size_type = std::size_t;
static constexpr bool red = true;
static constexpr bool black = false;
struct Node;
using node_ptr = std::shared_ptr<Node>;
using node_ref = const node_ptr &;
using raw_ptr = Node *;
struct Node {
value_type val;
bool color;
size_type size, rank;
node_ptr l, r;
Node(bool color, node_ref l, node_ref r)
: color(color), size(l->size + r->size), rank(l->rank + (l->color == black)), l(l), r(r) {}
Node(const_reference val) : val(val), color(black), size(1), rank(0), l(nullptr), r(nullptr) {}
};
private:
node_ptr root = nullptr;
PersistentRedBlackTree(node_ref root) : root(root) {}
static node_ptr create(bool color, node_ref l, node_ref r) {
return std::make_shared<Node>(color, l, r);
}
static node_ptr create(const_reference val) {
return std::make_shared<Node>(val);
}
public:
PersistentRedBlackTree() = default;
PersistentRedBlackTree(const std::vector<value_type> & v)
: root(v.empty() ? nullptr : build(std::begin(v), std::end(v), 30)) {}
PersistentRedBlackTree(size_type n, const_reference x)
: root(n == 0 ? nullptr : buildn(n, x, 30)) {}
bool empty() const noexcept {
return size() == 0;
}
size_type size() const noexcept {
return root ? root->size : 0;
}
void clear() {
root = nullptr;
}
std::vector<value_type> enumerate() const {
std::vector<value_type> elements;
std::stack<raw_ptr> stk;
stk.emplace(root.get());
while (!stk.empty()) {
raw_ptr q = stk.top();
stk.pop();
if (q->l) {
stk.emplace(q->r.get());
stk.emplace(q->l.get());
}
else elements.emplace_back(q->val);
}
return elements;
}
PersistentRedBlackTree merge(const PersistentRedBlackTree & a) const {
return merge(root, a.root);
}
std::pair<PersistentRedBlackTree, PersistentRedBlackTree> split(size_type k) const {
assert(k <= size());
const auto sp = split(root, k);
return {sp.first, sp.second};
}
PersistentRedBlackTree insert(size_type k, const_reference x) const {
assert(k <= size());
return insert(root, k, x);
}
PersistentRedBlackTree erase(size_type k) const {
assert(k < size());
return erase(root, k);
}
const_reference get(size_type k) const noexcept {
assert(k < size());
raw_ptr q = root.get();
while (q->l) {
if (k < q->l->size) q = (q->l).get();
else k -= q->l->size, q = (q->r).get();
}
return q->val;
}
private:
template<class InputIterator>
node_ptr build(InputIterator first, InputIterator last, int k) const {
if (first + 1 == last) return create(*first);
const auto n = last - first;
const unsigned int m = 1u << k;
if (n > m) return merge(build(first, first + m, k - 1), build(first + m, last, k - 1));
return build(first, last, k - 1);
}
node_ptr buildn(size_type n, const_reference x, int k) const {
if (n == 1) return create(x);
const unsigned int m = 1u << k;
if (n > m) return merge(buildn(m, x, k - 1), buildn(n - m, x, k - 1));
return buildn(n, x, k - 1);
}
node_ptr as_root(const node_ptr & q) const {
if (!q) return nullptr;
if (q->color == red) return create(black, q->l, q->r);
return q;
}
node_ptr merge(const node_ptr & a, const node_ptr & b) const {
if (!a) return b;
if (!b) return a;
node_ptr res = merge_sub(a, b);
res->color = black;
return res;
}
node_ptr merge_sub(const node_ptr & a, const node_ptr & b) const {
if (a->rank < b->rank) {
node_ptr c = merge_sub(a, b->l);
if (b->color == black && c->color == red && c->l->color == red) {
if (b->r->color == black) return create(black, c->l, create(red, c->r, b->r));
c->color = black;
return create(red, c, create(black, b->r->l, b->r->r));
}
return create(b->color, c, b->r);
}
else if (a->rank > b->rank) {
const node_ptr c = merge_sub(a->r, b);
if (a->color == black && c->color == red && c->r->color == red) {
if (a->l->color == black) return create(black, create(red, a->l, c->l), c->r);
c->color = black;
return create(red, create(black, a->l->l, a->l->r), c);
}
return create(a->color, a->l, c);
}
return create(red, a, b);
}
std::pair<node_ptr, node_ptr> split(const node_ptr & a, size_type k) const {
if (!a) return {nullptr, nullptr};
if (k == 0) return {nullptr, as_root(a)};
if (k == a->size) return {as_root(a), nullptr};
if (k < a->l->size) {
const auto sp = split(a->l, k);
return {as_root(sp.first), merge(sp.second, as_root(a->r))};
}
if (k > a->l->size) {
const auto sp = split(a->r, k - a->l->size);
return {merge(as_root(a->l), sp.first), as_root(sp.second)};
}
return {as_root(a->l), as_root(a->r)};
}
node_ptr insert(const node_ptr & a, size_type k, const_reference x) const {
if (!a) return create(x);
const auto sp = split(a, k);
return merge(sp.first, merge(create(x), sp.second));
}
node_ptr erase(const node_ptr & a, size_type k) const {
const auto sp = split(a, k + 1);
return merge(split(sp.first, k).first, sp.second);
}
};