누적 합 (Prefix Sum)

계산 양을 줄여서 시간적으로 많은 이득을 볼 수 있는 알고리즘이다.

1. 기본 원리

1) 1차원 배열

1차원 배열에서 i번째부터 j번째 인덱스까지 k를 더한 것을 기록하려면, 새로운 배열의 i번째 인덱스에 k를 더하고 j+1번째 인덱스에 k를 빼면 된다.

• 새로운 배열의 크기는 기존 배열 크기보다 하나 이상 크게 만든다.

 

예를 들어 크기가 5인 배열에서 0번째부터 2번째 인덱스까지 N을 빼고 싶다면 다음과 같이 누적 합 배열을 만든다.

{ -N, 0, 0, N, 0, 0 }

 

위 새로운 배열을 0번째부터 마지막 인덱스까지 누적 합을 계산하게 되면 다음과 같다.

누적 합 예1

 

추가로 1번째부터 2번째 인덱스까지 M을 더하고 싶다면 누적 합 배열에 값을 추가한다.

{ -N, -M, 0, N, M, 0 }

 

다시 0번째부터 마지막 인덱스까지 누적 합을 계산하게 되면 다음과 같다.

누적 합 예2

 

누적 합 배열에 계속 값을 저장한 후 마지막에 한 번만 누적 합을 계산하면, 최종적인 변화량을 기록하는 배열을 가질 수 있다.

 

2) 2차원 배열

2차원 배열 누적 합

 

[C++] 누적 합(Prefix sum) — 💡번뜩💡 (tistory.com)