累積和で区間を引き算にする
区間を何度も足す代わりに、先頭からの合計を保存します。区間を半開区間 [l,r) に統一すると境界が揃います。
言語：Python / 計算量：前処理 O(N)、各質問 O(1)
考え方
- s[0]=0 を用意。
- s[i+1]=s[i]+a[i]。
- [l,r) の和は s[r]-s[l]。
具体例
a=[3,1,4,2]、s=[0,3,4,8,10]。[1,3) は1+4=5。s[3]-s[1]=8-3。
実装
a = [3, 1, 4, 2]
s = [0]
for x in a:
s.append(s[-1] + x)
print(s[3] - s[1])注意する条件
要素が更新されるたびに作り直すと O(N)。更新が多ければ Fenwick tree などを検討します。
確認問題
a=[2,5,1] の [1,3) の和は？
解答と理由
6
添字1と2の値、5+1です。
実装課題
N Q、配列 A、続いて Q 行の l r。0 ≤ l ≤ r ≤ N。各 [l,r) の和を出力。N,Q ≤ 200000。
入力:
3 2
2 5 1
0 2
1 3
出力:
7
6参考実装
import sys
input = sys.stdin.readline
n, q = map(int, input().split())
s = [0]
for x in map(int, input().split()):
s.append(s[-1] + x)
for _ in range(q):
l, r = map(int, input().split())
print(s[r] - s[l])実戦につなげる補講
一度に全て読まなくて大丈夫です。今日は1節と1問から。
遅いコードを先に書く
区間[l,r)を求めるたびsum(a[l:r])と書けば、短い例では正しく答えられます。しかし長い区間がQ回続くとO(NQ)です。どの区間も元の列は同じなのに、同じ要素を何度も足し直しています。
境界に名前を付ける
s[k]を「先頭からk個の合計」と決めます。s[0]=0、s[k+1]=s[k]+a[k]。sはN+1個です。区間[l,r)の合計はs[r]−s[l]。rを含まない約束なら、l=rの空区間も自然に0になります。
引き算で消える部分を手で追う
a=[4,1,7,2]ならs=[0,4,5,12,14]。区間[1,3)は1+7=8で、s[3]−s[1]=12−4=8。先頭側の4を取り除き、欲しい区間だけが残ります。
使える条件と限界
値が途中で変わらないときに強い方法です。1要素を書き換えると後ろの累積値が変わります。更新が何度も来る問題ではFenwick tree等を検討します。また区間の最小値は引き算では復元できません。
段階式の追加演習
1. 境界を手で追う
a=[4,1,7,2]について[0,4)、[2,2)、[3,4)の和を答えて。
ヒント
s[r]−s[l]をそのまま使う。
解答と理由
14、0、2。全区間・空区間・末尾1個を確認すると添字のずれを見つけやすい。
2. 実装：質問をまとめて答える
0始まり半開区間の質問queriesに対し、区間和のリストを返すrange_sumsを書いて。
ヒント
sを1回だけ作り、各質問は引き算。
解答と理由
前処理O(N)、質問合計O(Q)、追加メモリO(N+Q)。返す答えのリストにもQ個分を使う。
def range_sums(a, queries):
s = [0]
for x in a:
s.append(s[-1] + x)
return [s[r] - s[l] for l, r in queries]3. 公式入力の添字を変換
1始まりで両端を含むL〜Rが与えられた。0始まり半開区間にすると？
ヒント
最初の要素の添字だけ1引く。右端は境界。
解答と理由
[L−1,R)。答えはs[R]−s[L−1]。L=R=1なら先頭1個になるか確認する。
4. 発見の練習：個数にも使える？
文字列の区間にAが何個あるかを何度も聞かれる。和の問題ではないが累積和を使える？
ヒント
各文字を0か1に置き換える。
解答と理由
Aなら1、それ以外なら0の列を作れば、区間の合計がAの個数になる。データを何に置き換えるかも解法の一部。
公式過去問への橋渡し
ABC098 C / 公式解説PDF
候補を1つ動かしたときに、左側と右側の集計を毎回やり直す必要があるか考える。
公式問題 / 公式解説見本を閉じて確認
- 何を繰り返しているかを説明できる
- 使える条件と使えない条件を1つずつ言える
- 見本を閉じて実装し、小さい入力で確かめられる