問題
整数列 $A = (A_1, A_2, \ldots, A_N)$ が与えられる。以下の $Q$ クエリに答えよ。
- クエリ型1:
1 t i x— 時刻 $t$ の状態の配列において $A_i$ を $x$ に変更した新しいバージョンを作る（元のバージョンは保持） - クエリ型2:
2 t l r— 時刻 $t$ の状態の配列において $A_l + \cdots + A_r$ の和を出力する
入力形式
N Q
A_1 A_2 ... A_N
クエリ形式制約
$1 \leq N \leq 2 \times 10^5$
$1 \leq Q \leq 2 \times 10^5$
$1 \leq A_i, x \leq 10^9$
$1 \leq l \leq r \leq N$
入出力例
入力例 1
5 5
1 2 3 4 5
1 0 3 10
2 0 1 5
2 1 1 5
1 1 1 7
2 3 1 5出力例 1
15
22
29バージョン0: [1,2,3,4,5]、バージョン1: [1,2,10,4,5]（A[3]←10）
ヒント (段階的開示)
ヒント1: 方向性
永続データ構造の本質は「変更されないノードは共有、変更されたパス上のノードだけ新規作成」。セグメント木の場合、1回の点更新で更新されるのは $O(\log N)$ ノードだけ。
ヒント2: アプローチ
各バージョンは「ルートノードへのポインタ」で識別。更新時は変更パス上のノードを新規作成し、変更されないサブツリーは古いノードをそのまま共有。動的にノードを割り当て、
left[node], right[node], sum[node] を配列で管理。ヒント3: 誘導
MAX_NODES = (N + Q) * 40
left = [0] * MAX_NODES
right = [0] * MAX_NODES
total = [0] * MAX_NODES
node_cnt = [1] # 0はNULLノード
def update(prev, l, r, pos, val):
node = new_node()
if l == r:
total[node] = val
return node
mid = (l + r) // 2
if pos <= mid:
left[node] = update(left[prev], l, mid, pos, val)
right[node] = right[prev] # 共有
else:
left[node] = left[prev] # 共有
right[node] = update(right[prev], mid+1, r, pos, val)
total[node] = total[left[node]] + total[right[node]]
return node模範解答 (Python)
import sys
input = sys.stdin.readline
def solve():
N, Q = map(int, input().split())
A = list(map(int, input().split()))
A = [0] + A # 1-indexed
MAX_NODES = (N + Q) * 40
lc = [0] * MAX_NODES # left child
rc = [0] * MAX_NODES # right child
sm = [0] * MAX_NODES # sum
cnt = [1] # 0 = null node
def new_node():
n = cnt[0]
cnt[0] += 1
return n
def build(l, r):
nd = new_node()
if l == r:
sm[nd] = A[l]
return nd
mid = (l + r) // 2
lc[nd] = build(l, mid)
rc[nd] = build(mid + 1, r)
sm[nd] = sm[lc[nd]] + sm[rc[nd]]
return nd
def update(prev, l, r, pos, val):
nd = new_node()
if l == r:
sm[nd] = val
return nd
mid = (l + r) // 2
if pos <= mid:
lc[nd] = update(lc[prev], l, mid, pos, val)
rc[nd] = rc[prev]
else:
lc[nd] = lc[prev]
rc[nd] = update(rc[prev], mid + 1, r, pos, val)
sm[nd] = sm[lc[nd]] + sm[rc[nd]]
return nd
def query(nd, l, r, ql, qr):
if nd == 0:
return 0
if ql <= l and r <= qr:
return sm[nd]
mid = (l + r) // 2
res = 0
if ql <= mid:
res += query(lc[nd], l, mid, ql, qr)
if qr > mid:
res += query(rc[nd], mid + 1, r, ql, qr)
return res
roots = [0] * (Q + 2)
roots[0] = build(1, N)
ver_cnt = 0
results = []
for _ in range(Q):
line = list(map(int, input().split()))
if line[0] == 1:
_, t, i, x = line
ver_cnt += 1
roots[ver_cnt] = update(roots[t], 1, N, i, x)
else:
_, t, l, r = line
results.append(query(roots[t], 1, N, l, r))
print('\n'.join(map(str, results)))
solve()Step-by-Step 解説
1永続データ構造の概念
通常のセグメント木は1つの状態しか保持できない。永続セグメント木は「全バージョンの状態」を $O(N + Q \log N)$ メモリで保持。鍵はパス圧縮による共有。
通常のセグメント木は1つの状態しか保持できない。永続セグメント木は「全バージョンの状態」を $O(N + Q \log N)$ メモリで保持。鍵はパス圧縮による共有。
2ノードプールの管理
動的割り当てをシミュレートするため、大きな配列を確保し
動的割り当てをシミュレートするため、大きな配列を確保し
cnt カウンタでノード発行。ノード0は NULL として予約。MAX_NODES = (N + Q) * 40 で余裕を持つ。3build（初期構築）
通常のセグメント木と同じ再帰構造。違いは動的ノード割り当てのみ。$O(N)$ 時間・空間。
通常のセグメント木と同じ再帰構造。違いは動的ノード割り当てのみ。$O(N)$ 時間・空間。
4update（永続的点更新）
変更パス上の $O(\log N)$ ノードを新規作成し、他はすべて旧ノードを共有。
変更パス上の $O(\log N)$ ノードを新規作成し、他はすべて旧ノードを共有。
5query（バージョン指定区間和）
ルートノードをバージョンごとの
ルートノードをバージョンごとの
roots[t] で切り替えるだけで、指定バージョンの状態での区間和が得られる。6バージョン管理
roots[] 配列でバージョン番号 → ルートノードIDを管理。型1で新バージョン発行、型2でバージョン指定。よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| MAX_NODES が小さすぎる | $O(N + Q \log N)$ の見積もり不足 | (N + Q) * 40 など余裕を持つ |
| ノード0をNULLとして未予約 | cnt = 0 から始めてNULL判定が壊れる | cnt = [1] で0番をNULL予約 |
| バージョン番号のオフセットミス | 型1と型2の番号体系の混乱 | 入力の $t$ をそのままインデックスに使う |
| 再帰深さ超過 | $N = 2 \times 10^5$ で深さ $\approx 18$ 段 | Pythonでは sys.setrecursionlimit(10**6) |
| 区間が1始まりと0始まりの混在 | A = [0] + A を忘れる | 1-indexedに統一して扱う |
次のステップ
- 発展問題1: 永続セグメント木を用いた静的区間 k 番目（マージソート木の代替）
- 発展問題2: 永続 Union-Find（Union 操作を永続化、Find 操作に path compression を使わない実装）
- 発展問題3: 部分的永続・完全永続の概念の違いと実装コスト比較