【Java】累積和と区間の和

累積和について

累積和とは、ある数列の先頭n個の要素の和を並べた数列です。

累積和の例

数列a = 1, 3, 5
累積和の数列s = 1, 4, 9
s[1] = a[1] = 1
s[2] = a[1] + a[2] = 1 + 3 = 4
s[3] = a[1] + a[2] + a[3] = 1 + 3 + 5 = 9

Javaのコードに使いやすいように一般化

配列a = {a[0], a[1], … , a[n-1]}
先頭0個の和：s[0] = 0
先頭1個の和：s[1] = a[0]
先頭2個の和：s[2] = a[0] + a[1]
↓
先頭n個の和：s[n] = a[0] + a[1] + … + a[n-1]

区間i→jまでの和について

• 配列aの先頭i個の和はs[i]
i <= j のとき
• s[i]=(a[0] ～ a[i-1]の和)
• s[j]=(a[0] ～ a[i-1]の和) + (a[i] ～ a[j-1]の和)
• s[j] - s[i] = (a[i] ～ a[j-1]の和)
• ∴ 区間a[i] → a[j]の和 = s[j + 1] - s[i] となります。

区間の和のコード例

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n, x, y;
        n = sc.nextInt();
        x = sc.nextInt();
        y = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        // 累積和を格納する長さ n+1 の配列 s の全要素を 0 で初期化
        int[] s = new int[n + 1];
        // i を 0 から n-1 まで繰り返す
        for (int i = 0; i < n; i++) {
            // s[i+1] に s[i] + a[i] を代入し、s[1]以降の累積和の配列を作成
            s[i + 1] = s[i] + a[i];
        }

        // 区間 a[x] → a[y] の和 = s[y + 1] - s[x] を出力 
        System.out.println(s[y + 1] - s[x]);
    }
}

標準入力の入力値は下記の通りです。

3 1 2
11 22 33

変数n、x、y、aは下記の通りです。

n = 3
x = 1
y = 2
a = {11, 22, 33}

---

コード例の解説

標準入力から入力を受け取るコードの解説は割愛しますので、下記の部分のみ解説します。

// 累積和の配列 s を作成
int[] s = new int[n + 1];
for (int i = 0; i < n; i++) {
    s[i + 1] = s[i] + a[i];
}

// 区間の和を出力
System.out.println(s[y + 1] - s[x]);

1. 累積和の配列sを、サイズn+1で作成し、全要素を0で初期化します。
   （先頭0個の和0を加えるため、サイズはn+1となります。）
   この時の累積和の配列sは、下記の通りとなります。

   s = {0, 0, 0, 0}
   

2. 0～(n-1=)2までループするfor文を定義して、
3. s[1]に、s[0]=0 + a[0]=11 の11を代入します。
4. s[2]に、s[1]=11 + a[1]=22 の33を代入します。
5. s[3]に、s[2]=33 + a[2]=33 の66を代入します。
   この時の累積和の配列sは、下記の通りとなります。

   s = {0, 11, 33, 66}
   

6. 区間 a[1] → a[2] の和を求めるために、s[3] = 66 - s[1] = 11 の 55 を出力します。