累積和（１次元）

問題

$ N $ 日間のイベントが開催され、$ i $ 日目には $ A_i $ 人が来場しました。

以下のような $ Q $ 個の質問に答えて下さい・

🔹質問１：$ L_1 $ 日目から $ R_1 $ 日目までの総来場者数は何人ですか。
　　　・
　　　・
🔹質問Ｑ：$ L_q $ 日目から $ R_q $ 日目までの総来場者数は何人ですか。

[制約]
🔹$ 1 \leqq N \leqq 100000 $
🔹$ 1 \leqq Q \leqq 100000 $
🔹$ 1 \leqq A_i \leqq 10000 $
🔹$ 1 \leqq L_q \leqq R_q \leqq N $

解き方・ソースコード

累積和を使うと、$L$日目から$R$日目までの総来場者数は下記の計算式で求めることができます。

$$ (R日目までの累計来場者数) - (L-1日目までの累計来場者数) $$

また累積和は、以下のように計算すると計算量$ O(N) $で求めることができます。

🔹$S_0 = 0$とする。
🔹$i=1,2,3,…,N$の順に、$S_i=S_{i-1} + A_i$とする。

累積和の計算に $O(N)$、質問に答える処理に $O(Q)$ かかるので、プロブラム全体の計算量は $O(N+Q)$ となります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#-------- 入力例１ ---------
N = 15          # イベント開催日数
Q = 3           # 質問の数
# イベント日ごとの来場者数
A = [621, 652, 410, 143, 260, 101, 158, 464, 573, 182, 198, 107, 134, 102, 449]
L = [4, 3, 2]       # カウントする期間の開始日
R = [13, 10, 15]    # カウントする期間の終了日
#---------------------------
S = [ None ] * (N + 1)
S[0] = 0
for i in range(N):
    S[i + 1] = S[i] + A[i]
 
for j in range(Q):
    print('{}日目から{}日目までの総来場者数は {} 人です。'.format(L[j], R[j], S[R[j]] - S[L[j] - 1]))

[実行結果（入力例１）]

4日目から 13日目までの総来場者数は 2320 人です。

3日目から 10日目までの総来場者数は 2291 人です。

2日目から 15日目までの総来場者数は 3933 人です。

期間ごとの総来場者数をカウントすることができました。