Day 060-Q4 — 二次元セグメント木 (2D RMQ)

問題

$H \times W$ のグリッドがある。初期値はすべて $0$。以下の $Q$ 個のクエリを処理せよ：

• update r c v: グリッドの $(r, c)$ の値を $v$ に更新する
• query r1 c1 r2 c2: 矩形 $[r1, r2] \times [c1, c2]$ 内の最大値を出力する

入出力例

4 4 5
update 2 3 10
update 1 1 5
query 1 1 4 4
query 1 1 1 3
update 3 3 8

10
5

update (2,3)=10, update (1,1)=5。query 全体 → max=10。query 行1・列1〜3 → max=5（(1,1)=5, (1,2)=0, (1,3)=0）。

概念図: 二次元セグメント木の構造

ヒント（段階的開示）

class SegTree2D:
    def __init__(self, H, W):
        self.H = H; self.W = W
        self.seg = [[0] * (2*W) for _ in range(2*H)]

    def _update_col(self, row_node, c, v):
        c = c - 1 + self.W
        self.seg[row_node][c] = max(self.seg[row_node][c], v)
        c >>= 1
        while c >= 1:
            self.seg[row_node][c] = max(self.seg[row_node][2*c], self.seg[row_node][2*c+1])
            c >>= 1

    def update(self, r, c, v):
        r = r - 1 + self.H
        while r >= 1:
            self._update_col(r, c, v)
            r >>= 1

模範解答 (Python)

コピーimport sys
input = sys.stdin.readline

class SegTree2D:
    def __init__(self, H, W):
        self.H = H
        self.W = W
        self.seg = [[0] * (2 * W) for _ in range(2 * H)]

    def _update_col(self, row_node, c, v):
        c = c - 1 + self.W
        self.seg[row_node][c] = max(self.seg[row_node][c], v)
        c >>= 1
        while c >= 1:
            self.seg[row_node][c] = max(
                self.seg[row_node][2 * c],
                self.seg[row_node][2 * c + 1]
            )
            c >>= 1

    def update(self, r, c, v):
        r = r - 1 + self.H
        while r >= 1:
            self._update_col(r, c, v)
            r >>= 1

    def _query_col(self, row_node, c1, c2):
        res = 0
        c1 = c1 - 1 + self.W
        c2 = c2 - 1 + self.W
        while c1 <= c2:
            if c1 & 1:
                res = max(res, self.seg[row_node][c1])
                c1 += 1
            if not (c2 & 1):
                res = max(res, self.seg[row_node][c2])
                c2 -= 1
            c1 >>= 1
            c2 >>= 1
        return res

    def query(self, r1, c1, r2, c2):
        res = 0
        r1 = r1 - 1 + self.H
        r2 = r2 - 1 + self.H
        while r1 <= r2:
            if r1 & 1:
                res = max(res, self._query_col(r1, c1, c2))
                r1 += 1
            if not (r2 & 1):
                res = max(res, self._query_col(r2, c1, c2))
                r2 -= 1
            r1 >>= 1
            r2 >>= 1
        return res

def main():
    H, W, Q = map(int, input().split())
    seg = SegTree2D(H, W)
    out = []
    for _ in range(Q):
        line = input().split()
        if line[0] == 'update':
            r, c, v = int(line[1]), int(line[2]), int(line[3])
            seg.update(r, c, v)
        else:
            r1, c1, r2, c2 = int(line[1]), int(line[2]), int(line[3]), int(line[4])
            out.append(seg.query(r1, c1, r2, c2))
    print('\n'.join(map(str, out)))

main()

Step-by-Step 解説

Step 1: データ構造の設計

外側（行方向）セグ木のサイズ $2H$、各ノードが内側（列方向）セグ木（サイズ $2W$）を持つ。合計メモリ $O(H \cdot W)$（$H = W = 1000$ で約 $2 \times 10^6$ セル）。

Step 2: 点更新

$(r, c)$ を更新すると、行セグ木の祖先ノード $O(\log H)$ 個全てに対して列セグ木の更新 $O(\log W)$ が走る。合計 $O(\log H \cdot \log W)$。

なぜ祖先全て更新するか: 行セグ木の各ノードは「担当区間の列セグ木の最大値」を保持するため、点が更新されるとその点を含む全行ノードの列値を更新する必要がある。

Step 3: 矩形クエリ

行範囲 $[r1, r2]$ を行セグ木のノード列に分解（最大 $2\log H$ ノード）。各ノードの列セグ木で $[c1, c2]$ の最大値を取得。合計 $O(\log H \cdot \log W)$。

Step 4: 計算量

更新・クエリともに $O(\log H \cdot \log W)$。$H = W = 1000$ で $\log H \cdot \log W \approx 100$。$Q = 2 \times 10^5$ で約 $2 \times 10^7$ 演算。

よくあるミス

次のステップ

発展問題: 点更新・矩形和クエリ（最大値ではなく和）に変更せよ（2D BITで $O(\log H \cdot \log W)$ が実現可能）。さらに区間更新・矩形クエリへ拡張する場合は2D遅延セグ木が必要になる。

自己評価