動的セグメント木
(DataStructure/DynamicSegmentTree.hpp)

View this file on GitHub
Last update: 2021-03-07 13:12:15+09:00
Include: #include "DataStructure/DynamicSegmentTree.hpp"
Link: https://tkmst201.github.io/Library/DataStructure/DynamicSegmentTree.hpp

概要

配列を扱うデータ構造で、セグメント木の亜種です。
必要なノードのみ動的に作成することで、要素数 $N$ の配列、$M$ 回の更新に対して、空間計算量 $\mathcal{O}(\min(N, M \log{M}))$ で、1 点更新や区間畳み込み、区間の単位元初期化、他の動的セグメント木との区間スワップを $\mathcal{O}(\log{N})$ で行うことができます。
区間に対して一意に値が定まり、区間をまとめて計算できるような演算が扱えます。例: +, xor, min, gcd, 関数の合成 など。

DynamicSegmentTree(size_t n, const T & id_elem, const F & f)
- $\Theta(1)$ 要素数 $n$ で初期化
DynamicSegmentTree(const DynamicSegmentTree & rhs)
- this 、rhs の単位元ではない要素の個数をそれぞれ $M_1, M_2$ として $\mathcal{O}(\min(|$this$|, M_1\log |$this$|) + \min(|$rhs$|, M_2\log |$rhs$|))$ rhs をコピー
DynamicSegmentTree(DynamicSegmentTree && rhs)
- this の単位元ではない要素の個数を $M$ として $\mathcal{O}(\min(|$this$|, M\log |$this$|))$ rhs をムーブ
void clear()
- 単位元では無い要素の個数を $M$ として $\mathcal{O}(\min(N, M\log{N}))$ メモリを解法し、すべての要素の値を単位元で初期化
void clear(size_t l, size_t r)
- 対象に含まれる単位元では無い要素の個数を $M$ として $\mathcal{O}(\min(r - l + \log{N}, M\log{N}))$ $A_l, \ldots, A_{r-1}$ のメモリを解法し、単位元で初期化
size_t size()
- $\Theta(1)$ 配列の要素数 $N$ を返す
void set(size_t k, const T & x)
- $\Theta(\log{N})$ $A_k = x$
T get(size_t k)
- $\mathcal{O}(\log{N})$ $A_k$ を返す
T fold(size_t l, size_t r)
- $\mathcal{O}(\log{N})$ 半開区間 $[l, r)$ の演算結果 $f(A_l, f(A_{l+1}, f(\ldots, f(A_{r-2}, A_{r-1}))\ldots)$ を返す
T fold_all()
- $\Theta(1)$ $fold(0,N)$ の計算結果 $f(A_0, f(A_1, f(\ldots, f(A_{N-2}, A_{N-1}))\ldots))$ を返す
void swap(DynamicSegmentTree & rhs, size_t l, size_t r)
- $\mathcal{O}(\log{N})$ rhs と区間 $[l, r)$ をスワップ

コンストラクタ

F は二項演算 std::function<T (const T &, const T &)> の略記です。

制約

F の単位元は id_elem
$(T, f,$ id_elem$)$ はモノイド

DynamicSegmentTree(size_t n, const T & id_elem, const F & f)

要素数 $n$ で初期化します。初期値は単位元 id_elem です。

計算量

$\Theta(1)$

DynamicSegmentTree(const DynamicSegmentTree & rhs)

動的セグメント木 rhs をコピーします。

計算量

this 、rhs の単位元ではない要素の個数をそれぞれ $M_1, M_2$ として $\mathcal{O}(\min(|$this$|, M_1\log |$this$|) + \min(|$rhs$|, M_2\log |$rhs$|))$

DynamicSegmentTree(DynamicSegmentTree && rhs)

動的セグメント木 rhs をムーブします。ムーブ後の rhs はすべての要素の値は単位元で初期化されます。

計算量

this の単位元ではない要素の個数を $M$ として $\mathcal{O}(\min(|$this$|, M\log |$this$|))$

メンバ関数

以下、要素数 $N$ の配列 $A_0, A_1, \ldots, A_{N-1}$ を対象とします。二項演算は $f$ です。

void clear()

メモリを解法し、すべての要素の値を単位元で初期化します。

計算量

単位元では無い要素の個数を $M$ として $\mathcal{O}(\min(N, M\log{N}))$

void clear(size_t l, size_t r)

$A_l, \ldots, A_{r-1}$ のメモリを解法し、単位元で初期化します。 $l = r$ のときは何も行いません。

制約

$0 \leq l \leq r \leq N$

計算量

対象に含まれる単位元では無い要素の個数を $M$ として $\mathcal{O}(\min(r - l + \log{N}, M\log{N}))$

size_t size()

配列の要素数 $N$ を返します。

計算量

$\Theta(1)$

void set(size_t k, const T & x)

$A_k$ を $x$ に変更します。

制約

$0 \leq k < N$

計算量

$\Theta(\log{N})$

T get(size_t k)

$A_k$ を返します。

制約

$0 \leq k < N$

計算量

$\mathcal{O}(\log{N})$

T fold(size_t l, size_t r)

半開区間 $[l, r)$ の演算結果 $f(A_l, f(A_{l+1}, f(\ldots, f(A_{r-2}, A_{r-1}))\ldots)$ を返します。 $l = r$ のときは単位元を返します。

制約

$0 \leq l \leq r \leq N$

計算量

$\mathcal{O}(\log{N})$

T fold_all()

$fold(0,N)$ の計算結果 $f(A_0, f(A_1, f(\ldots, f(A_{N-2}, A_{N-1}))\ldots))$ を返します。

計算量

$\Theta(1)$

void swap(DynamicSegmentTree & rhs, size_t l, size_t r)

rhs が扱う配列を $B_0, B_1, \ldots, B_{N-1}$ として、$A_l, \ldots, A_{r-1}$ と $B_l, \ldots, B_{r-1}$ の部分をスワップします。

制約

$N =$ $|$rhs$|$
rhs と代数構造が等しい

計算量

$\mathcal{O}(\log{N})$

使用例

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

int main() {
	DynamicSegmentTree<int> seg(10, 0, [](auto x, auto y) { return x + y; });
	
	cout << "size() = " << seg.size() << endl; // 10
	
	seg.set(0, 1);
	seg.set(1, 2);
	seg.set(3, 3);
	seg.set(5, 4);
	seg.set(6, 5);
	seg.set(7, 6);
	seg.set(9, 7);
	// idx 0 1 2 3 4 5 6 7 8 9
	//     1 2 0 3 0 4 5 6 0 7
	for (int i = 0; i < seg.size(); ++i) cout << seg.get(i) << " \n"[i + 1 == seg.size()];
	
	cout << "fold_all() = " << seg.fold_all() << endl; // 28 ( = 1+2+...+7 )
	cout << "fold(1, 6) = " << seg.fold(1, 6) << endl; // 9 ([2, 0, 3, 0, 4])
	
	seg.clear(5, 7);
	cout << "seg.clear(5, 7)" << endl;
	// 1 2 0 3 0 0 0 6 0 7
	for (int i = 0; i < seg.size(); ++i) cout << seg.get(i) << " \n"[i + 1 == seg.size()];
	
	DynamicSegmentTree<int> seg2(10, 0, [](auto x, auto y) { return x + y; });
	seg2.set(1, -4);
	seg2.set(3, -5);
	seg2.set(5, -8);
	seg2.set(6, -9);
	// 0 -4 0 -5 0 -8 -9 0 0 0
	for (int i = 0; i < seg2.size(); ++i) cout << seg2.get(i) << " \n"[i + 1 == seg2.size()];
	
	cout << "swap(2, 8)" << endl;
	seg.swap(seg2, 2, 8);
	// 1  2 0 -5 0 -8 -9 0 0 7
	for (int i = 0; i < seg.size(); ++i) cout << seg.get(i) << " \n"[i + 1 == seg.size()];
	// 0 -4 0  3 0  0  0 6 0 0
	for (int i = 0; i < seg2.size(); ++i) cout << seg2.get(i) << " \n"[i + 1 == seg2.size()];
	
	
	/*
		1 2 0 -5 0 -8 -9 0 0 7
		1 2 0 -5 0 -8 -9 0 0 7
		1 2 0 -5 0 -8 -9 0 0 7
		1 2 0 -5 0 -8 -9 0 0 7
		0 0 0 0 0 0 0 0 0 0
	*/
	for (int i = 0; i < seg.size(); ++i) cout << seg.get(i) << " \n"[i + 1 == seg.size()];
	{
		auto segt = seg;
		for (int i = 0; i < segt.size(); ++i) cout << segt.get(i) << " \n"[i + 1 == segt.size()];
	}
	for (int i = 0; i < seg.size(); ++i) cout << seg.get(i) << " \n"[i + 1 == seg.size()];
	{
		auto segt = std::move(seg);
		for (int i = 0; i < segt.size(); ++i) cout << segt.get(i) << " \n"[i + 1 == segt.size()];
	}
	for (int i = 0; i < seg.size(); ++i) cout << seg.get(i) << " \n"[i + 1 == seg.size()];
}

TODO

TODO: clear(l, r) の test の追加

参考

2021/03/04: https://kazuma8128.hatenablog.com/entry/2018/11/29/093827

Verified with

Code

#ifndef INCLUDE_GUARD_DYNAMIC_SEGMENT_TREE_HPP
#define INCLUDE_GUARD_DYNAMIC_SEGMENT_TREE_HPP

#include <functional>
#include <cassert>
#include <stack>
#include <cstdint>

/**
 * @brief https://tkmst201.github.io/Library/DataStructure/DynamicSegmentTree.hpp
 */
template<typename T>
struct DynamicSegmentTree {
	using value_type = T;
	using const_reference = const value_type &;
	using size_type = std::size_t;
	using F = std::function<value_type (const_reference, const_reference)>;
	
private:
	struct Node;
	using node_ptr = Node *;
	using const_ptr = const Node * const;
	struct Node {
		value_type val;
		node_ptr child[2] {nullptr, nullptr};
		Node() = default;
		Node(const_reference val) : val(val) {}
	};
	
	template<typename U>
	struct Data {
		U node;
		size_type l, r;
		Data(U node, size_type l, size_type r) : node(node), l(l), r(r) {}
	};
	
private:
	size_type n, n_;
	int log_n;
	value_type id_elem;
	F f;
	node_ptr root = nullptr;
	
public:
	DynamicSegmentTree(size_type n, const_reference id_elem, const F & f)
		: n(n), id_elem(id_elem), f(f), root(nullptr) {
		n_ = 1;
		log_n = 0;
		while (n_ < n) n_ <<= 1, ++log_n;
	}
	
	DynamicSegmentTree(const DynamicSegmentTree & rhs) {
		*this = rhs;
	}
	
	DynamicSegmentTree(DynamicSegmentTree && rhs) {
		*this = std::forward<DynamicSegmentTree>(rhs);
	}
	
	~DynamicSegmentTree() {
		clear();
	}
	
	DynamicSegmentTree & operator =(const DynamicSegmentTree & rhs) {
		if (this != &rhs) {
			clear();
			n = rhs.n;
			n_ = rhs.n_;
			log_n = rhs.log_n;
			id_elem = rhs.id_elem;
			f = rhs.f;
			root = copy_dfs(rhs.root, nullptr);
		}
		return *this;
	}
	
	DynamicSegmentTree & operator =(DynamicSegmentTree && rhs) {
		if (this != &rhs) {
			clear();
			n = rhs.n;
			n_ = rhs.n_;
			log_n = rhs.log_n;
			id_elem = rhs.id_elem;
			f = rhs.f;
			root = rhs.root;
			rhs.root = nullptr;
		}
		return *this;
	}
	
	void clear() {
		clear_subtree(root);
		root = nullptr;
	}
	
	void clear(size_type l, size_type r) {
		assert(l <= r);
		assert(r <= size());
		if ((l == 0 && r == n_) || n_ == 1) { clear(); return; }
		if (l == r || !root) return;
		std::stack<Data<node_ptr>> stk;
		stk.emplace(root, 0, n_);
		while (!stk.empty()) {
			auto [node, cl, cr] = stk.top();
			stk.pop();
			if (cl == cr) {
				node->val = f(node->child[0] ? node->child[0]->val : id_elem, node->child[1] ? node->child[1]->val : id_elem);
				continue;
			}
			const size_type m = cl + ((cr - cl) >> 1);
			stk.emplace(node, 0, 0);
			if (m < r && node->child[1]) {
				if (l <= m && cr <= r) {
					clear_subtree(node->child[1]);
					node->child[1] = nullptr;
				}
				else stk.emplace(node->child[1], m, cr);
			}
			if (l < m && node->child[0]) {
				if (l <= cl && m <= r) {
					clear_subtree(node->child[0]);
					node->child[0] = nullptr;
				}
				else stk.emplace(node->child[0], cl, m);
			}
		}
	}
	
	size_type size() const noexcept {
		return n;
	}
	
	void set(size_type k, const_reference x) {
		assert(k < size());
		if (!root) root = new Node;
		node_ptr node = root;
		std::stack<node_ptr> stk;
		for (int i = log_n - 1; i >= 0; --i) {
			stk.emplace(node);
			const bool r = k >> i & 1;
			if (!node->child[r]) node->child[r] = new Node;
			node = node->child[r];
		}
		node->val = x;
		while (!stk.empty()) {
			node = stk.top();
			stk.pop();
			node->val = f(node->child[0] ? node->child[0]->val : id_elem, node->child[1] ? node->child[1]->val : id_elem);
		}
	}
	
	value_type get(size_type k) const noexcept {
		assert(k < size());
		if (!root) return id_elem;
		node_ptr node = root;
		for (int i = log_n - 1; i >= 0; --i) {
			const bool r = k >> i & 1;
			if (!node->child[r]) return id_elem;
			node = node->child[r];
		}
		return node->val;
	}
	
	value_type fold(size_type l, size_type r) const noexcept {
		assert(l <= r);
		assert(r <= size());
		if (l == r || !root) return id_elem;
		value_type res = id_elem;
		std::stack<Data<node_ptr>> stk;
		stk.emplace(root, 0, n_);
		while (!stk.empty()) {
			auto [node, cl, cr] = stk.top();
			stk.pop();
			if (l <= cl && cr <= r) res = f(res, node->val);
			else {
				const size_type m = cl + ((cr - cl) >> 1);
				if (m < r && node->child[1]) stk.emplace(node->child[1], m, cr);
				if (l < m && node->child[0]) stk.emplace(node->child[0], cl, m);
			}
		}
		return res;
	}
	
	value_type fold_all() const noexcept {
		if (!root) return id_elem;
		return root->val;
	}
	
	void swap(DynamicSegmentTree & rhs, size_type l, size_type r) {
		assert(size() == rhs.size());
		assert(id_elem == rhs.id_elem);
		assert(l <= r);
		assert(r <= size());
		if (this == &rhs) return;
		if (l == r) return;
		if ((l == 0 && r == n_) || n_ == 1) { std::swap(root, rhs.root); return; }
		if (!root && !rhs.root) return;
		if (!root) root = new Node{id_elem};
		if (!rhs.root) rhs.root = new Node{id_elem};
		std::stack<Data<std::pair<node_ptr, node_ptr>>> stk;
		stk.emplace(std::make_pair(root, rhs.root), 0, n_);
		while (!stk.empty()) {
			auto [nodes, cl, cr] = stk.top();
			auto [node1, node2] = nodes;
			stk.pop();
			if (cl == cr) {
				node1->val = f(node1->child[0] ? node1->child[0]->val : id_elem, node1->child[1] ? node1->child[1]->val : id_elem);
				node2->val = f(node2->child[0] ? node2->child[0]->val : id_elem, node2->child[1] ? node2->child[1]->val : id_elem);
				continue;
			}
			const size_type m = cl + ((cr - cl) >> 1);
			stk.emplace(nodes, 0, 0);
			if (m < r && (node1->child[1] || node2->child[1])) {
				if (l <= m && cr <= r) std::swap(node1->child[1], node2->child[1]);
				else {
					if (!node1->child[1]) node1->child[1] = new Node;
					else if (!node2->child[1]) node2->child[1] = new Node;
					stk.emplace(std::make_pair(node1->child[1], node2->child[1]), m, cr);
				}
			}
			if (l < m && (node1->child[0] || node2->child[0])) {
				if (l <= cl && m <= r) std::swap(node1->child[0], node2->child[0]);
				else {
					if (!node1->child[0]) node1->child[0] = new Node;
					else if (!node2->child[0]) node2->child[0] = new Node;
					stk.emplace(std::make_pair(node1->child[0], node2->child[0]), cl, m);
				}
			}
		}
	}
	
private:
	node_ptr copy_dfs(const_ptr q, node_ptr r) {
		if (!q) return nullptr;
		node_ptr res = new Node{q->val};
		res->child[0] = copy_dfs(q->child[0], res);
		res->child[1] = copy_dfs(q->child[1], res);
		return res;
	}
	
	void clear_subtree(node_ptr r) {
		if (!r) return;
		std::stack<node_ptr> stk;
		stk.emplace(r);
		while (!stk.empty()) {
			node_ptr node = stk.top();
			stk.pop();
			if (node->child[0]) stk.emplace(node->child[0]);
			if (node->child[1]) stk.emplace(node->child[1]);
			delete node;
		}
	}
};

#endif // INCLUDE_GUARD_DYNAMIC_SEGMENT_TREE_HPP

#line 1 "DataStructure/DynamicSegmentTree.hpp"



#include <functional>
#include <cassert>
#include <stack>
#include <cstdint>

/**
 * @brief https://tkmst201.github.io/Library/DataStructure/DynamicSegmentTree.hpp
 */
template<typename T>
struct DynamicSegmentTree {
	using value_type = T;
	using const_reference = const value_type &;
	using size_type = std::size_t;
	using F = std::function<value_type (const_reference, const_reference)>;
	
private:
	struct Node;
	using node_ptr = Node *;
	using const_ptr = const Node * const;
	struct Node {
		value_type val;
		node_ptr child[2] {nullptr, nullptr};
		Node() = default;
		Node(const_reference val) : val(val) {}
	};
	
	template<typename U>
	struct Data {
		U node;
		size_type l, r;
		Data(U node, size_type l, size_type r) : node(node), l(l), r(r) {}
	};
	
private:
	size_type n, n_;
	int log_n;
	value_type id_elem;
	F f;
	node_ptr root = nullptr;
	
public:
	DynamicSegmentTree(size_type n, const_reference id_elem, const F & f)
		: n(n), id_elem(id_elem), f(f), root(nullptr) {
		n_ = 1;
		log_n = 0;
		while (n_ < n) n_ <<= 1, ++log_n;
	}
	
	DynamicSegmentTree(const DynamicSegmentTree & rhs) {
		*this = rhs;
	}
	
	DynamicSegmentTree(DynamicSegmentTree && rhs) {
		*this = std::forward<DynamicSegmentTree>(rhs);
	}
	
	~DynamicSegmentTree() {
		clear();
	}
	
	DynamicSegmentTree & operator =(const DynamicSegmentTree & rhs) {
		if (this != &rhs) {
			clear();
			n = rhs.n;
			n_ = rhs.n_;
			log_n = rhs.log_n;
			id_elem = rhs.id_elem;
			f = rhs.f;
			root = copy_dfs(rhs.root, nullptr);
		}
		return *this;
	}
	
	DynamicSegmentTree & operator =(DynamicSegmentTree && rhs) {
		if (this != &rhs) {
			clear();
			n = rhs.n;
			n_ = rhs.n_;
			log_n = rhs.log_n;
			id_elem = rhs.id_elem;
			f = rhs.f;
			root = rhs.root;
			rhs.root = nullptr;
		}
		return *this;
	}
	
	void clear() {
		clear_subtree(root);
		root = nullptr;
	}
	
	void clear(size_type l, size_type r) {
		assert(l <= r);
		assert(r <= size());
		if ((l == 0 && r == n_) || n_ == 1) { clear(); return; }
		if (l == r || !root) return;
		std::stack<Data<node_ptr>> stk;
		stk.emplace(root, 0, n_);
		while (!stk.empty()) {
			auto [node, cl, cr] = stk.top();
			stk.pop();
			if (cl == cr) {
				node->val = f(node->child[0] ? node->child[0]->val : id_elem, node->child[1] ? node->child[1]->val : id_elem);
				continue;
			}
			const size_type m = cl + ((cr - cl) >> 1);
			stk.emplace(node, 0, 0);
			if (m < r && node->child[1]) {
				if (l <= m && cr <= r) {
					clear_subtree(node->child[1]);
					node->child[1] = nullptr;
				}
				else stk.emplace(node->child[1], m, cr);
			}
			if (l < m && node->child[0]) {
				if (l <= cl && m <= r) {
					clear_subtree(node->child[0]);
					node->child[0] = nullptr;
				}
				else stk.emplace(node->child[0], cl, m);
			}
		}
	}
	
	size_type size() const noexcept {
		return n;
	}
	
	void set(size_type k, const_reference x) {
		assert(k < size());
		if (!root) root = new Node;
		node_ptr node = root;
		std::stack<node_ptr> stk;
		for (int i = log_n - 1; i >= 0; --i) {
			stk.emplace(node);
			const bool r = k >> i & 1;
			if (!node->child[r]) node->child[r] = new Node;
			node = node->child[r];
		}
		node->val = x;
		while (!stk.empty()) {
			node = stk.top();
			stk.pop();
			node->val = f(node->child[0] ? node->child[0]->val : id_elem, node->child[1] ? node->child[1]->val : id_elem);
		}
	}
	
	value_type get(size_type k) const noexcept {
		assert(k < size());
		if (!root) return id_elem;
		node_ptr node = root;
		for (int i = log_n - 1; i >= 0; --i) {
			const bool r = k >> i & 1;
			if (!node->child[r]) return id_elem;
			node = node->child[r];
		}
		return node->val;
	}
	
	value_type fold(size_type l, size_type r) const noexcept {
		assert(l <= r);
		assert(r <= size());
		if (l == r || !root) return id_elem;
		value_type res = id_elem;
		std::stack<Data<node_ptr>> stk;
		stk.emplace(root, 0, n_);
		while (!stk.empty()) {
			auto [node, cl, cr] = stk.top();
			stk.pop();
			if (l <= cl && cr <= r) res = f(res, node->val);
			else {
				const size_type m = cl + ((cr - cl) >> 1);
				if (m < r && node->child[1]) stk.emplace(node->child[1], m, cr);
				if (l < m && node->child[0]) stk.emplace(node->child[0], cl, m);
			}
		}
		return res;
	}
	
	value_type fold_all() const noexcept {
		if (!root) return id_elem;
		return root->val;
	}
	
	void swap(DynamicSegmentTree & rhs, size_type l, size_type r) {
		assert(size() == rhs.size());
		assert(id_elem == rhs.id_elem);
		assert(l <= r);
		assert(r <= size());
		if (this == &rhs) return;
		if (l == r) return;
		if ((l == 0 && r == n_) || n_ == 1) { std::swap(root, rhs.root); return; }
		if (!root && !rhs.root) return;
		if (!root) root = new Node{id_elem};
		if (!rhs.root) rhs.root = new Node{id_elem};
		std::stack<Data<std::pair<node_ptr, node_ptr>>> stk;
		stk.emplace(std::make_pair(root, rhs.root), 0, n_);
		while (!stk.empty()) {
			auto [nodes, cl, cr] = stk.top();
			auto [node1, node2] = nodes;
			stk.pop();
			if (cl == cr) {
				node1->val = f(node1->child[0] ? node1->child[0]->val : id_elem, node1->child[1] ? node1->child[1]->val : id_elem);
				node2->val = f(node2->child[0] ? node2->child[0]->val : id_elem, node2->child[1] ? node2->child[1]->val : id_elem);
				continue;
			}
			const size_type m = cl + ((cr - cl) >> 1);
			stk.emplace(nodes, 0, 0);
			if (m < r && (node1->child[1] || node2->child[1])) {
				if (l <= m && cr <= r) std::swap(node1->child[1], node2->child[1]);
				else {
					if (!node1->child[1]) node1->child[1] = new Node;
					else if (!node2->child[1]) node2->child[1] = new Node;
					stk.emplace(std::make_pair(node1->child[1], node2->child[1]), m, cr);
				}
			}
			if (l < m && (node1->child[0] || node2->child[0])) {
				if (l <= cl && m <= r) std::swap(node1->child[0], node2->child[0]);
				else {
					if (!node1->child[0]) node1->child[0] = new Node;
					else if (!node2->child[0]) node2->child[0] = new Node;
					stk.emplace(std::make_pair(node1->child[0], node2->child[0]), cl, m);
				}
			}
		}
	}
	
private:
	node_ptr copy_dfs(const_ptr q, node_ptr r) {
		if (!q) return nullptr;
		node_ptr res = new Node{q->val};
		res->child[0] = copy_dfs(q->child[0], res);
		res->child[1] = copy_dfs(q->child[1], res);
		return res;
	}
	
	void clear_subtree(node_ptr r) {
		if (!r) return;
		std::stack<node_ptr> stk;
		stk.emplace(r);
		while (!stk.empty()) {
			node_ptr node = stk.top();
			stk.pop();
			if (node->child[0]) stk.emplace(node->child[0]);
			if (node->child[1]) stk.emplace(node->child[1]);
			delete node;
		}
	}
};

動的セグメント木 (DataStructure/DynamicSegmentTree.hpp)

概要

コンストラクタ

DynamicSegmentTree(size_t n, const T & id_elem, const F & f)

DynamicSegmentTree(const DynamicSegmentTree & rhs)

DynamicSegmentTree(DynamicSegmentTree && rhs)

メンバ関数

void clear()

void clear(size_t l, size_t r)

size_t size()

void set(size_t k, const T & x)

T get(size_t k)

T fold(size_t l, size_t r)

T fold_all()

void swap(DynamicSegmentTree & rhs, size_t l, size_t r)

使用例

TODO

参考

Verified with

Code

動的セグメント木
(DataStructure/DynamicSegmentTree.hpp)