PersistentDualSegmentTree

クラス · 永続双対セグメント木

template <monoid M>
struct PersistentDualSegmentTree;

概要

永続双対セグメント木

計算量

構築は $O(n)$、点取得・区間作用は $O(\log n)$

構築・破棄

名前	説明	計算量
`(constructor)`	(1) 空の木を構築する (2) n要素をeで初期化する (3) 列vから構築する	(1) $O(1)$ (2) $O(n)$ (3) $O(n)$

メンバ関数

名前	説明	計算量
`at`	k番目の値を返す	$O(\log n)$
`get`	k番目の値を返す	$O(\log n)$
`apply`	(1) a番目にvalを作用した新しいversionを返す (2) 半開区間[a,b)にvalを作用した新しいversionを返す	$O(\log n)$

演算子

名前	説明	計算量
`operator[]`	i番目の値を返す	$O(\log n)$

メンバの詳細

(constructor)

// (1)
constexpr PersistentDualSegmentTree();

// (2)
PersistentDualSegmentTree(int _n, T e = M::id());

// (3)
template <class U>
PersistentDualSegmentTree(const std::vector<U> &v);

(1) 空の木を構築する

計算量: $O(1)$

(2) n要素をeで初期化する

計算量: $O(n)$

(3) 列vから構築する

計算量: $O(n)$

apply

// (1)
PersistentDualSegmentTree apply(int a, T val) const;

// (2)
PersistentDualSegmentTree apply(int a, int b, T val) const;

(1) a番目にvalを作用した新しいversionを返す

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

(2) 半開区間[a,b)にvalを作用した新しいversionを返す

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