Prefix Sum

1차원배열에서 i ~ k 번째 사이의 값들의 합을 구하는 Algorithm

구간 합(Prefix Sum)은 알고리즘은 이름 그대로 연속적으로 나열된 N개의 수가 있을 때 특정 구간의 모든 수를 합한 값을 계산한다.

예를 들어 5개의 데이터로 구성된 수열 $10, 20, 30, 40, 50$이 있다고 가정한다면, 2번째 수부터 4번째 수까지의 합은 $90(20 + 30 + 40)$ 이다.

Problem 1, 구간 합 빠르게 계산하기

$N$ 개의 정수로 구성된 수열과 Left와 Right로 구성된 $M$ 개의 쿼리(Query)정보가 있다.

이 때 각 쿼리에 대하여 [Left, Right] 구간에 포함된 모든 데이터들의 합을 출력하시오.

단, 해당 문제의 수행 시간 제한은 $O(N + M)$이다.

Explanation

해당 문제는 구간 합 알고리즘을 사용하여 $N$ 개의 수 위치 각각에 대하여 접두사 합을 계산하여 P에 저장하면 된다.

이 때 M개의 쿼리 정보를 확인할 때 구간 합은 $P[Right] - P[Left - 1]$이다.

위 과정을 코드로 구현하면 다음과 같다.

const N = 5;
const arr = [10, 20, 30, 40, 50];

// 접두사 합(Prefix Sum) 배열 계산
let sum_value = 0;
const prefix_sum = [6];

for (let i = 0; i < N; i++) {
  sum_value += arr[i];
  prefix_sum[i + 1] = sum_value;
}


// 구간 합 계산(3번째 수부터 4번째 수까지)
const left = 3;
const right = 4;
console.log(prefix_sum[right] - prefix_sum[left - 1]);

참고 자료

(이코테 2021) 이것 취업을 위한 코딩 테스트다 - 동빈나