DualSegmentTree

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

template <monoid M>
struct DualSegmentTree;

概要

双対セグメント木

計算量

構築は $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を作用する (2) 半開区間[a,b)にvalを作用する	$O(\log n)$

メンバの詳細

(constructor)

// (1)
DualSegmentTree();

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

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

(1) 空の木を構築する

計算量: $O(1)$

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

計算量: $O(n)$

(3) 列vから構築する

計算量: $O(n)$

apply

// (1)
void apply(int a, T val);

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

(1) a番目にvalを作用する

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

(2) 半開区間[a,b)にvalを作用する

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