応用情報技術者アルゴリズムとデータ構造オリジナル・公式資料照合難易度★★★☆☆

添字1～5の配列a={2,5,1,4,3}に対し、p[0]=0、p[i]=p[i−1]+a[i]で累積和を作る。添字3から5までの合計をO(1)時間で求める式と値の組はどれか。

p[5]−p[3]で7

p[5]−p[3]は添字4～5の合計7です。開始点3の要素1まで引いてしまいます。

p[5]−p[2]で8★ 正解

p[5]=15、p[2]=7なので差は8です。添字3～5の1+4+3に一致します。

p[5]−p[1]で13

p[5]−p[1]は添字2～5の合計13です。不要なa[2]=5も含みます。

p[5]+p[2]で22

二つの累積和を足すと先頭部分を重複して含みます。区間和には差を使います。

解説

両端を含む区間[l,r]の和はp[r]−p[l−1]です。事前計算O(n)の後、各区間の問合せはO(1)になります。

対応範囲：2026年度応用情報技術者試験

資料確認日：2026-10-28

ゲーミフィケーションで応用情報技術者合格を目指す。無料・課金なし。