今回は paiza の「累積和」の問題に挑戦！
問題概要
問題：
- 長さ N の数列 A = [A₁, A₂, …, Aₙ]
- 整数 K個 のクエリ Q₁, Q₂, …, Qₖ（それぞれ 1 ≤ Qi ≤ N）
要求：
各 Qi に対して、
A₁ + A₂ + … + A_{Qi} の和（＝ 先頭から Qi 番目までの合計）を 高速に求めること。
入力例:
10 3
45
74
-94
68
-63
19
-47
-69
38
60
9
5
5
出力例:
-29
30
30
🔺 NG例：タイムオーバー
const rl = require('readline').createInterface({input:process.stdin});
const lines = [];
rl.on('line', (input) => lines.push(input));
rl.on('close', () => {
const [N, K] = lines[0].split(' ').map(Number);
const arrA = lines.slice(1, N+1).map(Number);
const query = lines.slice(N+1).map(Number);
const result = []
for(const q of query){
const temp = arrA.slice(0, q);
result.push(temp.reduce((acc, cur) => acc + cur, 0));
}
console.log(result.join('\n'));
});
- 各クエリで
arrA.slice(0, q)を毎回作成してreduceしている → 毎回 O(q) の計算。
- クエリが多い または、
qが大きいと、時間がかかる可能性がある。
✅ OK例：
const rl = require('readline').createInterface({ input: process.stdin });
const lines = [];
rl.on('line', (input) => lines.push(input));
rl.on('close', () => {
const [N, K] = lines[0].split(' ').map(Number);
const arrA = lines.slice(1, N + 1).map(Number);
const query = lines.slice(N + 1).map(Number);
// 累積和を作成（長さ N+1）
const prefixSum = [0];
for (let i = 0; i < N; i++) {
prefixSum[i + 1] = prefixSum[i] + arrA[i];
}
// 各 q について O(1) で出力
const result = query.map(q => prefixSum[q]);
console.log(result.join('\n'));
});
-
prefixSum[q]にはA[0]〜A[q-1]の合計が入っている。
-
prefixSum[0] = 0を入れることで、1-based（1番目からq番目）っぽく扱えて、計算が楽になる
-
sliceやreduceを使わないので、超高速＆省メモリ。
🗒️ まとめ
- 累積和 (
prefixSum)：配列の部分和を高速で求めるためのテクニック。
- 使いどき：同じ配列に対する部分和のクエリが複数あるとき。
- 書き方のコツ：先頭に
0を追加することで「最初から i 番目までの和」をprefixSum[i]で求められる。
- TLE 回避の鍵：クエリごとに
sliceやreduceを使わず、事前に計算しておく。