Day 005-Q1 | 累積和（2次元）

問題

H行W列のグリッド。各セルに整数値。Q個のクエリで矩形領域 (r1, c1) から (r2, c2) までの合計を答えよ（1-indexed）。

入力形式

H W
a[1][1] ... a[1][W]
...
a[H][1] ... a[H][W]
Q
r1 c1 r2 c2
...

制約

$1 \le H, W \le 1000$

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

$0 \le a_{ij} \le 10^9$

入出力例

入力例 1

出力例 1

24
42

ヒント (段階的開示)

ヒント1: 方向性

毎クエリ O(HW) で TLE。前処理で2次元累積和を作るとクエリ O(1)。

ヒント2: アプローチ

S[i][j] = 左上(1,1)〜(i,j)の合計。包除原理で矩形和を求める。

ヒント3: 誘導

S[i][j] = a[i-1][j-1] + S[i-1][j] + S[i][j-1] - S[i-1][j-1]

# クエリ
sum = S[r2][c2] - S[r1-1][c2] - S[r2][c1-1] + S[r1-1][c1-1]

模範解答 (Python)

import sys
input = sys.stdin.readline

def main():
    H, W = map(int, input().split())
    a = []
    for _ in range(H):
        a.append(list(map(int, input().split())))

    S = [[0] * (W + 1) for _ in range(H + 1)]
    for i in range(1, H + 1):
        for j in range(1, W + 1):
            S[i][j] = a[i-1][j-1] + S[i-1][j] + S[i][j-1] - S[i-1][j-1]

    Q = int(input())
    for _ in range(Q):
        r1, c1, r2, c2 = map(int, input().split())
        ans = S[r2][c2] - S[r1-1][c2] - S[r2][c1-1] + S[r1-1][c1-1]
        print(ans)

main()

Step-by-Step 解説

12次元累積和の意味
S[i][j] = 左上(1,1)から(i,j)の長方形の総和。

2構築式
上と左の累積和を足して、重複する左上部分を引く。

3クエリ処理（包除原理）
引き過ぎた左上を再度足す → 4項式。

計算量

前処理: $O(HW)$
各クエリ: $O(1)$
合計: $O(HW + Q)$

よくあるミス

ミス	原因	正しい書き方
0-indexed で複雑化	境界処理が面倒	1-indexed + 0パディング
-S[i-1][j-1] を忘れる	包除の最後の足し戻し忘れ	4項を必ず揃える

Day 005-Q1 — 累積和（2次元）

問題