累積和とは｜競技プログラミング初心者向けにわかりやすく解説

累積和とは

累積和（cumulative sum / prefix sum）は、配列の「先頭からの合計」をあらかじめ計算しておくことで、あとから好きな区間の合計を一瞬で求められるようにするテクニックです。

競技プログラミングでは、「配列の l 番目から r 番目までの合計を何度も求めたい」という場面がよく出てきます。毎回ループで足し合わせていると遅くなりますが、事前に累積和を作っておけば、どんな区間でも引き算 1 回で答えが出せるようになります。

累積和の嬉しいところは、次の 2 点です。

• 実装が短く、書きやすい
• 区間和を求めるクエリが O(1) になる（つまり一瞬で答えられる）

アルゴリズムというよりは前処理のテクニックに近いのですが、知っているだけで解ける問題が一気に増える、とても強力な道具です。

まずはイメージから：テストの合計点

累積和の考え方は、次のような場面を想像するとわかりやすいです。

あなたは 10 回のテストを受けた。先生から、「3 回目から 7 回目までの合計点は？」「5 回目から 9 回目までの合計点は？」というふうに、いろいろな区間の合計を何度も聞かれる。

聞かれるたびに「3 回目から 7 回目までの点数を足す…」と計算していたら大変です。そこで、「1 回目から i 回目までの合計点」を最初に全部計算してメモしておきます。

i	1	2	3	4	5	6	7
テストの点数	60	80	70	90	50	100	85
1〜i の合計点	60	140	210	300	350	450	535

こうしておくと、例えば「3 回目から 7 回目までの合計」は、

(1〜7 の合計) - (1〜2 の合計) = 535 - 140 = 395

というふうに、引き算 1 回で答えが出せます。これが累積和の基本的な発想です。

配列に対する累積和

それでは、配列に対して累積和を作る流れを見ていきましょう。

累積和の定義

元の配列を A[0], A[1], ..., A[N-1] とします。累積和の配列 S を、次のように定義します。

• S[0] = 0
• S[i] = A[0] + A[1] + ... + A[i-1]（i ≥ 1）

つまり、S[i] は「A の先頭から i 個の合計」です。S[0] = 0 としておくのがポイントで、こうすると区間和の式がきれいに書けます。

区間和を求める公式

A[l], A[l+1], ..., A[r-1] の合計（半開区間 [l, r) の和）は、累積和を使うと次のように書けます。

A[l] + A[l+1] + ... + A[r-1] = S[r] - S[l]

![区間和 l, r) = S[r] - S[l] を表す図

たったこれだけです。どんなに長い区間でも、引き算 1 回 = O(1) で答えが求められます。

具体例

元の配列 A = [3, 1, 4, 1, 5, 9, 2, 6] を例に、累積和 S を作ってみましょう。

i	0	1	2	3	4	5	6	7	8
A[i]	3	1	4	1	5	9	2	6
S[i]	0	3	4	8	9	14	23	25	31

たとえば「A[2] から A[5] までの合計」（つまり 4 + 1 + 5 + 9 = 19）を累積和で求めると、

S[6] - S[2] = 23 - 4 = 19

となり、一致します。

C++ での実装

累積和の作り方と使い方を、そのままコードにするとこうなります。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, Q;
    cin >> N >> Q;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];

    // 累積和 S を作る（S の長さは N+1）
    vector<long long> S(N + 1, 0);
    for (int i = 0; i < N; i++) {
        S[i + 1] = S[i] + A[i];
    }

    // Q 個のクエリに答える：[l, r) の区間和を出力
    for (int q = 0; q < Q; q++) {
        int l, r;
        cin >> l >> r;
        cout << S[r] - S[l] << endl; // O(1) で答えられる
    }

    return 0;
}

ポイントは 3 つです。

1. 累積和の配列は、元の配列より 1 つ長い（N + 1 要素）
2. S[0] = 0 から始めて、S[i + 1] = S[i] + A[i] で順番に足していく
3. 区間 [l, r) の和は S[r] - S[l]

累積和の作成は O(N)、各クエリの応答は O(1) なので、クエリが Q 個あっても全体で O(N + Q) で処理できます。全探索で毎回足すと O(N × Q) かかるので、違いは非常に大きいです。

計算量：なぜこんなに速いのか

例えば N = 100,000、Q = 100,000 のような問題を考えてみましょう。

• 毎回ループで足す：1 回あたり最大 N 回、合計で N × Q = 100 億回 → 間に合わない
• 累積和を使う：前処理 N 回 + 各クエリ 1 回、合計で N + Q = 20 万回 → 一瞬

