[JS] 구간 합 시간 초과 해결하기

BOJ 11659 : 배열이 주어지고, 여러 번의 구간합을 구하는 문제.

구간합을 매번 직접 계산하면 O(n*m)시간 복잡도가 발생한다.

누적합을 이용하면 O(1)로 구간합을 구할 수 있다.

• 배열의 각 위치까지 누적합을 미리 계산해두고, 구간 합을 빠르게 구하는 기법
• 예를 들어 3부터 5까지의 합이면, 5까지의 누적합 - 2까지의 누적합 하면 되니까 빠르게 계산 가능!

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const [n, m] = input[0].split(' ').map(Number);

input.shift();
let list = input[0].split(' ').map(Number);

// ✅ 누적 합 배열 생성 (Prefix Sum)
let prefixSum = Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) {
    prefixSum[i] = prefixSum[i - 1] + list[i - 1];
}

input.shift();

// ✅ 쿼리 처리 (O(1) 연산)
let result = [];
for (let i = 0; i < m; i++) {
    const [a, b] = input[i].split(' ').map(Number);
    result.push(prefixSum[b] - prefixSum[a - 1]);  // O(1)로 구간 합 계산
}

console.log(result.join('\n'));  // 한번에 출력 (출력 시간 최적화)