구간합(Prefix Sum)

구간합

__💡 구간합이란?__
합배열을 이용해 시간복잡도를 줄이는 목적의 알고리즘__

합배열 S

S[i] = A[0] + a[1] + ... + A[i-1] + A[i]

기존의 배열을 전처리한 배열

기존 일정 범위의 합을 구하는 시간복잡도가 $O(N)$ 에서 $O(1)$ 로 감소

합배열 만드는 법

S[i] = S[i-1] + A[i];

합배열에서 특정 구간 내의 합 구하는 법

[부분합] j~i 사이 구간 구할때

result = S[i] - S[j-1];

 

j 가 아닌 j-1

2~4 까지의 구간합을 구하고 싶으면 

 

 

💡
연관문제

[G3] 10986 나머지 합
[S1] 11660 구간합 5
[S3] 11659 구간합 4