永続配列

列の要素を、ヒープと同じ形の二分木のノードに 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$ と増えます。

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