PartiallyPersistentArray

クラス · 部分永続配列 (PartiallyPersistentArray)

template <class T>
struct PartiallyPersistentArray;

概要

部分永続配列

テンプレートパラメータ

計算量

• 構築は $O(n)$、更新は償却 $O(1)$、参照は該当要素の更新回数を $q$ として $O(\log q)$

備考

• 更新は最新時刻に対してのみ行えるが、参照は任意の過去時刻に対して行える。各要素が (時刻, 値) の履歴を持つ fat node 方式で、更新のたびに履歴を 1 つ末尾に積む。
• 時刻は更新のたびに 1 進む。set(k, val, t) を使うと外部の時刻（非減少）をそのまま 割り当てられ、同一時刻に複数要素を更新できる。

構築・破棄

メンバ関数

演算子

メンバの詳細

(constructor)

// (1)
PartiallyPersistentArray();

// (2)
PartiallyPersistentArray(int n, T val = T());

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

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

• 計算量: $O(1)$

(2) n 個の val を時刻 0 の状態として作る

• 計算量: $O(n)$

(3) 列 v を時刻 0 の状態として作る

• 計算量: $O(n)$

at

// (1)
T at(int k) const;

// (2)
T at(int k, int t) const;

(1) operator[](k) の別名

• 計算量: $O(\log q)$

(2) get(k, t) の別名

• 計算量: $O(\log q)$

get

// (1)
T get(int k) const;

// (2)
T get(int k, int t) const;

(1) operator[](k) の別名

• 計算量: $O(\log q)$

(2) 時刻 t における k 番目の値を返す。t が現在時刻を超える場合は最新の値を返す

• 計算量: $O(\log q)$

set

// (1)
int set(int k, T val);

// (2)
void set(int k, T val, int t);

(1) 時刻を 1 進めて k 番目を val に変更する

• 戻り値: 更新後の時刻
• 計算量: 償却 $O(1)$

(2) 現在時刻以上の時刻 t で k 番目を val に変更し、現在時刻を t にする

• 計算量: 償却 $O(1)$
• 備考: 同一時刻に同じ要素を複数回更新した場合は最後の値が採用される

to_vector

// (1)
std::vector<T> to_vector() const;

// (2)
std::vector<T> to_vector(int t) const;

(1) 現在時刻における配列全体を返す

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

(2) 時刻 t における配列全体を返す

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