partial_persistent_array¶
ソースコード¶
from titan_pylib.data_structures.array.partial_persistent_array import PartialPersistentArray
展開済みコード¶
1# from titan_pylib.data_structures.array.partial_persistent_array import PartialPersistentArray
2from typing import Iterable, TypeVar, Generic
3
4T = TypeVar("T")
5
6
7class PartialPersistentArray(Generic[T]):
8 """部分永続配列です。
9 最新版の更新と、過去へのアクセスが可能です。
10 """
11
12 def __init__(self, a: Iterable[T]):
13 """``a`` から部分永続配列を構築します。
14 初期配列のバージョンは ``0`` です。
15 :math:`O(n)` です。
16 """
17 self.a: list[list[T]] = [[e] for e in a]
18 self.t: list[list[int]] = [[0] for _ in range(len(self.a))]
19 self.last_time: int = 0
20
21 def set(self, k: int, v: T, t: int) -> None:
22 """位置 ``k`` を ``v`` に更新します。
23 :math:`O(1)` です。
24
25 Args:
26 k (int): インデックスです。
27 v (T): 更新する値です。
28 t (int): 新たな配列のバージョンです。
29 """
30 assert t >= self.last_time
31 assert t > self.t[k][-1]
32 self.a[k].append(v)
33 self.t[k].append(t)
34 self.last_time = t
35
36 def get(self, k: int, t: int = -1) -> T:
37 """位置 ``k`` 、バージョン ``t`` の要素を返します。
38 :math:`O(\\log{n})` です。
39
40 Args:
41 k (int): インデックスです。
42 t (int, optional): バージョンです。デフォルトは最新バージョンです。
43 """
44 if t == -1 or t >= self.t[k][-1]:
45 return self.a[k][-1]
46 tk = self.t[k]
47 ok, ng = 0, len(tk)
48 while ng - ok > 1:
49 mid = (ok + ng) // 2
50 if tk[mid] <= t:
51 ok = mid
52 else:
53 ng = mid
54 return self.a[k][ok]
55
56 def tolist(self, t: int) -> list[T]:
57 """バージョン ``t`` の配列を返します。
58 :math:`O(n\\log{n})` です。
59 """
60 return [self.get(i, t) for i in range(len(self))]
61
62 def show(self, t: int) -> None:
63 print(f"Time: {t}", end="")
64 print([self.get(i, t) for i in range(len(self))])
65
66 def show_all(self) -> None:
67 """すべてのバージョンの配列を表示します。"""
68 for i in range(self.last_time):
69 self.show(i)
70
71 def __len__(self):
72 return len(self.a)
仕様¶
- class PartialPersistentArray(a: Iterable[T])[source]¶
Bases:
Generic[T]部分永続配列です。 最新版の更新と、過去へのアクセスが可能です。
- get(k: int, t: int = -1) T[source]¶
位置
k、バージョンtの要素を返します。 \(O(\log{n})\) です。- Parameters:
k (int) – インデックスです。
t (int, optional) – バージョンです。デフォルトは最新バージョンです。