Day 089-Q5 — Persistent Treap（永続平衡二分探索木・バージョン管理）

問題

長さ $N$ の整数列 $a_1,\dots,a_N$ が与えられる。これをバージョン0とする。$Q$ 個のクエリを順に処理せよ。

• 1 v l r x: バージョン $v$ の数列に対し、区間 $[l,r]$ の各要素に $x$ を加算した新しいバージョンを作る（元のバージョン $v$ はそのまま残る）。新バージョン番号はこれまでに作られたバージョン数（バージョン0を含む）。
• 2 v l r: バージョン $v$ の区間 $[l,r]$ の総和を出力する（新バージョンは作らない）。

入出力例

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

15
45
15
11
13

バージョン0=[1,2,3,4,5]。v0の[2,4]に+10→v1=[1,12,13,14,5]。v0は不変(和15)。v1の[1,2]に-1→v2=[0,11,13,14,5]。v1の[1,2]の和は13のまま。

概念図: split/merge の経路だけを clone し、旧バージョンの木は不変のまま

ヒント

def clone(i):
    j = new_id()
    left[j]=left[i]; right[j]=right[i]; pri[j]=pri[i]
    size[j]=size[i]; val[j]=val[i]; sm[j]=sm[i]; lazy[j]=lazy[i]
    return j

def split(i, k):
    if i == 0: return 0, 0
    push_down(i)
    i = clone(i)   # 元のノード i は変更しない
    ...

模範解答

import sys, random
random.seed(1)

def main():
    data = sys.stdin.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

    cap = (n + q) * 4 + 10
    left = [0]*cap; right = [0]*cap; pri = [0.0]*cap; size = [0]*cap
    val = [0]*cap; sm = [0]*cap; lazy = [0]*cap
    cnt = 0

    def new_node(v):
        nonlocal cnt
        cnt += 1; i = cnt
        pri[i] = random.random(); size[i] = 1; val[i] = v; sm[i] = v; lazy[i] = 0
        left[i] = 0; right[i] = 0
        return i

    def clone(i):
        nonlocal cnt
        cnt += 1; j = cnt
        left[j]=left[i]; right[j]=right[i]; pri[j]=pri[i]
        size[j]=size[i]; val[j]=val[i]; sm[j]=sm[i]; lazy[j]=lazy[i]
        return j

    def pull(i):
        size[i] = size[left[i]] + size[right[i]] + 1
        sm[i] = sm[left[i]] + sm[right[i]] + val[i]

    def apply_add(i, x):
        if i == 0: return i
        i = clone(i)
        val[i] += x; sm[i] += x * size[i]; lazy[i] += x
        return i

    def push_down(i):
        if lazy[i] != 0:
            left[i] = apply_add(left[i], lazy[i])
            right[i] = apply_add(right[i], lazy[i])
            lazy[i] = 0

    def build(arr):
        def rec(lo, hi):
            if lo > hi: return 0
            mid = (lo + hi) // 2
            root = new_node(arr[mid])
            left[root] = rec(lo, mid - 1)
            right[root] = rec(mid + 1, hi)
            pull(root)
            return root
        return rec(0, len(arr) - 1)

    def split(i, k):
        if i == 0: return 0, 0
        push_down(i)
        i = clone(i)
        ls = size[left[i]]
        if ls < k:
            l2, r2 = split(right[i], k - ls - 1)
            right[i] = l2
            pull(i)
            return i, r2
        else:
            l2, r2 = split(left[i], k)
            left[i] = r2
            pull(i)
            return l2, i

    def merge(x, y):
        if x == 0: return y
        if y == 0: return x
        if pri[x] > pri[y]:
            push_down(x); x = clone(x)
            right[x] = merge(right[x], y)
            pull(x)
            return x
        else:
            push_down(y); y = clone(y)
            left[y] = merge(x, left[y])
            pull(y)
            return y

    def range_add(root, l, r, x):
        p, bc = split(root, l - 1)
        b, c = split(bc, r - l + 1)
        b = apply_add(b, x)
        return merge(merge(p, b), c)

    def range_sum(root, l, r):
        p, bc = split(root, l - 1)
        b, c = split(bc, r - l + 1)
        return sm[b]

    versions = [build(a)]
    out = []
    for _ in range(q):
        typ = data[idx]; idx += 1
        if typ == '1':
            v = int(data[idx]); l = int(data[idx+1]); r = int(data[idx+2]); x = int(data[idx+3]); idx += 4
            versions.append(range_add(versions[v], l, r, x))
        else:
            v = int(data[idx]); l = int(data[idx+1]); r = int(data[idx+2]); idx += 3
            out.append(str(range_sum(versions[v], l, r)))
    print('\n'.join(out))

main()

計算量: 1回の split/merge は期待値 $O(\log N)$。全体で $O((N+Q)\log N)$、メモリも $O((N+Q)\log N)$。

Step-by-Step 解説

Step 1: ノードを配列で管理し clone を基本操作にする

再帰的なクラスではなく left/right/pri/size/val/sm/lazy を配列にし、ノードをIDで参照する。「上書きせず新しいIDを発行する」clone がすべての基本。

Step 2: split/merge を非破壊的に実装

通常のTreapの split/merge は途中で通過するノードを書き換えるが、永続版では書き換え対象を必ず clone してから行う。

Step 3: 遅延伝播も複製込みで行う

push_down で子に加算を伝えるとき、子ノードを直接書き換えず apply_add 内で clone してから更新する。怠ると旧バージョンが破壊される。

Step 4: 区間加算＝split→加算→merge、新バージョン保存

戻り値の根を新しいバージョンとして versions リストに追加する。

Step 5: 区間和＝split の副産物をそのまま読む

読み取り専用なので merge で戻す必要はない。

よくあるミス

次のステップ

• 発展問題: 区間反転（reverse）を追加した永続Treap
• 発展問題: Persistent Arrayとの比較・使い分け

自己評価