PersistentSegmentTree

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

template <class S, class F = void>
requires monoid<S> && (std::is_void_v<F> || (monoid<F> && acts_on<F, typename S::value_type>))
struct PersistentSegmentTree;

概要

永続セグメント木

テンプレートパラメータ

名前	説明
`S`	データのモノイド
`F`	作用素モノイド（op が作用素の合成、f が値への作用）。`void` なら遅延伝播なし（`apply`/`copy` は提供せず、`prod`/`get` は push を伴わない const な読み取りになる）。

計算量

構築は $O(n)$、更新・作用・区間積・区間copyは $O(\log n)$

備考

void は内部で std::monostate に正規化し、本体を 1 つに保つ。遅延伝播ありの場合、 prod は経路上の push 結果を root にキャッシュするため非 const になる。

構築・破棄

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

メンバ関数

名前	説明	計算量
`at`	(1) 遅延なしの木でk番目の値を返す (2) 遅延ありの木でk番目の値を返す	$O(\log n)$
`get`	(1) 遅延なしの木でk番目の値を返す (2) 遅延ありの木でk番目の値を返す	$O(\log n)$
`set`	k番目をvalへ変更した新しいversionを返す	$O(\log n)$
`reset`	k番目を単位元へ戻した新しいversionを返す	$O(\log n)$
`apply`	(1) v[k] に f を作用させた版を返す (2) v[a … b-1] に f を作用させた版を返す	$O(\log n)$
`copy`	v[a … b-1] を cp の同区間で置き換えた版を返す	$O(\log n)$
`all_prod`	全要素の積を返す	$O(1)$
`prod`	(1) 遅延なしの木で半開区間[a,b)の積を返す (2) 遅延ありの木で半開区間[a,b)の積を返す	$O(\log n)$

演算子

名前	説明	計算量
`operator[]`	(1) 遅延なしの木でi番目の値を返す (2) 遅延ありの木でi番目の値を返す	$O(\log n)$

メンバの詳細

(constructor)

// (1)
constexpr PersistentSegmentTree();

// (2)
PersistentSegmentTree(int _n, T e = S::id());

// (3)
template <class V>
PersistentSegmentTree(const std::vector<V> &v);

(1) 空の木を構築する

計算量: $O(1)$

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

計算量: $O(n)$

(3) 列vから構築する

計算量: $O(n)$

at

// (1)
T at(int k) const requires(!use_lazy);

// (2)
T at(int k) requires use_lazy;

(1) 遅延なしの木でk番目の値を返す

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

(2) 遅延ありの木でk番目の値を返す

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

get

// (1)
T get(int k) const requires(!use_lazy);

// (2)
T get(int k) requires use_lazy;

(1) 遅延なしの木でk番目の値を返す

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

(2) 遅延ありの木でk番目の値を返す

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

apply

// (1)
PersistentSegmentTree apply(int k, U f) const requires use_lazy;

// (2)
PersistentSegmentTree apply(int a, int b, U f) const requires use_lazy;

(1) v[k] に f を作用させた版を返す

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

(2) v[a … b-1] に f を作用させた版を返す

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

prod

// (1)
T prod(int a, int b) const requires(!use_lazy);

// (2)
T prod(int a, int b) requires use_lazy;

(1) 遅延なしの木で半開区間[a,b)の積を返す

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

(2) 遅延ありの木で半開区間[a,b)の積を返す

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

operator[]

// (1)
T operator[](int i) const requires(!use_lazy);

// (2)
T operator[](int i) requires use_lazy;

(1) 遅延なしの木でi番目の値を返す

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

(2) 遅延ありの木でi番目の値を返す

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