Prefix Sum 알고리즘

주어진 배열을 모두 더해서 값을 가지고 활용하는 문제 

예시) BOJ 11659

 

 

i번째 수부터 j번째 수까지 반복해서 수를 구하는 방법 대신

 

S[i] = S[i-1] + A[i]를 활용하면, O(n)

 

S[i] - S[j-1]으로 값을 총 O(N) 시간 만에 구할 수 있다