• 알고리즘
  • 누적 합

누적 합 (Prefix Sum)

문제

크기가 $N$인 정수 배열 $A$가 있고, 여기서 다음과 같은 연산을 최대 $M$번 수행해야 하는 문제가 있습니다.

  • 구간 $l$, $r$ ($l ≤ r$)이 주어졌을 때, $A[l] + A[l+1] + \dots + A[r-1] + A[r]$을 구해서 출력하기

$A[l] + A[l+1] + \dots + A[r-1] + A[r]$을 구하기 위해 소스 1과 같이 모두 더하는 방법이 있습니다.

소스 1

소스 1의 시간 복잡도는 $O(N)$입니다. 문제에서는 연산을 최대 $M$번 수행해야 한다고 했으니, 총 시간 복잡도는 $O(NM)$이 됩니다.

누적 합

누적 합 아이디어는 배열 $A$에 들어있는 값이 바뀌지 않는다는 점을 이용합니다. 배열이 변하지 않으니 구간의 합도 변하지 않습니다. 따라서, 앞에서부터 차례대로 누적된 합을 구해놓고 이를 이용해서 구간의 합을 구할 수 있습니다.

$S[i] = A[1] + \dots + A[i]$, $S[0] = 0$ 으로 정의합시다.

$l$번째 수부터 $r$번째 수까지 합은 $S[r] - S[l-1]$과 같습니다.

그 이유를 알아보면

$S[r] = A[1] + ... + A[r]$

$S[l-1] = A[1] + ... + A[l-1]$

입니다. 따라서, $S[r] - S[l-1] = A[l] + \dots + A[r]$이 됩니다.

구간의 합을 구하기 위해서 뺄셈 연산 한 번만 하면되니 시간 복잡도는 $O(1)$입니다. 연산을 총 $M$번 수행해야 하니 총 시간 복잡도는 $O(M)$이 됩니다.

예시

$i$$0$$1$$2$$3$$4$$5$$6$$7$$8$
$A[i]$$7$$2$$4$$5$$9$$1$$9$$2$
$S[i]$$0$$7$$9$$13$$18$$27$$28$$37$$39$
$S[r]$$0$$7$$9$$13$$18$$27$$28$$37$$39$
$S[l-1]$$0$$7$$9$$13$$18$$27$$28$$37$$39$
$S[r]-S[l-1]$$0$$7$$9$$13$$18$$27$$28$$37$$39$

위의 예시는 $l = $, $r = $인 경우입니다.

구현

누적 합을 저장할 배열 $S$는 $O(N)$에 구할 수 있습니다.

$S[i] = A[1] + \dots + A[i-1] + A[i]$이고, 여기서 $A[1] + \dots + A[i-1]$는 $S[i-1]$로 표현할 수 있습니다. 이 점을 이용해 소스 2와 같이 구현할 수 있습니다.

구간 $l$, $r$의 합은 $S[r] - S[l-1]$으로 구할 수 있습니다.

소스 2

배열의 시작 인덱스

위의 설명에서 배열 $A$의 시작 인덱스는 $1$로 사용했습니다. 그 이유는 $S[l-1]$ 때문입니다. 시작 인덱스가 $1$이면 $l$의 최솟값은 $1$이고, 여기서 $l-1$은 $0$입니다. 만약, 시작 인덱스가 $0$이었다면, $l$의 최솟값은 $0$이고, 이때 $l-1$은 $-1$입니다.

배열의 인덱스로 음수를 사용할 수 없기 때문에, $1$부터 시작하는 것으로 정했습니다. 물론 $0$부터 시작해도 누적 합을 사용할 수 있습니다. 하지만, 뒤에 배열 한 칸이 더 필요합니다.

11659 - 구간 합 구하기 4

누적 합을 사용하기 위해 이 글의 가장 처음에 설명한 문제와 같은 문제입니다. 소스 3으로 해결할 수 있습니다.

소스 3