部分的な2次元累積和を求めるやり方

概要

• 青枠内の累積値を以下の手順で求める

1. 左上からの累積値をすべての箇所で算出する
2. 1で算出されたものを利用して部分的な２次元累積和(青枠内)を求める

全ての左上からの累積値を求める

考え方

• 赤の累積値 + 青の値 = 青の累積値

手順

• 実際のプログラムでは事前準備として累積値の初期値は0なので上に1行、左に1行追加されて6行6列で初期化を行う。

1. 上の累積値は27
2. 左の累積値を足すと 27 + 24 = 51
3. 重なる部分の合計を引くと 51 - 15 = 36
4. 元の2次元配列の値 を足すと 36 + 6 = 42

• 完成形（実際のプログラムでは左と上の0は不要になるので消しておいたほうがよい。）

全体の累積値から部分的な累積値を算出

考え方

• 対象範囲を含んだ左上からの累積値 - 不要な部分を取り除いたもの

手順

• 先に算出した累積値の２次元配列を使う

1. 左上からの合計値 64
2. 上の合計値を引く 64 - 24 = 40
3. 左の合計を引く 40 - 10 = 30
4. ２重に引いた部分を足す 30 + 3 = 33。よって答えは33