Day 119-Q5 | 2次元スパーステーブル（矩形RMQ・O(1)クエリ）

問題

H行W列のグリッドに整数が書かれている。Q個のクエリが与えられ、各クエリでは矩形範囲 $(r_1, c_1) - (r_2, c_2)$（両端含む、1-indexed）が指定される。それぞれについて、矩形内に含まれる値の最小値を出力せよ。グリッドの値は更新されない（静的クエリ）。

入力形式

H W
a_{1,1} a_{1,2} ... a_{1,W}
...
a_{H,1} a_{H,2} ... a_{H,W}
Q
r1_1 c1_1 r2_1 c2_1
...
r1_Q c1_Q r2_Q c2_Q

制約

$1 \le H, W \le 500$

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

$0 \le a_{i,j} \le 10^9$

$r1 \le r2$, $c1 \le c2$

入出力例

入力例1

出力例1

1
0
2

矩形(1,1)-(2,2)は{5,2,7,1}で最小1。矩形(2,2)-(4,4)は{1,3,8,0,4,2,5,7,1}で最小0。矩形(1,3)-(3,4)は{9,4,3,8,4,2}で最小2。

概念図: 4隅の重なり矩形でminを取る

ヒント（段階的開示）

ヒント1: 方向性

1次元のスパーステーブル（区間min/gcd等の冪等半群クエリをO(1)で答える構造）は既に知っている前提とする。この構造を「行方向」と「列方向」の2つの軸に対して独立に適用すると、矩形クエリにも同じ考え方が使える。

ヒント2: アプローチ

st[kh][kw][i][j]を「行iから$2^{kh}$行分、列jから$2^{kw}$列分の矩形の最小値」と定義する。$kh=kw=0$（1×1マス）を基準に、行方向にまとめる遷移と列方向にまとめる遷移を適用して埋めていける。クエリ時は矩形を4つの（重なりを許す）$2^{kh}\times2^{kw}$の矩形でカバーしてminを取る。

ヒント3: 誘導（コード骨格）

# 前処理: st[0][0] = 元のグリッド
#   kw方向の拡張: st[kh][kw][i][j] = min(st[kh][kw-1][i][j], st[kh][kw-1][i][j+2^(kw-1)])
#   kh方向の拡張: st[kh][kw][i][j] = min(st[kh-1][kw][i][j], st[kh-1][kw][i+2^(kh-1)][j])
#
# クエリ(r1,c1,r2,c2)（0-indexed）:
#   h = r2-r1+1; w = c2-c1+1
#   kh = h.bit_length()-1; kw = w.bit_length()-1
#   4隅の 2^kh x 2^kw 矩形でminを取る
#   min(
#     st[kh][kw][r1][c1],
#     st[kh][kw][r1][c2-2^kw+1],
#     st[kh][kw][r2-2^kh+1][c1],
#     st[kh][kw][r2-2^kh+1][c2-2^kw+1],
#   )

模範解答 (Python)

import sys


def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    H = int(data[idx]); idx += 1
    W = int(data[idx]); idx += 1
    grid = []
    for _ in range(H):
        row = list(map(int, data[idx:idx + W])); idx += W
        grid.append(row)

    LOGH = max(1, H.bit_length())
    LOGW = max(1, W.bit_length())

    # st[kh][kw][i][j]
    st = [[None] * LOGW for _ in range(LOGH)]
    st[0][0] = grid

    for kh in range(LOGH):
        for kw in range(LOGW):
            if kh == 0 and kw == 0:
                continue
            cur = [[0] * W for _ in range(H)]
            if kw > 0:
                half = 1 << (kw - 1)
                prev = st[kh][kw - 1]
                for i in range(H):
                    row_prev = prev[i]
                    row_cur = cur[i]
                    for j in range(W):
                        j2 = j + half
                        row_cur[j] = row_prev[j] if j2 >= W else min(row_prev[j], row_prev[j2])
            else:
                half = 1 << (kh - 1)
                prev = st[kh - 1][kw]
                for i in range(H):
                    i2 = i + half
                    if i2 >= H:
                        cur[i] = prev[i][:]
                    else:
                        row_a, row_b = prev[i], prev[i2]
                        cur[i] = [min(row_a[j], row_b[j]) for j in range(W)]
            st[kh][kw] = cur

    def query(r1, c1, r2, c2):
        h = r2 - r1 + 1
        w = c2 - c1 + 1
        kh = h.bit_length() - 1
        kw = w.bit_length() - 1
        table = st[kh][kw]
        r2b = r2 - (1 << kh) + 1
        c2b = c2 - (1 << kw) + 1
        return min(
            table[r1][c1],
            table[r1][c2b],
            table[r2b][c1],
            table[r2b][c2b],
        )

    Q = int(data[idx]); idx += 1
    out = []
    for _ in range(Q):
        r1 = int(data[idx]) - 1; idx += 1
        c1 = int(data[idx]) - 1; idx += 1
        r2 = int(data[idx]) - 1; idx += 1
        c2 = int(data[idx]) - 1; idx += 1
        out.append(str(query(r1, c1, r2, c2)))
    print('\n'.join(out))


