Prefix sum ( 누적합 )
목적 : 범위가 아무리 넓어도 범위 안의 값들의 합(구간합)을 빠르고 간편하게 구하기
사용 이유 : 누적합을 만들고 구간합을 구하는 시간복잡도는 O(N)[누적합 배열을 만들때 걸리는 시간]*O(1) = O(N)이다. 일반적인 반복문을 사용해서 구간합을 구하려 하면 시간 복잡도가 O(n²)가 되버린다. 숫자가 커지면 간단한 코드를 돌리는데 시간이 한 세월이기 때문에 구간합을 구할때는 누적합을 사용하는게 좋아보인다.
누적합을 이용해 구간합을 구하는 예시 (그림으로 더 자세히 설명)
= 2~5합 = psum[5]-psum[1]
누적합 배열을 만들기 편하려면 , 기존 배열의 0번째 인덱스는 비워두는 것이 좋다.왜냐하면 구현하면서 앞의 인덱스를 사용하기 때문이다. 아래 코드와 그림을 보면 더 쉽게 이해할 수 있다.
int[] a = 주어진 배열(0번째 인덱스가 비워진 상태)
int[] psum = 누적합 배열 = new int[a의 길이];
for(int i=1 ; i< a의 길이 ; i++){
// 이전까지의 합 + 현재 번째의 값
// 여기의 i-1 때문에 psum은 1 부터 받아야 만들기 편하다.
psum[i] = psum[i-1] + a[i];
}
참고자료
( 부족한 부분이나 수정해야 할 부분을 알려주시면 매우 압도적으로 감사하겠습니다! )
