[알고리즘] 누적합 (prefix sum)

누적합(혹은 prefix sum)은 알고리즘 풀이에서 아주 자주 등장하는 핵심 기법이다.
시간복잡도, 효율적 데이터 처리가 중요한 많은 문제에서 누적합 배열을 이용하면 반복 계산을 대폭 줄일 수 있다.

1. 누적합이란?

누적합이란, 배열 A의 원소들을 앞에서부터 더해가며 새로운 배열 S를 만드는 것이다.
즉, S[i]는 원 배열 A의 0번째부터 i번째까지의 합이 된다.

예를 들면 아래와 같다.
A = [3, 1, 2, 5, 4]
S = [3, 4, 6, 11, 15]

const A = [3, 1, 2, 5, 4]  ;
const S = [A];
for(let i = 1; i < A.length; i++) {
S[i] = S[i-1] + A[i];
}
console.log(S); //

2. 누적합의 진짜 강점

• 누적합 배열을 활용하면 구간합 계산을 O(1)에 끝낼 수 있다.
• 예를 들어, A 배열의 i~j번째 구간 합을 계산할 때 반복문을 쓰면 O(j-i+1)이지만
• 누적합 배열이 있으면 S[j] - S[i-1]을 해서 한 번에 값을 구할 수 있다.

// i=2, j=4의 구간합(2~4번째 합)
const sum = S[4] - S[2]; // 15 - 4 = 11

3. 누적합의 활용 예시

• 구간 합 문제(Continuous Sum, Range Sum)
• 2차원 누적합(부분합), 예: 부분 행렬의 합
• 최장 연속 부분합, 슬라이딩 윈도우와 조합
• 쿼리 여러 번 처리(다수의 구간합 문제)
• 투포인터/이분 탐색 등과 결합 가능

4. 언제 적용이 가능할까?

• 누적합은 “기준점”을 하나 더 두는 것이 일반적이다.
• 보통 S[0]=0으로 두고 구현하면 S[j]-S[i] 형태가 자연스럽다.
• 구간합 쿼리가 많을 때, 미리 누적합 배열을 만들어두면 속도가 극적으로 빨라진다.
• 2차원 배열(행렬)에서도 row, col 단위로 prefix sum을 미리 구해두면 부분행렬의 합도 O(1)에 처리할 수 있다.

5. 누적합과 슬라이딩 윈도우

• 누적합과 슬라이딩 윈도우는 그 방식이 유사해 같은 개념이라고 생각할 수 있지만 다른점이 있다
• 누적합은 미리 전체 배열의 누적합 배열을 만들어두고 임의의 구간 합을 O(1)에 구한다면
• 슬라이딩 윈도우는 윈도우 크기가 고정된 경우, 이전 구간의 합에서 한쪽 값을 빼고 다른 쪽 값을 더하는 방식으로 O(1)에 다음 구간 합을 구한다
• 누적합은 여러 구간 쿼리가 있을 때 유리하고, 슬라이딩 윈도우는 한 번에 한 구간씩 순차적으로 처리할 때 적합하다.