今回はpaizaのクエリで「区間和」の問題に挑戦！
初めはその区間の値を取り出して合計を計算する関数を作って解いたけど、前回の累積和を利用した方が実行時間が短かった！
問題概要
- 長さ N の数列 A が与えられる。
- K 個の区間クエリ (l_i, r_i) が与えられる。
- 各クエリについて、区間 A_{l_i} から A_{r_i} までの和を求める。
- 入力は1-indexedの区間指定。
- 出力は各クエリに対して求めた区間和を順に表示。
入力例1
4 2
16
88
10
-65
2 4
1 2
出力例1
33
104
🔺75点のコード：タイムオーバー
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);
for(const q of query){
const [l, r] = q.split(' ').map(Number);
const temp = arrA.slice(l-1, r);
const result = temp.reduce((acc, cur) => acc + cur, 0);
console.log(result);
}
});
毎回 slice して reduce してるから、K が多いとめちゃくちゃ遅い！
✅ 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);
function rangeSum (l, r) {
let result = 0;
for(let i = l - 1; i < r; i++){
result += arrA[i];
}
return result;
}
for(const q of query){
const [l, r] = q.split(' ').map(Number);
console.log(rangeSum(l, r));
}
});
✨最速コード例？：累積和配列を使って区間和をO(1)で求める方法
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);
const prefixSum = [0];
for (let i = 0; i < arrA.length; i++) {
prefixSum[i+1] = prefixSum[i] + arrA[i];
}
for (const q of query) {
const [l, r] = q.split(' ').map(Number);
const result = prefixSum[r] - prefixSum[l - 1];
console.log(result);
}
});
-
前処理：O(N)
-
各クエリ：O(1)
-
計：O(N + K) → 非常に高速！
-
prefixSum[i]=arrA[0]からarrA[i-1]までの和(累積和) -
prefixSum[r] – prefixSum[l-1]=arrA[l-1]からarrA[r-1]までの和(区間和)
🔍 区間 arrA[l〜r] の和を求めるとき
問題のクエリでは：
- クエリ
l = 3,r = 6（1-indexed） - 対応する
arrAの範囲：arrA[2]～arrA[5] - 合計は
arrA[2]+arrA[3]+arrA[4]+arrA[5]
それはつまり、累積和的には：
prefixSum[6] – prefixSum[2]
-
prefixSum[6]はarrA[0]～arrA[5]の累積和 -
prefixSum[2]はarrA[0]〜arr[1]の累積和
なので、
prefixSum[6] – prefixSum[1] は arrA[2] +arrA[3] + arrA[4] + arrA[5]
つまり、
prefixSum[r] – prefixSum[l-1]
クエリの区間の終わりまでの累積和から、クエリの区間より前の累積和を引くことで区間和が求められる！
🗒️ まとめ
- 単純に
forループやslice+reduceで区間和を計算すると計算量が高く、タイムアウトの原因になる。
- 累積和（prefix sum）配列を事前に作ることで、各区間和の計算をO(1)にできる。
- 累積和配列 prefixSum の i 番目は「arrA の先頭から i-1 までの合計」を格納する。
- 区間和は
prefixSum[r] – prefixSum[l-1]で計算可能。- クエリの区間の終わりまでの累積和から、クエリの区間より前の累積和を引く
- l, r は 1-indexed
- 累積和を使うことで全クエリに対し効率的に処理できる（計算量は O(N + K)）。
- 配列の添字のズレ（0-indexed と 1-indexed）に注意し、累積和配列を0番目に0を入れることで扱いやすくなる。