SegmentTreeOnTree

template <monoid M>
struct SegmentTreeOnTree;

概要

Segment Tree on Tree

名前	説明	計算量
`(constructor)`	(1) 空の構造を構築する (2) n頂点の空の木を構築する	(1) $O(1)$ (2) $O(n)$

名前	説明	計算量
`add_edge`	無向辺u-vを追加する	償却 $O(1)$
`build`	(1) 根rとしてHL分解とsegment treeを構築する (2) 頂点値と辺値を設定して構築する	$O(n)$
`get_vertex`	頂点uの値を返す	$O(1)$
`set_vertex`	頂点uの値を変更する	$O(\log n)$
`set_edge`	edge_idの辺値を変更する	$O(\log n)$
`prod`	uからvへの経路積を順序付きで返す	$O(\log^2 n)$

// (1)
SegmentTreeOnTree();

// (2)
explicit SegmentTreeOnTree(int _n);

(1) 空の構造を構築する

(2) n頂点の空の木を構築する

// (1)
void build(int r = 0);

// (2)
void build(const std::vector<T> &v_vals, const std::vector<T> &e_vals =;

(1) 根rとしてHL分解とsegment treeを構築する

(2) 頂点値と辺値を設定して構築する

T prod(int u, int v, bool edge = false) const;

uからvへの経路積を順序付きで返す