PersistentArray
クラス · 永続配列
template <class T, int B = 4>
struct PersistentArray;
概要
永続配列
計算量
- 参照・更新は添字上限を $n$ として $O(\log_{2^B}n)$
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
(1) 空の配列を構築する (2) 既存の根から配列versionを構築する (3) n要素をvalで初期化する (4) 列vから構築する |
(1) $O(1)$ (2) $O(1)$ (3) $O(n\log_{2^B}n)$ (4) $O(n\log_{2^B}n)$ |
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
at |
k番目の値を返す | $O(\log_{2^B}k)$ |
get |
k番目の値を返す | $O(\log_{2^B}k)$ |
set |
k番目をvalに変更した新しいversionを返す | $O(\log_{2^B}k)$ |
演算子
| 名前 | 説明 | 計算量 |
|---|---|---|
operator[] |
i番目の値を返す | $O(\log_{2^B}i)$ |
メンバの詳細
(constructor)
// (1)
constexpr PersistentArray();
// (2)
constexpr PersistentArray(node_ptr _root);
// (3)
constexpr PersistentArray(int n, T val);
// (4)
template <class U>
constexpr PersistentArray(const std::vector<U> &v);
(1) 空の配列を構築する
- 計算量: $O(1)$
(2) 既存の根から配列versionを構築する
- 計算量: $O(1)$
(3) n要素をvalで初期化する
- 計算量: $O(n\log_{2^B}n)$
(4) 列vから構築する
- 計算量: $O(n\log_{2^B}n)$