Prefix Sums

Prefix Sums

array의 어떠한 slice라도 sum을 빠르게 계산할 수 있도록 해주는 방법이다. 예를 들어 어떤 배열의 인덱스 i부터 j까지의 합을 구하려고 할 때 for문을 써서 일일이 접근해서 더하면 O(N)이지만, 이 방법을 사용하면 O(1)이다.

def prefix_sums(A):
  n = len(A)
  P = [0] * (n + 1)
  for i in range(1, n + 1):
    P[i] = P[i - 1] + A[i - 1]
  return P

점화식: P[i] = P[i - 1] + A[i - 1]

A라는 배열이 있을 때, A 배열의 sum의 누적값을 계산해서 P에 넣는 것이다. P[i] = P[i - 1] + A[i - 1]으로 계산되고, P[i]는 A 배열의 i번째 원소(인덱스로는 i-1)까지의 합이라고 할 수 있다.

앞에서부터 누적값을 계산하므로 Prefix sums라는 이름이 붙은 것이고, 반대로 뒤에서부터 누적값을 계산하는 경우는 Suffix sums라고 한다. Prefix sums든, Suffix sums든 둘 다 P 배열을 완성시키고나면 array의 slice의 sum을 O(1)로 계산할 수 있다는 장점이 있다.

예를 들어 A 배열의 5번째 값부터 10번째 값까지의 sum을 구하고 싶다면 P[10] - P[4] 를 계산하면 알 수 있다. P를 계산하는 데에는 O(n)의 시간 복잡도가 들고, 이 후 array sum을 계산할 때에는 O(1) 이므로 m 번을 계산하면 총 시간복잡도는 O(n + m)이다. 반면 이 방법을 사용하지 않고 일일이 계산할 경우, O(n * m) 만큼의 시간복잡도가 든다.

Ref

코딜리티