DynamicSequence

クラス · 動的配列（スプレー木、反転可能、遅延伝播対応）

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

概要

動的配列（スプレー木、反転可能、遅延伝播対応）

親ポインタを持つ反復版 splay で根に運んだノードを起点に split/merge を構成する（償却 $O(\log n)$）。全ての操作（読み取り専用のクエリも含む）で対象位置を根まで splay する。AVL 版（join-based framework）と比較し、reverse/apply のような split して戻す操作の再結合コストが軽いためこちらを採用している。

テンプレートパラメータ

名前	説明
`S`	データのモノイド
`F`	作用素モノイド（op が作用素の合成、f が値への作用）。`void` なら遅延伝播なし（区間 apply は提供しない）。

備考

void は内部で std::monostate に正規化し、本体を 1 つに保つ。

構築・破棄

名前	説明	計算量
`(constructor)`	(1) 空の動的配列を構築する (2) 内部木から動的配列を構築する	$O(1)$

メンバ関数

名前	説明	計算量
`size`	要素数を返す	$O(1)$
`get`	k番目の値を返す	償却 $O(\log n)$
`set`	k番目の値を設定する	償却 $O(\log n)$
`insert`	(1) k番目へ値を挿入する (2) k番目へ値をムーブして挿入する	償却 $O(\log n)$
`emplace`	k番目へ値を直接構築して挿入する	償却 $O(\log n)$
`push_front`	(1) 先頭へ値を追加する (2) 先頭へ値をムーブして追加する	償却 $O(\log n)$
`push_back`	(1) 末尾へ値を追加する (2) 末尾へ値をムーブして追加する	償却 $O(\log n)$
`erase`	k番目の値を削除する	償却 $O(\log n)$
`pop_front`	先頭の値を削除する	償却 $O(\log n)$
`pop_back`	末尾の値を削除する	償却 $O(\log n)$
`prod`	(1) 接頭辞のモノイド積を返す (2) 半開区間のモノイド積を返す	償却 $O(\log n)$
`reverse`	半開区間を反転する	償却 $O(\log n)$
`apply`	(1) v[p] に f を作用させる (2) v[l … r-1] に f を作用させる	償却 $O(\log n)$
`lower_bound`	`prod(i) < key <= prod(i + 1)` となる i（すべての i で `prod(i) < key` なら `size()`）	償却 $O(\log n)$
`max_right`	(1) g(prod(0,r))が真となる最大のrを返す (2) g(prod(l,r))が真となる最大のrを返す	償却 $O(\log n)$
`min_left`	(1) g(prod(l,n))が真となる最小のlを返す (2) g(prod(l,r))が真となる最小のlを返す	償却 $O(\log n)$
`split`	(1) k番目で2つの配列へ分割する (2) lとrで3つの配列へ分割する	償却 $O(\log n)$
`merge_left`	別の配列を先頭へ連結する	償却 $O(\log n)$
`merge_right`	別の配列を末尾へ連結する	償却 $O(\log n)$

メンバの詳細

(constructor)

// (1)
DynamicSequence();

// (2)
DynamicSequence(node_ptr p);

(1) 空の動的配列を構築する

計算量: $O(1)$

(2) 内部木から動的配列を構築する

計算量: $O(1)$

insert

// (1)
void insert(int k, const T &val);

// (2)
void insert(int k, T &&val);

(1) k番目へ値を挿入する

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

(2) k番目へ値をムーブして挿入する

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

push_front

// (1)
void push_front(const T &val);

// (2)
void push_front(T &&val);

(1) 先頭へ値を追加する

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

(2) 先頭へ値をムーブして追加する

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

push_back

// (1)
void push_back(const T &val);

// (2)
void push_back(T &&val);

(1) 末尾へ値を追加する

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

(2) 末尾へ値をムーブして追加する

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

prod

// (1)
T prod(int r);

// (2)
T prod(int l, int r);

(1) 接頭辞のモノイド積を返す

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

(2) 半開区間のモノイド積を返す

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

apply

// (1)
void apply(int p, U f) requires use_lazy;

// (2)
void apply(int l, int r, U f) requires use_lazy;

(1) v[p] に f を作用させる

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

(2) v[l … r-1] に f を作用させる

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

max_right

// (1)
template <class G>
int max_right(G g);

// (2)
template <class G>
int max_right(int l, G g);

(1) g(prod(0,r))が真となる最大のrを返す

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

(2) g(prod(l,r))が真となる最大のrを返す

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

min_left

// (1)
template <class G>
int min_left(G g);

// (2)
template <class G>
int min_left(int r, G g);

(1) g(prod(l,n))が真となる最小のlを返す

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

(2) g(prod(l,r))が真となる最小のlを返す

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

split

// (1)
std::pair<DynamicSequence, DynamicSequence> split(int k);

// (2)
std::tuple<DynamicSequence, DynamicSequence, DynamicSequence> split(int l, int r);

(1) k番目で2つの配列へ分割する

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

(2) lとrで3つの配列へ分割する

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