Day 002-Q4 | 累積和（1次元）

問題

N 個の整数からなる数列 A がある。Q 個のクエリが与えられ、各クエリで整数 L, R が与えられる。A[L] + A[L+1] + ... + A[R] の合計を答えよ（1-indexed）。

入力形式

N Q
A_1 A_2 ... A_N
L_1 R_1
...
L_Q R_Q

制約

$1 \le N \le 10^5$

$1 \le Q \le 10^5$

$1 \le L_i \le R_i \le N$

$|A_i| \le 10^9$

入出力例

入力例 1

出力例 1

6
14
3

A[1..3]=6, A[2..5]=14, A[3..3]=3

ヒント (段階的開示)

ヒント1: 方向性

愚直に計算すると O(NQ) = 10^10 で TLE。事前処理でクエリを O(1) にできる。

ヒント2: アプローチ

prefix[i] = A[1]+...+A[i] を事前計算。A[L..R] = prefix[R] - prefix[L-1] で O(1)。

ヒント3: 誘導

prefix = [0] * (N + 1)
for i in range(N):
    prefix[i + 1] = prefix[i] + A[i]

ans = prefix[R] - prefix[L - 1]

模範解答 (Python)

import sys
input = sys.stdin.readline

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

prefix = [0] * (N + 1)
for i in range(N):
    prefix[i + 1] = prefix[i] + A[i]

for _ in range(Q):
    L, R = map(int, input().split())
    print(prefix[R] - prefix[L - 1])

Step-by-Step 解説

1累積和配列の意味
prefix[i] = A[1] から A[i] までの合計。prefix[0]=0 を番兵として配置。

2区間和の計算
A[L..R] = prefix[R] - prefix[L-1]。例: A[2..4] = prefix[4] - prefix[1] = 10 - 1 = 9。

3高速入力
Q=10^5 のクエリで sys.stdin.readline を使うと安定して高速。

計算量

前処理: $O(N)$
各クエリ: $O(1)$
合計: $O(N + Q)$

よくあるミス

ミス	原因	正しい書き方
`prefix[L]` を使う	L-1 が必要	`prefix[L-1]`
`[0] * N`	範囲外	`[0] * (N+1)`
毎回ループで合計	O(NQ) TLE	累積和を事前構築

Day 002-Q4 — 累積和（1次元）

問題