📊

累積和を図解でわかりやすく解説

に公開
C#
AtCoder
アルゴリズム
tech

この記事でわかること

  • 累積和を図解でわかりやすく解説 がどんな問題を解くための考え方か
  • 基本アイデアと処理の流れ
  • 実装するときに注意する点
  • 計算量の見方

参考資料

広告：この記事にはアフィリエイトリンクが含まれます。

『アルゴリズム図鑑 増補改訂版』

この記事で扱う処理の流れを、図を使って直感的に理解したい人向けの入門書です。

全体像

はじめに

累積和(Prefix Sum)は、配列の区間和を高速に求めるためのアルゴリズムです。

たとえば、配列の 2番目から4番目までの合計 を何度も聞かれるような問題では、毎回足し直すと時間がかかります。

そこで、先に「ここまでの合計」を配列にしておきます。これが累積和です。

累積和とは？

配列 A が次のようにあるとします。

A = [2, 4, 5, 7, 1, 3]

累積和 S は、S[i] = A[0] から A[i - 1] までの合計 として作ります。

S[0] = 0
S[1] = 2
S[2] = 2 + 4 = 6
S[3] = 2 + 4 + 5 = 11
S[4] = 2 + 4 + 5 + 7 = 18
S[5] = 2 + 4 + 5 + 7 + 1 = 19
S[6] = 2 + 4 + 5 + 7 + 1 + 3 = 22

つまり、こうなります。

A = [2, 4, 5, 7, 1, 3]
S = [0, 2, 6, 11, 18, 19, 22]

図解

区間 [2, 4]、つまり A[2] + A[3] + A[4] を求めたいとします。

index: 0  1  2  3  4  5
A:     2  4  5  7  1  3
             |--------|
              求めたい範囲

累積和を使うと、次のように考えられます。

実際には、

S[5] - S[2] = 19 - 6 = 13

なので、区間和は 13 です。

なぜ S[r + 1] - S[l] なのか

0-indexed の配列で、区間 [l, r] の合計を求めるときは、次の式を使います。

sum(l, r) = S[r + 1] - S[l]

S[r + 1] は A[0] から A[r] までの合計です。

S[l] は A[0] から A[l - 1] までの合計です。

その差を取ると、ちょうど A[l] から A[r] までが残ります。

C#での実装

using System;

class Program
{
    static void Main()
    {
        int[] a = { 2, 4, 5, 7, 1, 3 };
        int n = a.Length;

        int[] prefix = new int[n + 1];

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

        int left = 2;
        int right = 4;
        int sum = prefix[right + 1] - prefix[left];

        Console.WriteLine(sum);
    }
}

実行例

13

A[2] + A[3] + A[4] = 5 + 7 + 1 = 13 なので、正しく求められています。

2次元累積和

累積和は2次元にも拡張できます。

たとえば、表の中の長方形領域の合計を高速に求めたいときに使います。

1 2 3
4 5 6
7 8 9

2次元累積和では、「左上からここまでの合計」を持ちます。

長方形の合計は、足しすぎた部分を引いて、引きすぎた左上を足し戻します。

2次元累積和は、グリッド上の問題や画像・表データの集計でよく出てきます。

計算量

1次元累積和の計算量は次の通りです。

処理 計算量
累積和の前処理 O(N)
区間和クエリ1回 O(1)

2次元累積和の場合、行数を H、列数を W とすると次のようになります。

処理 計算量
2次元累積和の前処理 O(HW)
矩形和クエリ1回 O(1)

つまずきやすいポイント

S の長さは N + 1 にする

S[0] = 0 を入れるため、累積和配列は元の配列より1つ長くします。

これにより、S[r + 1] - S[l] の形で区間和をきれいに書けます。

r を含むか含まないかを意識する

この記事では、区間 [l, r] は r を含む形にしています。

一方で、プログラムでは [l, r) のように右端を含まない書き方もよく使います。

どちらで考えているかを混ぜないことが大事です。

合計が大きくなるなら long を使う

要素数や値が大きいと、int では足りないことがあります。

AtCoderでは、累積和は long[] で持つことも多いです。

まとめ

累積和は、区間和を高速に求めるための基本テクニックです。

  • 先に「ここまでの合計」を作る
  • 区間和は差で求める
  • 前処理は O(N)
  • クエリは O(1)
  • 2次元にも拡張できる

区間の合計を何度も聞かれる問題では、まず累積和を使えないか考えるとよいです。

参考

  • 『問題解決力を鍛える！アルゴリズムとデータ構造』
  • AtCoder の累積和・区間和系の問題

Discussion