累積和（２次元）

問題

$ H \times W $ のマス目があります。

上から $ i $ 行目、左から $ j $ 列目にあるマス $ (i,j) $ には、整数 $ X_{i,j} $ が書かれています。

このマス目ついて、以下の $ Q $ 個の質問に答えて下さい。

🔹質問１：左上 $ (A_1,B_1) $ 右下 $ (C_1,D_1) $ の長方形領域に書かれた整数の和を表示する。
🔹質問２：左上 $ (A_2,B_2) $ 右下 $ (C_2,D_2) $ の長方形領域に書かれた整数の和を表示する。
　　　・
　　　・
🔹質問Ｑ：左上 $ (A_Q,B_Q) $ 右下 $ (C_Q,D_Q) $ の長方形領域に書かれた整数の和を表示する。

[制約]
🔹$ 1 \leqq H \leqq 1500 $
🔹$ 1 \leqq W \leqq 1500 $
🔹$ 1 \leqq Q \leqq 100000 $
🔹$ 0 \leqq X_{i,j} \leqq 9 $
🔹$ 1 \leqq A_i \leqq C_i \leqq H $
🔹$ 1 \leqq B_i \leqq D_i \leqq W $

解き方・ソースコード

累積和は、１次元の配列だけではなく、２次元のマス目に対しても使うことができます。

２次元の累積和 $ Z_{i,j} $ はマス $ (1,1) $ を左上とし、マス $ (i,j) $ を右下とする長方形領域の総和です。

横方向の累積和をとった後、縦方法の累積和をとると効率的に計算することができます。

２次元の累積和を使って、長方形領域の合計値を求めるには、マス $ (a,b) $ を左上とし、マス $ (c,d) $ を右下とすると、次の式で求めることができます。

$$ Z_{c,d} + Z_{a-1,b-1} - Z_{a-1,d} - Z_{c,b-1} $$

２次元累積和を計算するのに $ O(HW) $ かかり、質問に答えるのに $ O(Q) $ かかるので、全体の計算量は $ O(HW+Q) $ となります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#-------- 入力例１ ---------
H, W = 5, 5      # マス目の高さと幅
X = [            # マス目に書かれている数字 
    [5, 3, 0, 5, 1],
    [1, 0, 3, 8, 0],
    [8, 0, 5, 0, 2],
    [4, 3, 0, 4, 5],
    [0, 9, 2, 7, 2]
]

Q = 2           # 質問の数
A = [2, 1]      # 左上の縦位置
B = [2, 1]      # 左上の横位置
C = [4, 5]      # 右下の縦位置
D = [5, 5]      # 右下の横位置
#---------------------------
# 累積和を求めるための配列
Z = [ [ 0 ] * (W + 1) for i in range(H + 1) ]
# 横方向の累積和を計算
for i in range(1, H + 1):
    for j in range(1, W + 1):
        Z[i][j] = Z[i][j - 1] + X[i - 1][j - 1]

# 縦方向の累積和を計算
for j in range(1, W + 1):
    for i in range(1, H + 1):
        Z[i][j] = Z[i - 1][j] + Z[i][j]

# 答えを求める
for i in range(Q):
    print(' 解：', Z[C[i]][D[i]] + Z[A[i] - 1][B[i] - 1] - Z[A[i] - 1][D[i]] - Z[C[i]][B[i] - 1])

[実行結果（入力例１）]

 解： 30

 解： 77

２次元の累積和を使って、各長方形領域に書かれた整数の総和を求めることができました。