구간 합 알고리즘(Prefix Algorithm)

구간 합 알고리즘이란?

• 배열의 연속된 구간의 합을 효율적으로 계산하는 알고리즘.
• 배열의 원소가 자주 변경되지 않고, 여러 번 구간 합을 계산해야 할 때 사용.
• 미리 배열의 각 원소까지의 누적 합을 계산하여, 이를 이용하여 구간 합을 빠르게 계산하는 방법.
• 시간 복잡도를 줄이는데 많은 도움이 됨.

누적 합이란?

• 기존 배열을 전처리한 배열.
• 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N) 에서 O(1)로 감소.
• 주어진 배열이 [1,2,3,4,5] 라고 할때, 누적 합 배열은[1,3,6,10,15] 가 됨.
• S[i] = A[0]+A[1]+A[2]+...+A[i-1]+A[i]

사용처

• 특정 구간의 합을 빠르게 계산하고 싶은 경우.
• 특정 구간의 최솟값 또는 최댓값을 빠르게 계산하고 싶은 경우.
• 특정 구간의 평균 등을 계산하고 싶은 경우.