期間ごとの売上の合計

累積和
問題 03
ふつう
目安 31 分

毎日の売上と、何日目から何日目までの合計を知りたいかという質問が何度も与えられる。累積和で、質問ごとに全部を足し直さずに答える練習です。

本番の試験は PC で受けることが多いので、PC での練習をすすめます。スマホでも、読んで、書いて、採点するところまで動きます。

入力は標準入力から読み、答えは標準出力に書きます。1 テストあたり 2 秒までです。

問題

ある店の、N 日間の毎日の売上が与えられます。そのあとに Q 個の質問が続きます。質問は 2 つの整数 l と r で、「l 日目から r 日目まで (l 日目と r 日目を含む) の売上の合計はいくらか」を表します。Q 個の質問のそれぞれに、答えを 1 行ずつ出力してください。

入力の形式

N Q
a_1 a_2 ... a_N
l_1 r_1
l_2 r_2
...
l_Q r_Q

1 行目に日数 N と質問の数 Q、2 行目に毎日の売上 a_i が半角の空白 1 つで区切られて並びます。3 行目から Q 行は、1 行に 1 つの質問です。

出力の形式

Q 行を出力します。k 行目に、k 番目の質問の答えを書きます。

制約

N と Q は、どちらも 1 以上 100000 以下です
売上 a_i は、0 以上 1000 以下の整数です
質問は、1 以上 l 以下 r 以下 N 以下を満たします

入力と出力の例

例 1

5 日間の売上が 3、1、4、1、5 です。1 日目から 5 日目までの合計は 14、2 日目から 3 日目までは 1 + 4 で 5、4 日目だけなら 1 です。

入力

出力

14
5
1

例 2

1 日だけで、質問も 1 つだけのときです。

入力

1 1
7
1 1

出力

ヒント

まだ開いていません

付箋は 3 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3答えに近い

全部のテストに通ると、解答と考え方が開きます。

先にヒントを試すと、自分で解けた手応えが残ります。どうしても詰まったときは、ここから開けます。

解答

売上を先頭から足していき、「1 日目から i 日目までの合計」を s[i] に並べて持ちます (s[0] は 0)。l 日目から r 日目までの合計は s[r] - s[l - 1] です。累積和を作るのが O(N)、1 つの質問に答えるのが O(1) なので、全部で O(N + Q) です。

Python

import sys

data = sys.stdin.read().split()
n, q = int(data[0]), int(data[1])
sales = list(map(int, data[2:2 + n]))

prefix = [0] * (n + 1)
for i in range(n):
    prefix[i + 1] = prefix[i] + sales[i]

answers = []
for i in range(q):
    l = int(data[2 + n + 2 * i])
    r = int(data[3 + n + 2 * i])
    answers.append(prefix[r] - prefix[l - 1])

print("\n".join(map(str, answers)))

JavaScript

const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter(Boolean).map(Number);
const n = data[0];
const q = data[1];
const sales = data.slice(2, 2 + n);

const prefix = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) {
  prefix[i + 1] = prefix[i] + sales[i];
}

const answers = [];
for (let i = 0; i < q; i++) {
  const l = data[2 + n + 2 * i];
  const r = data[3 + n + 2 * i];
  answers.push(prefix[r] - prefix[l - 1]);
}

console.log(answers.join("\n"));

計算量

時間は O(N + Q) です。質問のたびに l 日目から r 日目までを足し直す書き方は、1 つの質問に O(N)、全部で O(N × Q) かかります。Python の sum(sales[l - 1:r]) のように 1 行で書いても、中では同じ数だけ足しているので、N と Q が 10 万の入力では時間切れになります。

よくある間違い

累積和の 0 番目に 0 を置かず、l が 1 のときに s[l - 1] が範囲の外になる、または最初の日が数え落とされる
日付が 1 から数える入力なのに、配列の番号が 0 から数えることを忘れて、1 つずれる。s[r] - s[l - 1] の l - 1 を s[l] と書くと、l 日目の売上が引かれてしまいます
答えを 1 つずつ print して出力が遅くなる。Q が 10 万行なら、まとめて 1 回で出力するほうが速く書けます
入力を input() で 1 行ずつ読んで、Python で 10 万行の読み込みに時間を使いすぎる。sys.stdin.read() で全部を一度に読むと速くなります

解答を動かした版 Python 3.12.14Node.js 22.23.4確認日 2026/10/31

main.py

import sys

data = sys.stdin.read().split()
n, q = int(data[0]), int(data[1])
sales = list(map(int, data[2:2 + n]))
queries = [(int(data[2 + n + 2 * i]), int(data[3 + n + 2 * i])) for i in range(q)]

# ここから書く

入力

出力

「実行する」を押すと、ここに出力が出ます

できているか「提出して採点」を押すと、隠れたテストを全部走らせて、通ったかをここに出します