区間和の計算

今回は paiza の「区間和の計算」の問題に挑戦！

🧩 問題概要

• 長さ N の数列 A が与えられる
• 続いて n 個のクエリ が与えられる
• 各クエリでは
  • 整数 l, u が与えられ
  • A[l] から A[u] までの合計 を求める
• 各クエリの答えを 1行ずつ出力 する

入力例:

10                  // N
0 1 2 3 4 5 6 7 8 9 // A
5                   // n
0 1                 // l_1 u_1
0 4
3 8
2 9
1 3

出力例:

1
10
33
44
6

✅ OK例：

const rl = require('readline').createInterface({ input: process.stdin });

const lines = [];

rl.on('line', (inputLine) => lines.push(inputLine));

rl.on('close', () => {
    const N = Number(lines[0]);
    const arrA = lines[1].split(' ').map(Number);
    const n = Number(lines[2]);
    const query = lines.slice(3).map(line => line.split(' ').map(Number));
    
    // 区間和を返す関数
    function rangeSum(l, u) { 
        let sum = 0;
        for (let i = l; i <= u; i++) {
            sum += arrA[i];
        }
        return sum;
    }
    
    // クエリ
    for (let i = 0; i < n; i++) {
        const [l, u] = query[i];
        console.log(rangeSum(l, u));
    }
});

🔍 コードの流れ

• 標準入力を1行ずつ読み取り、配列 lines に保存する
• 1行目から数列の長さ N を取得する
• 2行目から数列 A を配列 arrA として読み込む
• 3行目からクエリ数 n を取得する
• 残りの行を、各クエリ (l, u) の配列 query として読み込む
• 区間 [l, u] の合計を計算する関数 rangeSum を定義する
  • l から u までループし、要素を順に足し合わせる
• 各クエリについて
  • rangeSum(l, u) を呼び出す
  • 計算結果をそのまま出力する

✨ OK例：累積和を使った解法

const rl = require('readline').createInterface({ input: process.stdin });

const lines = [];

rl.on('line', line => lines.push(line));

rl.on('close', () => {
    const N = Number(lines[0]);
    const arrA = lines[1].split(' ').map(Number);
    const n = Number(lines[2]);
    const queries = lines.slice(3).map(line => line.split(' ').map(Number));

    // ① 累積和配列を作る
    // prefix[i] = arrA[0] + arrA[1] + ... + arrA[i-1]
    const prefixSum = Array(N + 1).fill(0);
    for (let i = 0; i < N; i++) {
        prefixSum[i + 1] = prefixSum[i] + arrA[i];
    }

    // ② クエリに答える
    let output = [];
    for (const [l, u] of queries) {
        output.push(prefixSum[u + 1] - prefixSum[l]); // 区間和
    }

    console.log(output.join('\n'));
});

🔍 コードの流れ

① 累積和を先に作る（1回だけ）

• prefixSum[0] = 0
• prefixSum[i+1] = prefixSum[i] + A[i]
  ここで全ての合計情報を保存

② クエリは引き算だけ

• 区間 [l, u] の和：prefixSum[u + 1] – prefixSum[l]

※ prefixSum は「i 未満までの合計」を持つ配列だから u まで含めたいなら u + 1 が必要。

🗒️ まとめ

• 「同じ配列に対して区間和を何度も求める」 問題

• 素直な解法（毎回ループ）
  • 各クエリで l〜u を走査
  • 実装は簡単だが 計算量が大きい
• 条件が大きいと、毎回ループする解法は間に合わない

• 💡 解決策 → 累積和
  • あらかじめ「先頭からの合計」を保存
• 累積和の定義が重要
  • prefixSum[i] = A[0] 〜 A[i-1] の合計
• 区間和は 引き算だけで求まる
  • [l, u] = prefixSum[u+1] - prefixSum[l]

• 計算量が劇的に改善
  • 前処理：O(N)
  • 各クエリ：O(1)
• 今後の問題では、「先に情報を貯められないか？」を考えることがポイントかも！