[알고리즘] Prefix Sum 구간 합/누적 합 알고리즘

prefix sum이란 구간 합을 의미한다.

예를 들어,

int arr[5] = {10,20,30,40,50};

prefix sum은 prefix[i] = prefix[i-1] + arr[i]일 것이다.

int prefix[5];
prefix[0] = arr[0];

for(int i=1; i<5; i++){
	prefix[i] = prefix[i-1] + arr[i];
}

 

언제 쓰는가?

당연하지만 특정 인덱스들의 구간 합을 구할 때 사용한다... ㅎㅎ.. 예를 들어 인풋으로 들어오는 구간이 정해지지 않는데 구간합을 구해야 한다? 브루트포스를 사용하면 테스트케이스가 많아질 수록 시간초과 발생확률이 커진다.

이때 모든 구간합을 구해 놓는다면 prefix[구간 끝] - prefix[구간 시작]으로 쉽게 구할 수 있다.

 

관련 문제:

[leetcode 560] subarray sum equals k

eazymean.tistory.com/44

[leetcode 1248] Count Number of Nice Subarrays

 

참고:

codechacha.com/ko/java-prefix-sum/