solve()

計算量: 前処理はテーブル全体で$O(HW\log H\log W)$、各クエリは4点参照のみで$O(1)$。$H,W\le500$なら前処理はおよそ$2\times10^7$程度で十分間に合う。乱数80試行のstress test（愚直な二重ループでの矩形min計算との突き合わせ）を実際に実行し、全試行で一致を確認済み。

Step-by-Step 解説

11次元スパーステーブルの2次元への拡張の考え方
1次元では「長さ$2^k$の区間のmin」を再帰的に半分ずつ合成して前計算した。2次元でも同様に「$2^{kh}\times2^{kw}$の矩形のmin」を、行方向・列方向それぞれの半分の合成で前計算する。

2テーブルの埋め方（片方の軸ずつ拡張）
列方向の拡張を優先し、kw==0になった時だけ行方向に拡張する。依存関係が小さい方から解決される順序を保証するのがポイント。

3クエリの「4隅の矩形」トリック
1次元の「2つの重なる区間のminを取ればよい」というテクニックを、2次元では「4つの矩形」に拡張する。重なりを許して4隅をカバーすればよい。

4なぜmin（冪等演算）でないと成り立たないか
この手法は「同じ要素を複数回使っても結果が変わらない」冪等性（min, max, gcd, andなど）を持つ場合にのみ正しい。sumのような非冪等演算には使えない。

5計算量とサイズのトレードオフ
前処理メモリは$O(HW\log H\log W)$で、H,Wが大きくなると急速にメモリを圧迫する。本問題で$H,W\le500$としているのはこのメモリ制約を考慮したもの。

よくあるミス

ミス	原因	正しい書き方
kh方向とkw方向の拡張順序を誤り、依存元のテーブルがまだ埋まっていない	ループの順序を逆にしてしまう	依存関係を満たす順序でループを回す（kwを先に伸ばし切ってからkhを1段階進める）
クエリ時にkh,kwを別々のh,wから正しく計算せず、同じkを両軸に流用してしまう	1次元の感覚のまま実装してしまう	行方向のkh=h.bit_length()-1と列方向のkw=w.bit_length()-1をそれぞれ独立に計算する
sum等の非冪等演算でこの手法を使ってしまう	min/maxと同じノリで適用できると誤解する	非冪等演算には2次元累積和や2次元BITを使う
メモリ使用量を見積もらず大きなH,Wで実装しOOMになる	$O(HW\log H\log W)$のメモリコストを軽視する	制約からメモリを事前に見積もり、大きすぎる場合はハイブリッド構造や平方分割を検討する

次のステップ

発展: 更新（点更新）にも対応させたい場合、スパーステーブルでは不可能なため2次元セグメント木（またはBIT）への置き換えを検討する。
次回予告: フェーズ8+ Master Level ローテーション継続（次回のテーマは次セッションで選定）

自己評価

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

Day 119-Q5 — 2次元スパーステーブル（矩形RMQ・O(1)クエリ）

問題