누적합 알고리즘은 배열의 원소들을 앞에서부터 순서대로 더한 누적합을 다른 배열에 저장해 놓는 것입니다. 이렇게 미리 누적합을 구해 놓으면, 이후에 배열의 어떤 구간의 합을 구할 때에는 누적합 배열에서 구간의 끝 인덱스에 해당하는 누적합과 구간의 시작 인덱스 바로 전의 누적합을 빼면 구간의 합을 구할 수 있습니다. 이 방법을 이용하면 구간의 합을 구하는 데에 반복적인 계산을 줄일 수 있습니다.
하지만, 이 알고리즘을 사용하는 경우에는 누적합 배열을 구하는 데에 O(n)의 시간 복잡도가 들기 때문에, 배열의 크기가 작거나 구간의 합을 반복적으로 구하는 경우에만 유용합니다. 배열의 크기가 커지면 누적합 배열을 구하는 데에 시간이 오래 걸리게 되므로, 이 경우에는 다른 알고리즘을 사용하는 것이 더 효율적일 수 있습니다.
아래에 예시 작성하였습니다.
const ARRAY = [1, 3, 5, 7, 9, 10, 13];
const PREFIX_SUM_ARRAY = new Array(ARRAY.length).fill(0);
for (let i = 0; i < ARRAY.length; i++) PREFIX_SUM_ARRAY[i + 1] = PREFIX_SUM_ARRAY[i] + ARRAY[i];
const aa = ARRAY.slice(0, 4).reduce((a, b) => a + b, 0);
const bb = PREFIX_SUM_ARRAY[4];
console.log(aa === bb); // true
const aaa = ARRAY.slice(2, 4).reduce((a, b) => a + b, 0);
const bbb = PREFIX_SUM_ARRAY[4] - PREFIX_SUM_ARRAY[2];
console.log(aaa === bbb); // true