[부분 합] Partial sum

1. 부분 합

 

부분 합이란 배열의 각 위치에 대해 배열의 시작부터 현재 위치까지의 합을 구해둔 배열이다.

 

psum[i] = Σscores[j] (0<=j<=i)

 

이렇게 부분 합을 미리 계산하면 score의 특정 구간의 합을 O(1)만에 구할 수 있다.

 

a~b 구간의 합은 다음과 같다. 

psum[b] - psum[a-1] 

 

2. 부분합 계산하기

 

반복문을 통해 간단하게 수행된다.

 

psum[i] = psum[i-1] + array[i]

 

최대 O(N)의 시간이 걸린다.

 

c++에서는 STL인 partial_sum(array.begin(), array.end(), result) 을 사용할 수 있다.

 

3. 부분 합으로 분산(variance) 계산하기

 

부분 합을 잘 이용하면 합 혹은 평균 외에도 다른 값들을 쉽게 계산할 수 있다.

 

배열 A[]의 구간 A[a, ...b]의 분산은 다음과 같다.

 

v = (1/(b-a+1) )* Σ(A[i] - mab)^2    (i=a -> i=b)

 

mab는 a에서 b까지의 평균이다,

 

Σ(A[i] - mab)^2 =  Σ(A[i]^2 -2A[i]mab + mab^2)    

                      =  ΣA[i]^2 -2mabΣA[i] + (b-a+1)mab^2

 

따라서 A[i]^2 과 A[i] 의 부분 합을 미리 계산해두면 O(1)만에 분산을 계산할 수 있다.

 

4. 2차원에서의 부분 합

 

2차원 배열 A[][]이 주어질 때, A[y1, x1]에서 A[y2, x2] 까지의 직사각형 구간의 합을 계산하는 식은 다음과 같다.

 

psum[y,x] = ΣΣA[i,j]  (i=0 ~y, j = 0 ~x)

 

sum(y1,x1,y2,x2) = psum[y2,x2]-psum[y2,x1-1]-psum[y1-1,x1]+psum[y1-1,x1-1]

 

 

 

5. 구간 합의 활용

 

구간 트리는 구간 합의 확장개념이다.

구간 합 외에도 구간 곱, 구간의 최소값/최대값, 최대 출현 빈도 등 아주 많은 문제들을 

해결할 수 있다.

 

 

 

 

- 알고리즘 문제해결전략 597p