Day 007-Q1 | 遅延伝播セグメント木

問題

長さ $N$ の数列 $A$ がある。以下の $Q$ 個のクエリを処理せよ。

1 l r x : $A_l, \ldots, A_r$ の全要素に $x$ を加算
2 l r : $A_l, \ldots, A_r$ の最大値を出力

制約

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

$-10^9 \le A_i \le 10^9$

$1 \le l \le r \le N$

$-10^9 \le x \le 10^9$

入出力例

入力例 1

出力例 1

15
13
13

ヒント (段階的開示)

ヒント1: 方向性

区間更新（加算）と区間最大値クエリを両方 $O(\log N)$ で処理する。

ヒント2: アプローチ

「遅延」タグを各ノードに持たせ、必要になるまで子への伝播を遅らせる。

ヒント3: 誘導

def _push_down(self, node):
    if self.lazy[node] != 0:
        for child in [2*node, 2*node+1]:
            self.tree[child] += self.lazy[node]
            self.lazy[child] += self.lazy[node]
        self.lazy[node] = 0

模範解答 (Python)

import sys
from math import inf
input = sys.stdin.readline

class LazySegTree:
    def __init__(self, a):
        self.n = len(a)
        self.tree = [-inf] * (4 * self.n)
        self.lazy = [0] * (4 * self.n)
        self._build(a, 1, 0, self.n - 1)

    def _build(self, a, node, start, end):
        if start == end:
            self.tree[node] = a[start]
            return
        mid = (start + end) // 2
        self._build(a, 2*node, start, mid)
        self._build(a, 2*node+1, mid+1, end)
        self.tree[node] = max(self.tree[2*node], self.tree[2*node+1])

    def _push_down(self, node):
        if self.lazy[node] != 0:
            for child in [2*node, 2*node+1]:
                self.tree[child] += self.lazy[node]
                self.lazy[child] += self.lazy[node]
            self.lazy[node] = 0

    def update(self, l, r, val, node=1, start=None, end=None):
        if start is None:
            start, end = 0, self.n - 1
        if r < start or end < l:
            return
        if l <= start and end <= r:
            self.tree[node] += val
            self.lazy[node] += val
            return
        self._push_down(node)
        mid = (start + end) // 2
        self.update(l, r, val, 2*node, start, mid)
        self.update(l, r, val, 2*node+1, mid+1, end)
        self.tree[node] = max(self.tree[2*node], self.tree[2*node+1])

    def query(self, l, r, node=1, start=None, end=None):
        if start is None:
            start, end = 0, self.n - 1
        if r < start or end < l:
            return -inf
        if l <= start and end <= r:
            return self.tree[node]
        self._push_down(node)
        mid = (start + end) // 2
        return max(self.query(l, r, 2*node, start, mid),
                   self.query(l, r, 2*node+1, mid+1, end))

def main():
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))
    seg = LazySegTree(A)
    for _ in range(Q):
        q = list(map(int, input().split()))
        if q[0] == 1:
            _, l, r, x = q
            seg.update(l-1, r-1, x)
        else:
            _, l, r = q
            print(seg.query(l-1, r-1))

main()

Step-by-Step 解説

1通常のセグメント木との違い
通常のセグ木は点更新のみ。区間更新を素朴に行うと $O(N \log N)$ かかる。遅延伝播で区間更新も $O(\log N)$。

2lazy の役割
lazy[node] = 「このノードの子にまだ伝播していない加算値」。ノード自身の tree[node] はすでに更新済み。

3push_down のタイミング
子にアクセスする前に必ず _push_down を呼ぶ。

よくあるミス

ミス	原因	正しい書き方
push_down を query でも忘れる	update だけ気にしがち	query の分岐前にも `_push_down`
1-indexed と 0-indexed の混在	問題は 1-indexed	`l-1, r-1` で変換
lazy のリセット忘れ	子に渡した後に 0 にしない	`self.lazy[node] = 0` 必須

次のステップ

発展問題: 区間の要素を $x$ に「代入」するクエリ（assign lazy）と区間最小値クエリ

自己評価

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

Day 007-Q1 — 遅延伝播セグメント木

問題

制約