[C++]누적합(prefix sum)

누적 합이란, 처음 요소부터 n번째 요소의 합을 각 n번 index에 저장한 배열의 형태를 말한다.

a = { 1, 2, 3, 4, 5} 일 때, prefix_a = { 1, 3, 6, 10 15 }와 같은 형태이다.

누적 합은 시간복잡도를 줄이기 위해 주로 사용한다. 예를 들어, 어떤 배열이 주어지고, 시작 index와 끝 index를 n번 입력받아, 각각의 구간에 대한 합을 n번에 걸쳐 줄력하는 문제가 있다고 가정하자. 배열의 크기가 작다면 문제가 없지만, 배열이 커지게 되면 시간이 오래 걸리게 된다.

 

위에서 설명한 예시를 코드로 작성해 보았다. 해당 코드의 시간복잡도는 O(n^2)가 되고, 주어진 값에 의하면 최대 10억번의 for문 반복이 필요하다. 이럴 때를 위해 필요한 것이 누적합이다.

 

누적합을 사용하면 구간합을 구하는 과정이 for문이 아니라 뺄셈 한번으로 해결되기 때문에 시간복잡도가 O(n)으로 극적으로 단축된다.