AIで解説 AtCoder攻略　累積和

累積和ページの位置づけ

項目	内容
必修度	必修
学習目安	入門〜標準
前提	入力・配列・ループ
対象問題	76問（推定値あり76問、未算出0問）

この記事のdifficulty区分は、問題を解く順番を決めるための目安です。AtCoderの公式なA〜F区分ではなく、取得できたdifficulty推定値を次の範囲に分けています。

学習目安	difficulty推定値	問題数
入門	difficulty < 0	22
標準	0〜799	25
標準〜発展	800〜1199	12
発展	1200以上	17
未算出	—	0

累積和は、難しい公式を覚えるアルゴリズムではありません。同じ足し算を何度も繰り返さないために、途中までの合計を保存して使い回す方法です。この記事では、普通に計算したときに何が遅くなるのか、なぜ累積和なら速くなるのかを、最も簡単な例から確認します。

まず計算量を比べる

配列の長さをN、区間の問い合わせ回数をQとします。計算量のO( )は、入力が大きくなったときに処理回数がどの割合で増えるかを表す目安です。O(N)なら要素数に比例し、O(1)なら区間の長さに関係なくほぼ一定回数で終わります。

方法	前処理	1回の問い合わせ	Q回の合計	追加メモリ
毎回その区間を足す	O(1)	O(N)（最悪）	O(NQ)	O(1)
累積和を作る	O(N)	O(1)	O(N + Q)	O(N)

累積和は、最初にO(N)の準備をします。その代わり、各問い合わせでは配列を歩かず、保存済みの値を2個読んで引くだけです。Qが少ないときは前処理の方が大きく見えることもありますが、Qが多い問題ではO(NQ)とO(N+Q)の差が決定的になります。

使わない場合、なぜO(NQ)になるのか

区間 [l, r) の合計を求める最も素直なコードは、問い合わせのたびにlからrの直前までを足します。

def range_sum_slow(values, left, right):
    total = 0
    for i in range(left, right):
        total += values[i]
    return total

一つの区間がN個の要素を含むなら、1回の問い合わせで最大N回の加算が必要です。これをQ回繰り返すため、最悪の場合はN×Q回、つまりO(NQ)になります。例えばN=100000、Q=100000なら、単純計算で最大100億回規模の加算です。隣り合う問い合わせが同じ要素を含んでいても、上のコードはその重複を知りません。

累積和は「共通部分」を一度だけ計算する

配列Aから、先頭からi個の合計をP[i]に保存します。P[0]は「0個の合計」なので0にします。この定義なら、P[r]はA[0]からA[r-1]まで、P[l]はA[0]からA[l-1]までの合計です。

A       :  2   1   3   4   2
index   :  0   1   2   3   4
P       :  0   2   3   6  10  12
            └── l=1 ─────── r=4 ┘
             P[4] - P[1] = 10 - 2 = 8

P[4]にはA[0]+A[1]+A[2]+A[3]が入っています。P[1]にはA[0]だけが入っています。そのため、P[4]からP[1]を引くと、共通していたA[0]が消え、A[1]+A[2]+A[3]だけが残ります。これが、区間の中身を毎回足し直さなくてもよい理由です。

区間 [l, r) の合計は、必ず P[r] - P[l] と書けます。右端rを含めない半開区間に統一すると、長さ0の区間やl=0も同じ式で処理できます。

例題：ABC129 B Balanceを解く

例題として、ABC129 B Balance（公式解説）を使います。左右に分けたときの合計の差を最小にする問題で、累積和の仕組みを最小限のコードで確認できます。difficulty推定値が最も低い問題を機械的に選ぶと、単純な区間計算だけで累積和を使わない問題も混ざります。ここでは、累積値を更新して左右の答えを復元する流れが一番見えやすい問題を例題に選んでいます。

累積和を使わない解き方

分ける位置を一つ決めるたびに、左側と右側をそれぞれ足し直すと次の形になります。

best = 10**18
for split in range(1, N):
    left = sum(A[:split])
    right = sum(A[split:])
    best = min(best, abs(left - right))

各splitで最大N個を足すため、分ける位置がO(N)個あると全体はO(N²)です。Pythonではスライスの作成にも要素数に比例した時間とメモリがかかるため、見た目より軽くなりません。

累積和を使う解き方

全体の合計と、各位置までの合計を一度だけ作ります。

N = int(input())
A = list(map(int, input().split()))

prefix = [0]
for value in A:
    prefix.append(prefix[-1] + value)

best = 10**18
for split in range(1, N):
    left = prefix[split]
    right = prefix[N] - prefix[split]
    best = min(best, abs(left - right))

print(best)

前半のprefix作成がO(N)、後半のsplit走査もO(N)です。したがって全体の計算量はO(N)で、prefixを保存する追加メモリはO(N)です。

小さな入力で追いかける

A=[1, 2, 3, 4, 5]なら、全体の合計は15です。分ける位置ごとに左側だけを累積すれば、右側は15から引いて求められます。

split	左側の合計	右側の合計	差
1	1	14	13
2	3	12	9
3	6	9	3
4	10	5	5

最小値は3です。表の左側の合計1→3→6→10が、同じ値を何度も足さずに前の値へ一つずつ足して作られている点に注目してください。

Pythonでは標準ライブラリを使える

