永続配列
列の要素を、ヒープと同じ形の二分木のノードに 1 つずつ持たせます(最初の版では、ノード $k$ が $a_k$ を持ち、その子はノード $2k + 1$ と $2k + 2$)。 $a_i$ を持つノードには、 $i + 1$ を 2 進数で書いて先頭の $1$ より下の桁を上から見ていき、 $0$ なら左、 $1$ なら右の子に進むと着きます。 $a_i$ を書き換えるときは、根からそのノードまでの道にあるノードだけをコピーして、新しい根を作ります(経路コピー)。残りの部分木は前の版と共有するので、前の版はそのまま残り、どの版からでも新しい版を作れます(完全永続)。ノードはオブジェクトにせず、子の番号と要素をリスト lch, rch, val に持たせています。
版の番号は整数で、最初の列が版 $0$ です。set を呼ぶたびに $1, 2, \dots$ と増えます。
PersistentArray(a): 列 $a$ を版 $0$ として作る。 $O(N)$get(ver, i): 版 $\mathrm{ver}$ の $a_i$。 $O(\log N)$set(ver, i, x): 版 $\mathrm{ver}$ の $a_i$ を $x$ にした新しい版を作り、その番号を返す(版 $\mathrm{ver}$ は変わらない)。 $O(\log N)$ 時間・メモリ
set 1 回でノードが $O(\log N)$ 個増えるので、 $Q$ 回で $O(N + Q \log N)$ のメモリを使います。
例:
pa = PersistentArray([1, 2, 3, 4, 5])
v1 = pa.set(0, 2, 10) # 版 0 の a[2] を 10 にした版
v2 = pa.set(v1, 4, 20) # 版 v1 の a[4] を 20 にした版
v3 = pa.set(0, 0, 30) # 版 0 から枝分かれ
print([pa.get(v2, i) for i in range(5)]) # [1, 2, 10, 4, 20]
print([pa.get(v3, i) for i in range(5)]) # [30, 2, 3, 4, 5]
print([pa.get(0, i) for i in range(5)]) # [1, 2, 3, 4, 5]
スタックを永続にするだけなら、この配列はいりません。各版を、一番上の値とその下のスタックの組 (x, s) で表し、空のスタックを None とすると、push・pop・top がどれも $O(1)$ で、どの版からでも枝分かれできます。
s1 = (3, None) # 空のスタックに 3 を積んだ版
s2 = (5, s1) # s1 に 5 を積んだ版
s3 = (7, s1) # s1 から枝分かれ(s2 は変わらない)
# top は s[0]、pop した版は s[1]
print(s2[0], s3[0], s3[1][0]) # 5 7 3
コード
class PersistentArray:
# 経路コピーで永続化した配列。版の番号は 0, 1, 2, ...(どの版からでも新しい版を作れる)
# ノード 1 つが要素 1 つを持つ二分木。版 0 ではノード k が a[k] を持ち、子は 2k + 1 と 2k + 2
def __init__(self, a):
n = len(a)
self.lch = list(range(1, 2 * n, 2)) # lch[t] = ノード t の左の子
self.rch = list(range(2, 2 * n + 1, 2)) # rch[t] = ノード t の右の子
self.val = list(a) # val[t] = ノード t が持つ要素
self.root = [0] # root[v] = 版 v の根
def get(self, ver, i):
# 版 ver の a[i]
# i + 1 の 2 進表記を、先頭の 1 の次の桁から見ていき、0 なら左、1 なら右の子に進む
lch, rch = self.lch, self.rch
t = self.root[ver]
k = i + 1
for j in range(k.bit_length() - 2, -1, -1):
t = rch[t] if k >> j & 1 else lch[t]
return self.val[t]
def set(self, ver, i, x):
# 版 ver の a[i] を x にした新しい版を作り、その番号を返す(版 ver は変わらない)
lch, rch, val = self.lch, self.rch, self.val
t = self.root[ver]
k = i + 1
c = len(val) # 根から順に、通るノードをコピーしたノード c, c + 1, ... を作る
self.root.append(c)
for j in range(k.bit_length() - 2, -1, -1):
c += 1
val.append(val[t])
if k >> j & 1:
lch.append(lch[t])
rch.append(c)
t = rch[t]
else:
lch.append(c)
rch.append(rch[t])
t = lch[t]
lch.append(lch[t])
rch.append(rch[t])
val.append(x)
return len(self.root) - 1