누적합 알고리즘을 간단히 정리해보자

누적합 알고리즘은?

배열, 리스트 일정 구간까지의 합을 빠르게 계산하도록 미리 계산된 합의 결과를 저장해두는 방식.

[여러 번 구간 합을 계산해야할 때 사용]

 

사용할 수 있는 조건

- 배열이 반드시 정적 배열이어야 함. (변하지 않는 배열)

 

const A = [3, 1, 4, 1, 5];
const prefix = [A[0]];

for (let i = 1; i < A.length; i++) {
  prefix[i] = prefix[i - 1] + A[i];
}

const sum = (i, j) => i === 0 ? prefix[j] : prefix[j] - prefix[i - 1];

console.log(sum(1, 3)); // 1 + 4 + 1 = 6

 

1차원 배열이 주어졌을 때는 기준 점의 왼쪽을 보면 되기 때문에 prefix[i] = prefix[i-1]+A[i] 와 같은 식을 사용하여 더해나갑니다.

 

 

만약 누적합 없이 계산해야한다면 시간 복잡도는

 

O(N)

 

질문을 몇번 하는가에 따라서

 

O(N*Q)

 

만약 누적 합이라면?

 

O(N*Q) → O(N)

으로 줄일 수 있다.