Day 010-Q1 — Persistent Segment Tree

2026-04-23 黄色 / Phase 6 ★★★★★★ Persistent Segment Tree

問題

長さ $N$ の数列 $A$ と $Q$ 個のクエリ:

  • 1 i x : $A[i]$ に $x$ を加える
  • 2 t l r : バージョン $t$ における $A[l]+\ldots+A[r]$ を出力

バージョン 0 は初期状態。1 操作のたびにバージョンが増える。

制約

$1 \le N \le 10^5$
$1 \le Q \le 10^5$
$-10^9 \le A[i] \le 10^9$

入出力例

入力例 1

5 7
1 2 3 4 5
1 3 10
1 1 -1
2 0 1 5
2 1 2 4
2 2 1 3

出力例 1

15
19
15

ヒント (段階的開示)

ヒント1: 方向性
通常のセグ木は最新状態のみ。Persistent Segment Tree は各更新で新ルートを作り、変更パスだけコピー。
ヒント2: アプローチ
ノードオブジェクトで管理。更新時はルートから対象リーフへのパス上のノード（$O(\log N)$ 個）のみ新規作成。
ヒント3: 誘導 
def update(prev, l, r, i, x):
    node = Node(prev.l, prev.r, prev.val + x)
    if l == r: return node
    mid = (l + r) // 2
    if i <= mid:
        node.l = update(prev.l, l, mid, i, x)
    else:
        node.r = update(prev.r, mid+1, r, i, x)
    return node

模範解答 (Python)

import sys
input = sys.stdin.readline
sys.setrecursionlimit(300000)

class Node:
    __slots__ = ['l', 'r', 'val']
    def __init__(self, l=None, r=None, val=0):
        self.l = l
        self.r = r
        self.val = val

def build(arr, l, r):
    node = Node()
    if l == r:
        node.val = arr[l]
        return node
    mid = (l + r) // 2
    node.l = build(arr, l, mid)
    node.r = build(arr, mid+1, r)
    node.val = node.l.val + node.r.val
    return node

def update(prev, l, r, i, x):
    node = Node(prev.l, prev.r, prev.val + x)
    if l == r:
        return node
    mid = (l + r) // 2
    if i <= mid:
        node.l = update(prev.l, l, mid, i, x)
    else:
        node.r = update(prev.r, mid+1, r, i, x)
    return node

def query(node, l, r, ql, qr):
    if ql > r or qr < l:
        return 0
    if ql <= l and r <= qr:
        return node.val
    mid = (l + r) // 2
    return query(node.l, l, mid, ql, qr) + query(node.r, mid+1, r, ql, qr)

def solve():
    N, Q = map(int, input().split())
    A = [0] + list(map(int, input().split()))

    roots = [None] * (Q + 1)
    roots[0] = build(A, 1, N)
    ver = 0

    for _ in range(Q):
        tokens = list(map(int, input().split()))
        if tokens[0] == 1:
            _, i, x = tokens
            roots[ver+1] = update(roots[ver], 1, N, i, x)
            ver += 1
        else:
            _, t, l, r = tokens
            print(query(roots[t], 1, N, l, r))

solve()

Step-by-Step 解説

1永続化の核心
ノードをオブジェクトで持ち、更新時にパス上のノードだけコピー。$O(\log N)$ 時間・空間で新バージョン。
2build
$N$ 要素で通常の再帰セグメント木を構築。$O(N)$。
3update
ルートから $i$ への経路（$O(\log N)$ ノード）だけ新ノードを作成。
4query
バージョン $t$ のルートから通常の区間和クエリ。

よくあるミス

ミス原因正しい書き方
roots[ver+1] = roots[ver] で上書き永続化していない新ノードを作成して返す
再帰深度超過$N=10^5$ で深さ17setrecursionlimit(300000)
バージョン番号ずれ0始まり vs 1始まりroots[0] を初期状態として明示

次のステップ

  • 発展問題: Persistent Segment Tree + 座標圧縮で「バージョン $l$〜$r$ における $k$ 番目の要素」
  • 応用: 永続 Union-Find

自己評価

自分の回答

気づき・メモ