累積値の生成には、標準ライブラリのitertools.accumulateが使えます。AtCoderでは外部パッケージを追加できないため、標準ライブラリか短い自作関数を使います。

from itertools import accumulate

def make_prefix(values):
    return [0] + list(accumulate(values))

prefix = make_prefix(A)

def range_sum(prefix, left, right):
    return prefix[right] - prefix[left]

accumulate(values)は、先頭からの合計を順に返します。区間問い合わせを後で何度も行うなら、listへ変換して保存します。保存せずに一度だけ読み取るだけなら、iteratorのまま使える場合もあります。標準ライブラリの確認は標準ライブラリ・定石へ戻れます。

累積和を使える条件

次の条件がそろったら、累積和を候補にします。

元の配列が、問い合わせの途中で変わらない。
区間の合計・個数・XORなど、同じ集約値を何度も求める。
O(N)の前処理とO(N)のメモリを使ってよい。

負の値があっても、足し算なので累積和はそのまま使えます。一方、値の更新が途中に入る場合は保存したprefixが古くなります。更新と問い合わせを混ぜるなら、Fenwick木・セグメント木で区間を更新するのFenwick Treeやセグメント木を検討します。

似た方法との使い分け

「前計算して再利用する」という考え方は同じでも、速くしたい操作が異なります。

やりたいこと	選ぶ方法	見分け方
静的な配列の区間和を何度も求める	累積和	問い合わせの間に値が変わらない
区間へ加算する操作をまとめ、最後に全要素を出す	差分配列（imos法）	更新が先に全部分かっている
正の値の連続区間を条件付きで探す	尺取り法で単調な区間を探す	左右の端点を戻さずに動かせる
更新しながら区間和を求める	Fenwick木・セグメント木で区間を更新する	問い合わせの途中で値が変わる
長方形の合計を求める	二次元累積和	行と列の両方にprefixを作る
区間の最小値・最大値を何度も求める	セグメント木・Sparse Table	引き算だけでは重複部分を消せない

累積和は「問い合わせを速くする」方法です。差分配列は「区間更新を速くする」方法なので、名前が似ていても向きが反対です。

つまずきやすいポイント

半開区間を最後まで守る

prefixの添字は「何個分を含むか」と解釈します。入力が閉区間 [L, R] なら、0始まりの半開区間 [L, R+1) へ直してから prefix[R+1] - prefix[L] と計算します。

prefixの長さをN+1にする

prefix = [0]から始めてN個追加すると、添字0からNまで使えます。これにより、先頭から始まる区間も空区間も特別扱いしません。

1始まりの入力を変換する

問題文のL,Rが1始まりなら、配列アクセス用の添字へ変換する場所を一箇所に決めます。変換後の式を [l, r) にそろえ、途中で1始まりへ戻さないことが安全です。

累積和を作った後に元配列を更新しない

元配列を変更したら、古いprefixとの差し引きは正しくありません。更新があるかどうかを、コードを書く前に制約と操作列から確認します。

累積和で区間と差を数えるで先に確認する文法・ライブラリ

まずは必須Python文法で、入力・配列・条件分岐・ループなどの基本を確認してください。問題に合わせたキュー、ヒープ、二分探索などの選び方は標準ライブラリ・定石にまとめています。

累積和で区間と差を数えるの練習問題

難易度だけでなく、静的な配列か、更新があるか、区間の端点がどちら向きかを確認して順番を決めます。

まず解く

問題	公式解説	出題意図	difficulty
ABC209 A Counting	公式解説	Count the integers from A through B inclusive.	-1380
ABC403 A Odd Position Sum	公式解説	公式Editorialの方針を odd position sum として整理する。	-1129
ABC348 A Penalty Kick	公式解説	Official editorial intent is classified as periodic penalty.	-1088
ABC318 A Full Moon	公式解説	Count full-moon dates by solving a simple arithmetic progression.	-934
ABC454 A Closed interval	公式解説	Check whether the closed intervals intersect.	-912

次に解く

問題	公式解説	出題意図	difficulty
ABC280 B Inverse Prefix Sum	公式解説	Recover A_i as S_i−S_{i−1} from the inverse prefix sums.	-769
ABC349 A Zero Sum Game	公式解説	Official editorial intent is classified as zero sum.	-702
ABC351 B Spot the Difference	公式解説	Official editorial intent is classified as grid difference find.	-585
ABC199 B Intersection	公式解説	Intersect all [A_i,B_i] intervals and count integer points in the resulting range.	-547
ABC288 B Qualification Contest	公式解説	先頭K人だけを辞書順に並べ替え、残りを保持して出力する。	-483

挑戦問題

問題	公式解説	出題意図	difficulty
ABC449 B Deconstruct Chocolate	公式解説	Reconstruct the chocolate pieces with a two-dimensional prefix sum.	-476
ABC261 A Intersection	公式解説	2つの閉区間の共通部分の長さを端点の最大最小で求める。	-423
ABC130 B Bounding	公式解説	移動距離の累積値を順に計算し、上限以下の位置を数える。	-300
ABC129 B Balance	公式解説	各分割位置で左右の合計を比較し、差の最小値を求める。	-182
ABC405 C Sum of Product	公式解説	公式Editorialの方針を prefix sum accumulation として整理する。	-146