Day 096-Q4 | Persistent Array（関数型配列）

問題

長さ $N$ の配列 $A$（バージョン0）が与えられる。以下 $Q$ 個のクエリを順に処理せよ。

0 t i x: バージョン $t$ の配列をコピーし、位置 $i$（1-indexed）の値を $x$ に変更した新しい配列を作り、新しいバージョン番号として登録する。
1 t i: バージョン $t$ の配列の位置 $i$（1-indexed）の値を出力する。

過去のどのバージョンも変更されず参照し続けられる（永続性）ことに注意し、配列コピーを毎回 $O(N)$ で行うのではなく、永続セグメント木（path copying）を用いて1回の更新を $O(\log N)$ で行うことで、全体の計算量を改善せよ。

入力形式

N Q
A_1 A_2 ... A_N
query_1
:
query_Q

制約

$1 \le N \le 2\times10^5$

$1 \le Q \le 2\times10^5$

$t$ はその時点で存在するバージョン番号

$1 \le i \le N$, $|x|,|A_i|\le10^9$

入出力例

入力例1

出力例1

3
100
3

バージョン0から位置3を100に変えた新バージョン1を作っても、バージョン0の位置3は依然として3のまま。

概念図

ヒント（段階的開示）

ヒント1: 方向性

毎回配列をまるごとコピーすれば正しく永続性を実現できるが $O(NQ)$ になる。更新で変わるのは「根からその位置に至る経路上のノードだけ」であるという性質を、木構造の上で表現できないか考えよ。

ヒント2: アプローチ

セグメント木を考え、更新時に変更が及ぶパス上のノードだけを新しく複製し、それ以外の部分木は古いバージョンのノードをそのまま指す（共有する）。これが永続セグメント木（Persistent Segment Tree）であり、1回の更新につき $O(\log N)$ 個の新ノードを作るだけで済む。各バージョンは「そのバージョンのルートノード番号」だけを覚えておけばよい。

ヒント3: 誘導（コード骨格）

def update(prev, l, r, pos, x):
    node = new_node()
    if l == r:
        val[node] = x
        return node
    mid = (l + r) // 2
    if pos <= mid:
        left[node] = update(left[prev], l, mid, pos, x)
        right[node] = right[prev]          # 変更されない側は共有
    else:
        left[node] = left[prev]
        right[node] = update(right[prev], mid + 1, r, pos, x)
    return node

`build` で初期木を作り、各バージョンのルートを `roots` に保存。クエリ0では `update` の戻り値を `roots` に追加、クエリ1では `roots[t]` から `query` する。

模範解答 (Python)

import sys


def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    q = int(data[idx]); idx += 1
    a = [int(data[idx + i]) for i in range(n)]
    idx += n

    max_nodes = 2 * n + 40 * q + 10
    left = [0] * max_nodes
    right = [0] * max_nodes
    val = [0] * max_nodes
    cnt = 0

    def build(l, r):
        nonlocal cnt
        cnt += 1
        node = cnt
        if l == r:
            val[node] = a[l]
            return node
        mid = (l + r) // 2
        left[node] = build(l, mid)
        right[node] = build(mid + 1, r)
        return node

    def update(prev, l, r, pos, x):
        nonlocal cnt
        cnt += 1
        node = cnt
        if l == r:
            val[node] = x
            return node
        mid = (l + r) // 2
        if pos <= mid:
            left[node] = update(left[prev], l, mid, pos, x)
            right[node] = right[prev]
        else:
            left[node] = left[prev]
            right[node] = update(right[prev], mid + 1, r, pos, x)
        return node

    def query(node, l, r, pos):
        while l != r:
            mid = (l + r) // 2
            if pos <= mid:
                node, r = left[node], mid
            else:
                node, l = right[node], mid + 1
        return val[node]

    roots = [build(0, n - 1)]
    out = []
    for _ in range(q):
        typ = data[idx]; idx += 1
        if typ == b'0':
            t = int(data[idx]); idx += 1
            i = int(data[idx]) - 1; idx += 1
            x = int(data[idx]); idx += 1
            roots.append(update(roots[t], 0, n - 1, i, x))
        else:
            t = int(data[idx]); idx += 1
            i = int(data[idx]) - 1; idx += 1
            out.append(str(query(roots[t], 0, n - 1, i)))

    sys.stdout.write('\n'.join(out) + '\n')


solve()

計算量: 初期構築 $O(N)$、各更新 $O(\log N)$（新ノード $O(\log N)$ 個）、各クエリ $O(\log N)$。全体で $O(N+Q\log N)$。ノード総数は $O(N+Q\log N)$。

Step-by-Step 解説

1初期木の構築
`build` で区間 $[0,N-1]$ を再帰的に2分し、葉に初期値を格納。これがバージョン0のルート。

2更新はパスのみ複製
更新対象を含まない側の子は古いバージョンのノード番号をそのまま使い回す。新規ノードは $O(\log N)$ 個だけ。

3バージョン管理
`roots` リストのインデックスがそのままバージョン番号。バージョン0は初期状態、以後クエリ0のたびに1つずつ増える。

4クエリはそのバージョンのルートから辿るだけ
`query` は反復で対象位置に到達するまで左右の子を辿る。

よくあるミス

ミス	原因	正しい書き方
更新時に両方の子を新規作成してしまう	永続化の本質（共有）を理解していない	変更されない側は必ず `prev` のノード番号をそのまま使う
ノード配列サイズを $N$ だけ確保し溢れる	更新毎の新ノード数を見落とす	`max_nodes` は $O(N+Q\log N)$ 確保する
バージョン番号の管理を誤る	クエリの $t$ とリストのインデックスがずれる	クエリ0のたびに必ず `roots.append(...)`
`query` を再帰のまま書きスタックコストが無視できない	反復に書き換えられることを知らない	while ループで葉に到達するまで辿る

次のステップ

発展: Persistent Union-Find や Persistent Array によるオフライン処理（分岐管理）との関係を整理する
発展: 区間和クエリにも対応させる場合、各ノードに部分木和を持たせれば永続BIT/永続セグ木として汎用化できる
次回予告: Merge Sort Tree拡張（区間中央値クエリ・二分探索×ランク数え上げ）

自己評価

完全理解おおむね理解要復習

Day 096-Q4 — Persistent Array（関数型配列・永続セグメント木）

問題