Struct EulerTourTree

pub struct EulerTourTree<M> { /* private fields */ }

Euler tour tree

Implementations

impl<M: Monoid + Clone> EulerTourTree<M>

pub fn new(n: usize) -> Self

n個の頂点のみからなる森を構築する。

pub fn reroot(&mut self, r: usize)

頂点rをそれの属する木の根にする。

pub fn is_same_tree(&self, i: usize, j: usize) -> bool

2つの頂点が同一の木に属するかどうかを判定する。

pub fn link(&mut self, i: usize, j: usize) -> Result<(), &'static str>

異なる木にそれぞれ属する2頂点間に辺を張る。

pub fn cut(&mut self, i: usize, j: usize) -> Result<(), &'static str>

2頂点間を張る辺を削除する。

pub fn set(&mut self, i: usize, value: M)

頂点iの値をvalueに設定する。

pub fn update(&mut self, i: usize, value: M)

頂点iの値をモノイドの演算と値valueで更新する。

pub fn subtree_sum(&mut self, v: usize, p: usize) -> Result<M, &'static str>

頂点pを親とする頂点vについて、vを根とする部分木の値を集積して返す。