Day 129-Q1 — 永続遅延セグメント木（Persistent Lazy Segment Tree）

2026-08-21 赤色 Master / Phase 8+ ★★★★★★★★★ 子を書き換えずsum不変式+acc引数で正しく合成する区間加算+区間和のバージョン管理

問題

長さ $N$ の配列 $A$（バージョン0）に対し、1 v l r x（バージョン$v$の区間$[l,r]$に$x$を加算した新バージョンを作成）と2 v l r（バージョン$v$の区間$[l,r]$の和を出力）を$Q$個処理する。過去のバージョンは操作後も変化してはならない（永続データ構造）。

入力形式

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

制約

$1 \le N, Q \le 200000$
$-10^9 \le A_i, x \le 10^9$
$1 \le l \le r \le N$
$v$ はその時点までに存在するバージョン番号

入出力例

入力例1

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 5
2 2 1 5
2 1 3 4

出力例1

15
45
15
55
27

version0=[1,2,3,4,5]。version1はversion0の[2,4]に+10。version0は不変のまま15を維持。version2はversion1の[1,2]に+5。

概念図

バージョン間のノード共有（更新経路以外は再利用） version0 root0 L R version1（[2,4]に+10） root1' L' R' 未更新の子は共有 不変式: node.sum = childL.sum + childR.sum + node.lazy * len(node) query時は祖先のlazyをacc引数で積算し、完全一致ノードで node.sum + acc*len を返す 完全一致ノードは子を触らずsum/lazyだけ書き換えた新版を作る（子は元のまま共有）

ヒント（段階的開示）

ヒント1（方向性）

通常の遅延セグ木のpush-down（親のタグを子に書き込んで消す）は、子ノードが複数バージョンから共有されている永続構造では使えない。子を書き換えると他バージョンまで壊れる。

ヒント2（アプローチ）

各ノードのsumを常に真の合計値として維持し、lazyは「子孫に未反映の自分自身のタグ」とする。完全一致ノードは子を見ずにsum += x*len, lazy += xで新版を作る。部分一致ノードは触る子だけ複製し、sum = 新left.sum + 新right.sum + 自分のlazy*lenで自身の新版を作る。

ヒント3（誘導） 
def query(node, nl, nr, l, r, acc):
    if r < nl or nr < l:
        return 0
    if l <= nl and nr <= r:
        return node.sum + acc * (nr - nl + 1)
    mid = (nl + nr) // 2
    return (query(node.left, nl, mid, l, r, acc + node.lazy)
            + query(node.right, mid + 1, nr, l, r, acc + node.lazy))

クエリは祖先から積算されたaccを子に渡し続け、完全一致ノードで初めて真の値を得る。

模範解答 (Python)

import sys
sys.setrecursionlimit(1000000)


class Node:
    __slots__ = ('left', 'right', 'sum', 'lazy')

    def __init__(self, left, right, s, lazy):
        self.left = left
        self.right = right
        self.sum = s
        self.lazy = lazy


def build(arr, nl, nr):
    if nl == nr:
        return Node(None, None, arr[nl], 0)
    mid = (nl + nr) // 2
    l = build(arr, nl, mid)
    r = build(arr, mid + 1, nr)
    return Node(l, r, l.sum + r.sum, 0)


def update(node, nl, nr, l, r, x):
    if r < nl or nr < l:
        return node
    if l <= nl and nr <= r:
        length = nr - nl + 1
        return Node(node.left, node.right, node.sum + x * length, node.lazy + x)
    mid = (nl + nr) // 2
    newl = update(node.left, nl, mid, l, r, x)
    newr = update(node.right, mid + 1, nr, l, r, x)
    length = nr - nl + 1
    return Node(newl, newr, newl.sum + newr.sum + node.lazy * length, node.lazy)


def query(node, nl, nr, l, r, acc):
    if r < nl or nr < l:
        return 0
    if l <= nl and nr <= r:
        return node.sum + acc * (nr - nl + 1)
    mid = (nl + nr) // 2
    return (query(node.left, nl, mid, l, r, acc + node.lazy)
            + query(node.right, mid + 1, nr, l, r, acc + node.lazy))


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

    versions = [build(arr, 0, n - 1)]
    out = []

    for _ in range(q):
        t = int(data[idx]); idx += 1
        if t == 1:
            v = int(data[idx]); idx += 1
            l = int(data[idx]); idx += 1
            r = int(data[idx]); idx += 1
            x = int(data[idx]); idx += 1
            newroot = update(versions[v], 0, n - 1, l - 1, r - 1, x)
            versions.append(newroot)
        else:
            v = int(data[idx]); idx += 1
            l = int(data[idx]); idx += 1
            r = int(data[idx]); idx += 1
            out.append(str(query(versions[v], 0, n - 1, l - 1, r - 1, 0)))

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


solve()

Step-by-Step 解説

1sumの不変式
どのノードでも常にnode.sumが真の合計値になるよう維持する。子を書き換えず、自分のsumに直接加算しlazyタグだけ残す。
2更新の複製ルール
完全一致ノードは子ポインタをそのまま共有し新版を作るだけ。部分一致ノードは触る子だけ複製しsum = 新left.sum + 新right.sum + 古いlazy*lenで自身の新版を作る。
3クエリのacc引数
node.sumは自分のlazyまで反映済みだが祖先のlazyは未反映。部分一致ノードを降りるたびにacc + node.lazyを渡し続ける。
4バージョン管理
versionsリストにルートを追加するだけでO(1)切替。過去ノードは書き換えられないので常に正しい。
5計算量
更新・クエリともに$O(\log N)$、$Q$回で$O(Q\log N)$ノードが新規作成される。

よくあるミス

ミス原因正しい書き方
更新時に子へpush-downしてしまう通常の遅延セグ木のクセ子は書き換えず、その場のsum/lazyだけで表現する
クエリでaccを渡し忘れる「sumが常に真の値」という思い込み部分一致ノードを降りるたびにacc+node.lazyを渡す
更新で触らない側の子まで複製する「両方の子を新しく作る」誤解更新範囲と交わらない子はポインタをそのまま使い回す
バージョン番号のズレ新バージョン番号を明示管理していないversions.append後のlen(versions)-1が最新版

次のステップ

  • 発展: 区間代入と加算を両立させるには「代入タグ+加算タグ」の2層lazy構造が必要
  • 次回予告: 支配木（Dominator Tree・有向グラフの即時支配者計算）

自己評価

自分の回答

気づき・メモ