구간 합

구간 합 (Prefix Sum)

구간 합이란 나열된 숫자들에서 특정 구간의 숫자들의 합을 말한다.

ex) 배열 A = {1, 2, 3, 4, 5} 일 때, 2 to 4까지의 구간 합은 2 + 3 + 4 가 된다.

위 예시만 보면 그럼 특정 구간에서의 값들부터 차레대로 더해주면 되는거 아니야? 라고 생각할 수 있다. 하지만 단순히 특정 구간의 수를 매번 일일히 더하여서 값을 구하는 것은 TLE(Time Limit Error)를 보게 될 수도 있다.

그럼 구간 합은 어떻게 구하는 걸까?

배열 A의 값들을 누적해서 합하는 배열 S를 만든다.

s[0] = a[0] = 1
s[1] = s[0] + a[1] = 1 + 2 = 3
s[2] = s[1] + a[2] = 3 + 3 = 6
s[3] = s[2] + a[3] = 6 + 4 = 10
s[4] = s[3] + a[4] = 10 + 5 = 15

2부터 4 사이의 구간 합을 구하고 싶다면 s[3] - s[0]을 구하면 시간복잡도를 줄여 구해낼 수 있다.

합 배열을 미리 구해두면 구간 합은 한번의 게산으로 구할 수 있게 된다.

s[3] = a[0] + a[1] + a[2] + a[3]
s[0] = a[0]

s[3] - s[0] = a[1] + a[2] + a[3]

합 배열과 구간 합 공식을 활용하면 시간 복잡도를 줄이는 데 도움이 된다.