累積和 - アレがアレでアレ

競プロで知ったことのメモ。

簡単な概要

累積和とは前処理をすれば $O(1)$ の計算量で、区間の合計を求めることができるアルゴリズム。

例えば、長さ $N=7$ の数字の配列があるとする。

$a_{0}$	$a_{1}$	$a_{2}$	$a_{3}$	$a_{4}$	$a_{5}$	$a_{6}$
2	6	1	9	5	8	4

${a_2}$ から ${a_6}$ までの区間の合計を求めたいというときは、単純に ${a_2}$ から ${a_6}$ までをループ( ${a_2} + {a_3} + {a_4} + {a_5} + {a_6}$ )すれば求めることができる。

配列が長かったり、 ${a_1}$ ～ ${a_3}$ 、 ${a_0}$ ～ ${a_6}$ 、 ${a_4}$ ～ ${a_6}$ .....と区間の合計を求める回数が例えば $M=1,000,000$ 回もある場合、 $O(NM)$ かかるので処理にとても時間がかかってしまう。

累積和を使うと前処理に $O(N)$ かければ、区間の合計を求める計算量は $O(1)$ で済む。

どんな前処理かというと、以下のような $N+1$ 大きい配列を用意する。

$s_{0}$	$s_{1}$	$s_{2}$	$s_{3}$	$s_{4}$	$s_{5}$	$s_{6}$	$s_{7}$
0	2	8	9	18	23	31	35

この配列の中身、 $s_n$ には $a_{n-1}$ までの区間の合計が入っている。

$s_1 = a_0$
$s_2 = a_0 + a_1$
$s_3 = a_0 + a_1 + a_2$
...
...
...
$s_n = a_0 + ... + a_{n-1}$

この配列を用意すれば、 ${a_2}$ から ${a_6}$ までの区間の合計は ${s_7} - {s_2}$ という式で求めることができる。
${s_7}$ には ${a_0}$ から ${a_6}$ の合計が入っているので、 ${a_0}$ から ${a_1}$ の合計が入っている ${s_2}$ を引く。

${s_7} = {a_0} + {a_1} + {a_2} + {a_3} + {a_4} + {a_5} + {a_6}$
　 $= 35$

${s_2} = {a_0} + {a_1}$
　 $= 8$
$35 - 8 = 27$ となる。

実装

上の例、 ${a_2}$ から ${a_6}$ までの区間の合計を求めるプログラムをC#で実装してみる。

void Sample()
{
    var N = 7;
    var a = new int[7] { 2, 6, 1, 9, 5, 8, 4 };
    var s = new int[N + 1];

    var left = 2;
    var right = 6;

    for (int i = 0; i < N; i++)
    {
        s[i + 1] = s[i] + a[i];
    }

    Console.WriteLine(s[right + 1] - s[left]);
}