euler_tour

クラス · 根付き木を部分木区間へ写すオイラーツアー

struct euler_tour;

概要

根付き木を部分木区間へ写すオイラーツアー

計算量

構築は $O(n)$、各アクセサと区間取得は $O(1)$

構築・破棄

名前	説明	計算量
`(constructor)`	グラフ `g` を頂点 `r` を根とするオイラーツアーへ変換する	$O(n)$

メンバ関数

名前	説明	計算量
`size`	頂点数を返す	$O(1)$
`left`	頂点 `i` の部分木区間の左端を返す	$O(1)$
`right`	頂点 `i` の部分木区間の右端を返す	$O(1)$
`order`	頂点 `i` の行きがけ順を返す	$O(1)$
`query`	頂点 `v` の部分木区間 `[l, r)` を `f(l, r)` に渡す	$O(1)$（`f` の実行時間を除く）

演算子

名前	説明	計算量
`operator[]`	頂点 `i` の部分木に対応する半開区間 `[left, right)` を返す	$O(1)$

メンバの詳細

(constructor)

template <graph_type G>
euler_tour(const G &g, int r = 0);

グラフ g を頂点 r を根とするオイラーツアーへ変換する

パラメータ g: 木を表すグラフ
パラメータ r: 根
計算量: $O(n)$