Day 005-Q5 | セグメント木

問題

長さ $N$ の配列 $A$ が与えられます。以下のクエリを $Q$ 個処理してください。

1 i x : A[i] を x に変更する（1-indexed）
2 l r : A[l], A[l+1], ..., A[r] の最小値を出力する

入力形式

N Q
A1 A2 ... AN
クエリ1
クエリ2
...

制約

$1 \le N, Q \le 2 \times 10^5$

$-10^9 \le A[i], x \le 10^9$

入出力例

入力例 1

出力例 1

ヒント (段階的開示)

ヒント1: 方向性

一点更新と区間最小値クエリを $O(\log N)$ で処理できるデータ構造 → セグメント木。

ヒント2: アプローチ

セグメント木は配列を完全2分木で管理する。葉が配列要素、内部ノードが子の最小値を保持。

更新: 葉を変更 → 親を順に更新 $O(\log N)$
区間クエリ: 対応する区間ノードを集約 $O(\log N)$

ヒント3: 誘導

class SegTree:
    def __init__(self, n, e=float('inf')):
        self.n = 1
        while self.n < n:
            self.n <<= 1
        self.e = e
        self.tree = [e] * (2 * self.n)

    def update(self, i, x):  # 0-indexed
        i += self.n
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = min(self.tree[2*i], self.tree[2*i+1])

    def query(self, l, r):  # [l, r) 0-indexed
        res = self.e
        l += self.n; r += self.n
        while l < r:
            if l & 1:
                res = min(res, self.tree[l]); l += 1
            if r & 1:
                r -= 1; res = min(res, self.tree[r])
            l >>= 1; r >>= 1
        return res

模範解答 (Python)

import sys
input = sys.stdin.readline

class SegTree:
    """区間最小値セグメント木（0-indexed）"""
    def __init__(self, n, e=float('inf')):
        self.n = 1
        while self.n < n:
            self.n <<= 1
        self.e = e
        self.tree = [e] * (2 * self.n)

    def build(self, arr):
        for i, v in enumerate(arr):
            self.tree[i + self.n] = v
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = min(self.tree[2*i], self.tree[2*i+1])

    def update(self, i, x):
        i += self.n
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = min(self.tree[2*i], self.tree[2*i+1])

    def query(self, l, r):  # [l, r) の最小値
        res = self.e
        l += self.n; r += self.n
        while l < r:
            if l & 1:
                res = min(res, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                res = min(res, self.tree[r])
            l >>= 1; r >>= 1
        return res

def main():
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))

    seg = SegTree(N)
    seg.build(A)

    for _ in range(Q):
        query = list(map(int, input().split()))
        if query[0] == 1:
            _, i, x = query
            seg.update(i - 1, x)  # 1-indexed → 0-indexed
        else:
            _, l, r = query
            print(seg.query(l - 1, r))  # [l-1, r) で [l, r] を表現

main()

Step-by-Step 解説

1セグメント木の構造
サイズ: $2n$（$n$ は元の配列長以上の2べき）。インデックス: 根=1、左子=$2i$、右子=$2i+1$、葉=$n$〜$2n-1$。

2ビルド
葉を初期値で埋めた後、内部ノードを下から上へ計算。

3一点更新
i += n で葉のインデックスに変換し値を更新。while i > 1: i >>= 1 で親へ遡り、子の min を取り直す。

4区間クエリ [l, r)
ビット演算で左右端を収縮しながら区間を集約。l & 1 は左端が奇数（右の子）なら取り込む。

5計算量
更新: $O(\log N)$、クエリ: $O(\log N)$、初期ビルド: $O(N)$。

よくあるミス

ミス	原因	正しい書き方
半開区間の混同	`query(l, r)` が `[l,r]` か `[l,r)` か	コード内で統一してコメント明記
2べきに拡張しない	ツリーサイズが不足	`while self.n < n: self.n <<= 1`
1-indexedのまま渡す	入力が1-indexed	`i - 1` に変換してからメソッド呼び出し

Day 005-Q5 — セグメント木

問題