二次元累積和 1 (paizaランク C 相当)

5 行 5 列の整数が以下のように与えられます。

1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
5 6 7 8 9

これを二次元配列 A としたとき、i 行目 j 列目を A_{i, j} (0 ≦ i ≦ 4, 0 ≦ j ≦ 4) と表すことにします。

長方形領域の左上の要素を A_{1, 1}, 右下の要素を A_{3, 3} としたとき、この長方形領域内の整数の和を累積和を用いて求め、一行で出力してください。

左上の要素を A_{1, 1}, 右下の要素を A_{3, 3} としたときの長方形領域とは二次元配列 A のこの領域を指します。

3 4 5
4 5 6
5 6 7

---

(ヒント)

領域内の整数を足していけば、累積和を使わずとも答えを求めることができますが、練習として累積和で解いてみましょう

領域の和を求める方法はいくつかありますが、簡単な方法はループを用いて領域内の数を順番に足していくことです。しかしその方法では、領域の大きさが大きくなるほど、それに比例して計算時間も長くなってしまいます。

そこで、適切な前処理をして累積和を用いることで、答えを求める際の計算時間を大きく短縮することができます。

実際に考えてみましょう。

問題で与えられた領域を図示してみます。

'o'が領域内であり、'x'が領域外です。

       x →
       0 1 2 3 4
y   0　x x x x x
↓  1  x o o o x
    2  x o o o x
    3  x o o o x
    4  x x x x x

h 行 w 列の整数の二次元配列 A があったとき、 (h + 1) 行 (w + 1) 列の整数の二次元配列 s の各要素を以下のように考えます。

s_{y, x} =  A[i][j](0 ≦ i < y, 0 ≦ j < x) の和
(0 ≦ y ≦ h, 0 ≦ x ≦ w)

例えば、s_{4, 4} は、以下の領域の整数の和です。

       x →
       0 1 2 3 4
y   0　o o o o x
↓  1  o o o o x
    2  o o o o x
    3  o o o o x
    4  x x x x x

今回の問題の場合、求めたい和は [1, 4) x [1, 4) の長方形領域内の整数の和 と言うことができます。

また、任意の長方形領域内の整数の和は、4 つの s の足し引きで求めることができます。

ある長方形領域を [sx, gx) × [sy, gy) とすると、この長方形領域内の整数の和は

(長方形領域 [sx, gx) × [sy, gy)  内の整数の和) = s_{gy, gx} - s_{sy, gx} - s_{gy, sx} + s_{sy, sx}

と表すことができます。

特に問題で与えられた領域で考えると以下のようになります。

(長方形領域内の整数の和) = s_{4, 4} - s_{1, 4} - s_{4, 1} + s_{1, 1}

なぜこうなるのか図示して考えてみましょう。

s_{4, 4} は上で示したので、それ以外の三つの領域を以下に示します。

s_{1, 4} は以下の長方形領域内の整数の和です。

       x →
       0 1 2 3 4
y   0　o o o o x
↓  1  x x x x x
    2  x x x x x
    3  x x x x x
    4  x x x x x

s_{4, 1} は以下の長方形領域内の整数の和です。

       x →
       0 1 2 3 4
y   0　o x x x x
↓  1  o x x x x
    2  o x x x x
    3  o x x x x
    4  x x x x x

s_{1, 1} は以下の長方形領域内の整数の和です。

       x →
       0 1 2 3 4
y   0　o x x x x
↓  1  x x x x x
    2  x x x x x
    3  x x x x x
    4  x x x x x

この 4 つの領域を、示した式のように計算すると、一番大きい領域の s_{4, 4} から、要らない領域の s_{1, 4} と s_{4, 1} を引き、二重で引いてしまった s_{1, 1} を足す、ということをしているのがわかります。

また、二次元配列 s の各要素は、この考え方を応用して求めることができます。

s は全て 0 で初期化されているものとすると、s_{x + 1, y + 1} は

s_{y + 1, x + 1} = s_{y, x + 1} + s_{y + 1, x} - s_{y, x} + A_{y, x}

と表すことができます。

これによって求まった二次元配列 s を用いて、

(長方形領域内の整数の和) = s_{gy, gx} - s_{sy, gx} - s_{gy, sx} + s_{sy, sx}

を用いることで、長方形領域内の整数の和を求めることができます。

このヒントを元に、二次元累積和で問題を解いてみましょう