euler_tour_tree

クラス · 森への辺の追加・削除と連結成分のモノイド積を管理する Euler Tour Tree

template <monoid M>
struct euler_tour_tree;

概要

森への辺の追加・削除と連結成分のモノイド積を管理する Euler Tour Tree

計算量

構築は $O(n)$、動的操作は償却 $O(\log n)$

構築・破棄

名前	説明	計算量
`(constructor)`	(1) `n` 個の孤立頂点を単位元で初期化する (2) 頂点値 `v` を持つ孤立頂点の森を作る	$O(n)$
`~euler_tour_tree`	管理している全ノードを破棄する	$O(n + m)$（`m` は辺数）

メンバ関数

名前	説明	計算量
`link`	異なる連結成分の頂点 `u`, `v` を辺で結ぶ	償却 $O(\log n)$
`cut`	辺 `(u, v)` を削除する	償却 $O(\log n)$
`same`	頂点 `u`, `v` が同じ連結成分に属するか判定する	償却 $O(\log n)$
`set`	頂点 `u` の値を `val` に更新する	償却 $O(\log n)$
`get`	頂点 `u` の値を返す	償却 $O(\log n)$
`get_subtree`	`p` を親とした頂点 `v` の部分木のモノイド積を返す	償却 $O(\log n)$
`get_size`	`p` を親とした頂点 `v` の部分木サイズを返す	償却 $O(\log n)$

メンバ型

名前	説明	計算量
`T`	頂点値と集約値の型	型エイリアスのため実行時コストなし
`node_t`	Euler Tour Tree の内部ノード	構築は $O(1)$

メンバ変数

名前	説明	計算量
`n`	頂点数	$O(1)$ で参照可能
`vertex_node`	各頂点に対応するノード	$O(1)$ で各要素を参照可能
`edge_node`	各有向辺に対応するノード	1 辺の検索は $O(\log n)$

メンバの詳細

(constructor)

// (1)
euler_tour_tree(int _n);

// (2)
euler_tour_tree(const std::vector<T> &v);

(1) n 個の孤立頂点を単位元で初期化する

計算量: $O(n)$

(2) 頂点値 v を持つ孤立頂点の森を作る

計算量: $O(n)$

get_subtree

T get_subtree(int v, int p = -1);

p を親とした頂点 v の部分木のモノイド積を返す

p == -1 または p == v のときは v の連結成分全体を返す。

計算量: 償却 $O(\log n)$

get_size

int get_size(int v, int p = -1);

p を親とした頂点 v の部分木サイズを返す

p == -1 または p == v のときは v の連結成分サイズを返す。

計算量: 償却 $O(\log n)$

node_t

struct node_t;

Euler Tour Tree の内部ノード

計算量: 構築は $O(1)$

メンバ	説明
`v`	有向辺の始点と終点（`u == v` なら頂点ノード）
`sum`	ノード自身の値と部分木のモノイド積
`sz`	部分木に含まれる頂点ノード数
`r`	親・左子・右子へのポインタ
`node_t`	端点と初期値を指定してノードを作る