方針	前処理	1 クエリあたり	合計
毎回ループで足す	なし	O(N)	O(N × Q)
累積和	O(N)	O(1)	O(N + Q)

「同じ配列に対して何度も区間和を聞かれる」場面では、累積和を使わない理由がほぼない、と言ってもいいくらい強力です。

応用：2 次元の累積和（発展）

ここから先はかなり難しい内容です。まずは 1 次元の累積和を完全に使いこなせるようになってからで十分なので、最初はサラッと目を通すだけでも構いません。

累積和は 1 次元だけでなく、**2 次元の表（グリッド）**にも拡張できます。

H × W のマス目があり、各マスに数字が書かれている。好きな長方形の範囲の合計を何度も聞かれる。

1 次元と同じ発想で、「左上 (0, 0) から (i, j) までの長方形の合計」を表す 2 次元累積和 S[i][j] を作っておけば、任意の長方形の合計が引き算だけで求められます。

2 次元累積和の公式

左上 (r1, c1)、右下 (r2 - 1, c2 - 1) の長方形（半開区間）の合計は、

S[r2][c2] - S[r1][c2] - S[r2][c1] + S[r1][c1]

で求められます。同じ部分を 2 回引いてしまうので、最後に 1 回足し直すのがポイントです。

2 次元でも、前処理 O(HW)、各クエリ O(1) で答えられます。ただし、式の意味を正しく理解して実装するのは簡単ではないため、二次予選の中でも難しめの問題に挑戦したい人はぜひここまでマスターしてみてください。逆に、まずは一次予選を突破したいという段階なら、1 次元の累積和を確実に使えるようにする方が優先です。

つまずきやすいポイント

1. 累積和の配列は「1 つ長い」ことを忘れがち

累積和の配列 S は、元の配列 A より 1 つ長く取ります（長さ N + 1）。これを忘れて A と同じ長さで作ってしまうと、S[r] - S[l] の式がきれいに書けず、端の処理で条件分岐が必要になって混乱します。

「S[0] = 0 から始めて、S[i + 1] = S[i] + A[i]」を定型文として覚えてしまうのがオススメです。

2. 区間の「閉じ方」で添字がずれる

競技プログラミングでは、区間の表し方が問題によって違います。

• 半開区間 [l, r)：A[l], A[l+1], ..., A[r-1] の合計 → S[r] - S[l]
• 閉区間 [l, r]：A[l], A[l+1], ..., A[r] の合計 → S[r + 1] - S[l]

どちらの区間なのかを問題文で必ず確認しましょう。1 つずれるだけで WA（不正解）になります。

3. 合計がオーバーフローする

累積和はたくさんの値を足し合わせるので、合計が int の範囲（約 21 億）を超えることがあります。競技プログラミングでは基本的に long long を使うのが安全です。

vector<long long> S(N + 1, 0); // long long にしておくと安心

「A[i] 1 つ 1 つは小さくても、全部足したら桁が大きくなる」というのは累積和に限らずよくある落とし穴なので、常に意識しておきましょう。

まとめ

今回のポイントまとめです。

• 先頭からの合計を事前に計算しておく前処理のテクニック
• 区間和が O(1) で求められるので、同じ配列への区間和クエリが多いときに絶大な効果
• S[0] = 0、S[i + 1] = S[i] + A[i]、[l, r) の和は S[r] - S[l]
• 2 次元への拡張、差分更新と組み合わせたいもす法など応用も豊富

累積和は実装も短く、考え方もシンプルですが、使える場面を見抜けるかどうかで解ける問題の幅が大きく変わってきます。JOI 一次予選・二次予選でも頻出なので、ぜひマスターしてください。

練習問題に挑戦しよう

アルゴリズムは「読んで理解した」だけでは使えるようになりません。実際に自分の手で書いて、問題を解くことで初めて身につきます。

HaruCoder のオンライン受講では、累積和を使う問題を難易度順に用意しており、提出すれば自動で採点されます。「次に何を解けばいいかわからない」という悩みもなく、段階的にステップアップできます。

また、まだ競技プログラミングを始めたばかりで「そもそもどうやって問題を解くの？」という方は、先に以下の記事を読んでみてください。

• 競技プログラミングの始め方 — ブラウザだけで 1 問解く流れを画像付きで解説
• JOIの難易度全解説 — 累積和が実際に役立つコンテストの全体像