累積和で範囲合計｜コードで実践

累積和で範囲合計

このレッスンで分かること

prefix の長さは元配列より 1 だけ長い

配列に対して「l 番目から r 番目までの合計はいくつか」というクエリが大量に来るとします

ここで威力を発揮するのが 累積和 (prefix sum) です

累積和で範囲合計とは

累積和 (prefix sum) を作っておくことで、範囲合計のクエリを O(1) で答えられる仕組みを学ぶ。

配列に対して「l 番目から r 番目までの合計はいくつか」というクエリが大量に来るとします。素朴に答えるなら、毎回 l..r を for ループで合計するので、1 回のクエリに O(r - l) 、最悪 O(n) の時間がかかります。クエリが q 個なら全体で O(nq) です。

ここで威力を発揮するのが 累積和 (prefix sum) です。配列の先頭から各位置までの合計をあらかじめ計算しておけば、任意の範囲の合計は 2 つの累積和の引き算 で求められ、1 クエリあたり O(1) になります。前処理に O(n) 、クエリ q 個合わせて全体は O(n + q) 。これは競技プログラミングの基本テクニックの 1 つです。

「前処理で O(n) ＋クエリで O(1)」は、累積和をはじめとする多くの定数時間クエリ系アルゴリズムの定石。

累積和の定義と例

配列 arr = [a0, a1, a2, ..., an-1] に対して、累積和配列 prefix を次のように定義します。

prefix[0] = 0
prefix[1] = a0
prefix[2] = a0 + a1
prefix[i] = a0 + a1 + ... + a_{i-1}
prefix[n] = a0 + a1 + ... + a_{n-1}

つまり prefix の長さは n + 1 で、先頭に 0 を入れておくのがポイントです。範囲 [l, r] (両端含む) の合計は prefix[r + 1] - prefix[l] で計算できます。

diagram (will load when visible)

図のポイント (テキスト併記)

arr = [1, 2, 3, 4, 5] のとき、累積和は prefix = [0, 1, 3, 6, 10, 15]

arr = [1, 2, 3, 4, 5] のとき、累積和は prefix = [0, 1, 3, 6, 10, 15] 。区間 [1, 3] の合計 (a1 + a2 + a3 = 2 + 3 + 4) は prefix[4] - prefix[1] = 10 - 1 = 9 で一発で求まります。

prefix の長さは元配列より 1 だけ長い。先頭の 0 のおかげで l = 0 のときも特別扱いせず prefix[r+1] - prefix[0] で計算できる。

各言語での実装

Python、JavaScript、Java、Go のいずれも考え方は同じです。先頭に 0 を入れた長さ n + 1 の配列を埋めてから、引き算で範囲合計を返します。

Python

def rangeSum(arr, l, r):
    n = len(arr)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + arr[i]
    return prefix[r + 1] - prefix[l]

JavaScript

function rangeSum(arr, l, r) {
  const n = arr.length;
  const prefix = new Array(n + 1).fill(0);
  for (let i = 0; i < n; i++) {
    prefix[i + 1] = prefix[i] + arr[i];
  }
  return prefix[r + 1] - prefix[l];
}

Java

public static int rangeSum(int[] arr, int l, int r) {
    int n = arr.length;
    int[] prefix = new int[n + 1];
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + arr[i];
    }
    return prefix[r + 1] - prefix[l];
}

func rangeSum(arr []int, l int, r int) int {
    n := len(arr)
    prefix := make([]int, n+1)
    for i := 0; i < n; i++ {
        prefix[i+1] = prefix[i] + arr[i]
    }
    return prefix[r+1] - prefix[l]
}

本問のように 1 回しかクエリがない場合は、累積和を作るより素朴に sum(arr[l:r+1]) の方が短く書けます。しかし「累積和を一度作っておけば次のクエリは O(1)」という設計上のメリットを理解することが目的です。

よくある間違い

1 つ目は prefix の長さを n にしてしまう こと。prefix[r + 1] を参照したいので、長さは n + 1 必要です。先頭の 0 を忘れると、l = 0 のとき特別扱いが必要になります。

2 つ目は インデックスのズレ 。範囲 [l, r] (両端含む) と [l, r) (右端含まず) で式が変わります。本問では 両端を含む ので prefix[r + 1] - prefix[l] が正解です。

3 つ目は 負の値を含む配列を考えない こと。累積和は値の符号に関係なく成立しますが、r = -1 のような無効インデックスを渡さないこと、l > r のような無効区間を渡さないことは仕様で前提とします。

やってみよう

arr = [1, 2, 3, 4, 5] で l = 1, r = 3 のとき 9 が返る。
l = 0, r = 0 で a0 が返る (本問では arr[0])。
同じ累積和配列を使って、別の (l, r) で合計を瞬時に求められることを実感する。これが本来の威力。

累積和は「データを並べておけば差分で範囲集計ができる」という考え方の入口。1D だけでなく 2D 累積和 や 差分配列 にも発展する。

発展: 2D 累積和と差分配列

累積和は 2 次元配列にも拡張できます。グリッド grid[i][j] に対して prefix[i][j] = grid の (0,0) から (i-1,j-1) までの合計 を計算しておけば、任意の長方形領域の合計が 4 つの累積和の足し引き で O(1) で求まります。画像処理の integral image (積分画像) もこの考え方で、フィルタや顔検出の高速化に使われています。

累積和の 逆操作 が 差分配列 です。diff[i] = arr[i] - arr[i - 1] を考えると、arr[i] = diff[0] + diff[1] + ... + diff[i] で復元できます。差分配列を使うと「範囲 [l, r] に一律 +v する」操作が O(1) で行えるため、範囲加算 + 一括反映 のパターンで強力に効きます。累積和と差分配列はセットで覚えると、競技プログラミングや時系列データ処理で重宝します。

実務での応用

アクセスログから「直近 24 時間ごとの売上集計」を瞬時に表示したい、というケースで累積和は本領を発揮します。1 度 O(n) で累積和を作っておけば、ユーザーがどんな時間範囲を指定しても O(1) で答えられます。データベースのインデックスやマテリアライズドビューも、本質的には同じ「事前計算で問い合わせを高速化する」発想に立っています。

よくある質問

Q. このトピックを覚える意味は何ですか？

A. 累積和は「前処理で重い計算を済ませ、各クエリを高速化する」という発想の入口です。範囲集計・区間更新・2D集計など、実務でも競技プログラミングでも繰り返し登場する基本パターンなので、一度身に付けると応用範囲が広く、実務での問題解決スピードが格段に上がります。

Q. 実務でこの知識を使う場面は？

A. 時系列データの期間指定集計（例「直近 N 日の売上合計を瞬時に返す」）、ダッシュボードの範囲フィルタ、画像処理の積分画像 (integral image) による高速フィルタ、差分配列を使った範囲一括加算など、多くの場面で応用されます。一度 O(n) で前処理しておけばクエリが何回来ても O(1) で返せるため、データ量が多いシステムほど効果が大きくなります。

Q. 他の章とどう繋がりますか？

A. 後続の章で扱うデータ構造（スタック・キュー）、アルゴリズム（探索・ソート）の基礎になります。累積和は配列の前処理テクニックの入口で、後続のセグメント木・BIT（フェニック木）・差分配列など、より高度な区間クエリ構造の前提知識になります。

次のレッスン

次は 第3章まとめクイズ で、これまで学んだ内容の理解度を確認しましょう。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

累積和の要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. 累積和とは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

累積和で範囲合計