区間の和 1 Go編（paizaランク C 相当）

(はじめに)

この問題集では、累積和について扱います。

累積和は、一言でいうと「適切な前処理をおこない、配列上の区間の総和を高速で処理できるようにする手法」です。

どのように前処理をおこなうか、前処理した結果を利用するかなどは問題により異なります。この問題集を通してさまざまな累積和の問題に触れ、少しずつ累積和に慣れていきましょう。

まずは、問題を見てみましょう。

---

(問題)

10 個の整数 a_0, a_1, a_2, ..., a_9 からなる数列 a を用意します。

a_0, a_1, a_2, ..., a_9 をそれぞれ

1 5 9 7 5 3 2 5 8 4

としたとき、この数列の a_2 から a_7 までの和 (a_2 + a_3 + ... + a_7) を、累積和を使うことで求めてください。

---

(ヒント : 累積和の考え方)

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

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

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

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

数列 a_0, a_1, ..., a_(N-1) に対して、数列 s_0, s_1, ... s_N を以下のように考えます。

s_0 = 0
s_1 = a_0
s_2 = a_0 + a_1
s_3 = a_0 + a_1 + a_2
...
s_N = a_0 + a_1 + ... + a_(N-1)

例えば、a = {8, 1, 3} とすると、s = {0, 8, 9, 12} となります。

この数列 s を用いると、a_2 から a_7 までの和は s_8 - s_2 で求めることができます。

実際に考えてみましょう。
s_2 と s_8 はそれぞれ

s_2 = a_0 + a_1
s_8 = a_0 + a_1 + a_2 + s_3 + a_3 + a_4 + a_5 + a_6 + a_7

ですから、s_8 - s_2 は

s_8 - s_2 = (a_0 + a_1 + a_2 + a_3 + a_4 + a_5 + a_6 + a_7) - (a_0 + a_1)
= a_2 + a_3 + a_4 + a_5 + a_6 + a_7

となり、a_2 から a_7 までの和は s_8 - s_2 で求めることができるとわかります。

このように、数列 a の累積の和をあらかじめ計算しておくことで、長い区間の和でも一回の計算で求めることができます。

また、数列 s の各要素は、以下のように一つ前の要素を用いることで計算できます。

s_0 = 0
s_1 = s_0 + a_0
s_2 = s_1 + a_1
s_3 = s_2 + a_2
...
s_N = s_N-1 + a_N

そして、これを一般化すると

s_(i+1) = s_i + a_i

と考えることができます。これを for 文等ループを用いて実装することで、数列 s の各要素を求めることができます。

---

(ヒント : 開区間と閉区間)

累積和の区間は、開区間と閉区間を用いることでよりわかりやすく考えることができます。

閉区間とは、区間の端を含む区間のことで、[2, 7] のように表されます。

例えば、数列 a の範囲を [2, 7] のようにすると、これは

a_2, a_3, a_4, a_5, a_6, a_7

を表します。

開区間とは、区間の端を含まない区間のことで、(2, 7) のように表されます。

例えば、数列 a の範囲を (2, 7) のようにすると、これは

a_3, a_4, a_5, a_6

を表します。

累積和は、左端を閉区間、右端を開区間として考えると理解しやすいです。

このような区間を一般的に半開区間と呼びます。

例えば、数列 a の範囲を [2, 8) としたときの総和を考えてみましょう。

まず、a の範囲を [2, 8) としたとき、これは

a_2, a_3, a_4, a_5, a_6, a_7

を表します。

次に、s_2, s_8 は、a のどこからどこまでの和なのかを考えてみると

s_2 : [0, 2) の総和
s_8 : [0, 8) 総和

となります。

このことから、s_8 から s_2 を引くことで、数列 a の [2, 8) の総和を求めることができるとわかります。

これを、より一般的に考えると

数列 a の範囲を [left, right) としたとき、この範囲の総和は s[right] - s[left] で求めることができる

とすることができます。

最後に、開区間と閉区間の考え方を用いて、今回の問題のように、a_x から a_y (x ≦ y) までの和を求める場合を考えてみましょう。

この場合、範囲の右端は a_y を含むため、数列 a の範囲は [x, y + 1) であると考えることができます。

先ほど説明した通り、数列 a の範囲を [left, right) としたとき、この範囲の総和は s[right] - s[left] で求めることができるため、a_x から a_y までの和は

s[y + 1] - s[x]

と表すことができ、これを用いることでこの問題を解くことができます。