누적합!

크기가 N인 배열 A가 있을 때, 이것의 prefix sum은 N칸 혹은 N+1칸으로 이루어진 배열이다. 이번엔 N+1칸으로 이루어진 배열로 설명해보겠당!
이 경우, S[0] = 0 이겠죠?

S[i + 1] = S[i] + A[i]
로 채워나갈 수 있다.

예시로 알아보자
                 A[i] = {1 2 3 4 5 6 7}
일 때, 누적합 S는?
                 S[i] = {0 1 3 6 10 15 21 28} 이겠죠?
그럼 구간 [3, 5]의 합은?
A[3]+A[4]+A[5] = 15 이렇게 구할수도 있지만 -> O(N)
S[5+1] - S[3] = 21 - 6 = 15
로 O(1)에 구해낼 수 있다.
일반화 하자면, 구간 [s, e]의 합은 S[e + 1]- S[s] 이다!

💙 스터디 예제

◼ ch14

🔘I   11660 구간 합 구하기 5
🔘III 11441 합 구하기
🔘I   19951 태상이의 훈련소 생활
🔘I   16507 어두운 건 무서워
🟡IV 17943 도미노예측
🔘II  16139 인간-컴퓨터 상호작용
🟡III 3673 나눌 수 있는 부분 수열
🔘III 10211 Maximum Subarray
🔘II  17123 배열놀이
🟡IV 10986 나머지 합