Day 116-Q3 | Fat Node式永続配列

問題

長さ$N$の配列$A$に対し、$Q$個のクエリを処理せよ。配列への更新は「新しいバージョン」を作る形で記録され、過去の任意のバージョンの状態を参照できる（バージョンは常に最新版から次のバージョンが作られる一本道の管理でよい＝分岐しない部分永続）。

1 p x — 位置$p$（1-indexed）の値を$x$に変更し、新しいバージョンを作る。バージョン番号は$1$から始まる連番で、初期状態はバージョン$0$とする
2 v p — バージョン$v$の時点での位置$p$の値を出力する

入力形式

N
A_1 A_2 ... A_N
Q
query_1
query_2
...
query_Q

制約

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

クエリ2 v pの時点で$v$はそれまでの更新回数以下

入出力例

入力例1

出力例1

初期バージョン0は$[1,2,3]$。1 1 10でバージョン1は$[10,2,3]$。1 3 30でバージョン2は$[10,2,30]$。

概念図: 各位置が独立に持つ「更新の年表」

ヒント（段階的開示）

ヒント1: 方向性

セグメント木を丸ごとコピーする「フル永続化」は各バージョンで$O(\log N)$個の新規ノードを作る一般的な手法だが、実装がやや複雑になる。今回は「枝分かれしない一本道のバージョン管理（部分永続）」でよいので、もっと単純な方法がある。

ヒント2: アプローチ

各要素（配列の各位置）ごとに「その位置がいつ・どんな値に変わったか」の履歴を独立に持たせる、という発想（Fat Node法）を考える。ある位置$p$のバージョン$v$での値を知りたければ、$p$の更新履歴の中で「バージョン番号が$v$以下の最後の更新」を見つければよい。各位置の更新履歴はバージョン番号順に単調増加する列になるので、二分探索が使える。

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

history_v = [[0] for _ in range(N)]        # 各位置pの更新バージョン番号リスト（先頭は0）
history_val = [[A[i]] for i in range(N)]     # 対応する値のリスト
version = 0
# 更新: 1 p x
version += 1
history_v[p].append(version)
history_val[p].append(x)
# 参照: 2 v p
pos = bisect_right(history_v[p], v) - 1
answer = history_val[p][pos]

模範解答 (Python)

import sys
from bisect import bisect_right


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

    history_v = [[0] for _ in range(N)]
    history_val = [[A[i]] for i in range(N)]
    version = 0

    out = []
    for _ in range(Q):
        typ = data[idx]; idx += 1
        if typ == b'1':
            p = int(data[idx]) - 1
            x = int(data[idx + 1])
            idx += 2
            version += 1
            history_v[p].append(version)
            history_val[p].append(x)
        else:
            v = int(data[idx])
            p = int(data[idx + 1]) - 1
            idx += 2
            pos = bisect_right(history_v[p], v) - 1
            out.append(str(history_val[p][pos]))

    print('\n'.join(out))


solve()

計算量: 更新は各位置の履歴にappendするだけなので$O(1)$償却。参照はその位置の更新回数を$k$として$O(\log k)$の二分探索。全体で$O(N+Q\log Q)$、空間$O(N+Q)$。

Step-by-Step 解説

1フル永続とFat Nodeの使い分けの判断基準
「過去の任意バージョンから枝分かれして新しいバージョンを作れる必要があるか」がポイント。分岐が必要ならフル永続セグメント木、一本道の履歴だけでよいならFat Node法の方が実装がずっと単純で速い。

2各位置ごとの履歴配列の構築
バージョン番号は全体でグローバルに単調増加する連番。各位置$p$は、自分が変更された時だけ(version, value)のペアを自分の履歴に追加する。

3二分探索によるアクセス
bisect_right(history_v[p], v) - 1で「バージョン番号が$v$以下の中で最後の更新」のインデックスを求める。履歴はappendのみで作られるため既にソート済みで、そのまま二分探索が使える。

4更新が$O(1)$償却である理由
更新1回につき、変更対象の位置の履歴リストに要素を1つ追加するだけ。配列全体をコピーする必要が一切ない。

5空間計算量の確認
初期状態の$N$要素分に加え、更新1回につき履歴が1要素増えるだけなので、全体で$O(N+Q)$。

よくあるミス

ミス	原因	正しい書き方
Fat Node法でも過去のバージョンから枝分かれして新しいバージョンを作れると誤解する	フル永続との違いを理解していない	Fat Node法は一本道のバージョン管理（部分永続）専用。枝分かれが必要ならフル永続セグ木などが必要
更新のたびに配列全体をコピーして$O(N)$かけてしまう	各位置が独立に履歴を持つという発想に至らない	変更があった位置だけの履歴に`append`するので$O(1)$償却になる
`bisect_right`ではなく`bisect_left`を使い、ちょうど一致するバージョンで1つずれる	「$v$以下で最後の更新」と`bisect_left`（$v$未満）の意味を混同する	`bisect_right(history_v[p], v) - 1`で「$v$以下の最後の要素」のインデックスを正しく取得する
各位置の履歴リストを毎回ソートし直すなど不要な処理を入れてしまう	履歴がバージョン番号順に自然に増加することを忘れる	`append`するだけで既にソート済みなので再ソート不要

次のステップ

発展: 枝分かれ（fork）を許す「フル永続」に拡張する場合、Fat Nodeでは対応できない理由を整理し、永続セグメント木との使い分けを比較する
発展: 配列だけでなくUnion-Find（永続Union-Find）にも同じFat Node的発想を適用できるか検討する

自己評価

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

Day 116-Q3 — Fat Node式永続配列（部分永続・償却O(1)更新+二分探索アクセス）

問題