Struct TreeDepthQuery

pub struct TreeDepthQuery { /* private fields */ }

根付き木において、同一の深さの頂点の区間に対して区間クエリができる。

Implementations

impl TreeDepthQuery

pub fn new<E: TreeEdgeTrait>(tree: &Tree<E>, root: usize) -> Self

根をrootとするtreeを基に、TreeDepthQueryを構築する。

pub fn children_query(&self, i: usize, d: usize) -> Option<(usize, usize)>

頂点iから深さdの子孫頂点に対応する区間を返す。

Time complexity $O(\log n)$

pub fn me_query(&self, i: usize) -> (usize, usize)

頂点iに対応する区間を返す。

pub fn ancestor(&self, i: usize, k: usize) -> Option<usize>

頂点iのk個遡った祖先の頂点を返す。

Time complexity $O(k)$