問題
$ H \times W $ のマス目があります。
上から $ i $ 行目、左から $ j $ 列目にあるマス $ (i,j) $ には、整数 $ X_{i,j} $ が書かれています。
このマス目ついて、以下の $ Q $ 個の質問に答えて下さい。
🔹質問1:左上 $ (A_1,B_1) $ 右下 $ (C_1,D_1) $ の長方形領域に書かれた整数の和を表示する。
🔹質問2:左上 $ (A_2,B_2) $ 右下 $ (C_2,D_2) $ の長方形領域に書かれた整数の和を表示する。
・
・
🔹質問Q:左上 $ (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 $
解き方・ソースコード
累積和は、1次元の配列だけではなく、2次元のマス目に対しても使うことができます。
2次元の累積和 $ Z_{i,j} $ はマス $ (1,1) $ を左上とし、マス $ (i,j) $ を右下とする長方形領域の総和です。
横方向の累積和をとった後、縦方法の累積和をとると効率的に計算することができます。
2次元の累積和を使って、長方形領域の合計値を求めるには、マス $ (a,b) $ を左上とし、マス $ (c,d) $ を右下とすると、次の式で求めることができます。
$$ Z_{c,d} + Z_{a-1,b-1} - Z_{a-1,d} - Z_{c,b-1} $$
2次元累積和を計算するのに $ O(HW) $ かかり、質問に答えるのに $ O(Q) $ かかるので、全体の計算量は $ O(HW+Q) $ となります。
[Google Colaboratory]
1 | #-------- 入力例1 --------- |
[実行結果(入力例1)]
解: 30 解: 77
2次元の累積和を使って、各長方形領域に書かれた整数の総和を求めることができました。