구간합 구하기

구간합을 O(n) 만에 구하는 알고리즘에 대해서 알아볼게요

 

위와 같은 수열이 있다고 하고 이들의 구간합을 구해볼게요

구간합을 구한다는 말은 랜덤으로 어떤 구간을 정하면 그 구간의 합을 딱딱 구하는걸 말해요

[0 - 3], [2 - 4] 를 예시로 구간합을 구해봤어요. 어떤 구간이 주어질때마다 수열을 loop 돌며 구하는 방법이에요.

이 방법으로 모든 구간의 구간합을 구하기 위해서는 O(n^2)이라는 시간이 필요해요

 

하지만 오늘 알아볼 방법은 O(n)의 방법이에요

하늘색 수열이 보이시나요? 이건 0번째 원소부터 자기 자신까지의 누적합을 구해둔 배열이에요

0번째 누적합은 2,

1번째 누적합은 2 + 5 = 7

2번째 누적합은 2 + 5 + 8 = 15

 

이렇게 누적합을 구해두면 특정구간의 합을 O(1)만에 구할 수 있어요

[2-4] 를 보시면 누적합의 4번째 요소는 0번째 요소부터 4번째 요소까지의 누적합이죠

하지만 우리는 2번째 요소부터 4번째 요소의 누적합을 구하고싶으니 0, 1번째 요소의 값은 빼주어야해요

0, 1번째 요소의 누적합은 1번째 누적합이 갖고 있으니 26 - 7 = 19가 되는거에요



간단하지만 유용한 알고리즘이니 머릿속에 넣어두는게 좋아요