누적합(Prefix Sum) / 구간합 알고리즘 선택

Solf·2025년 2월 5일

알고리즘 모음

목록 보기

9/11

누적합은 특정 구간내의 수열의 원소들의 집계를 구해야하는 문제에서 유용하게 사용될 수 있다.

만약 쿼리형태로 특정 구간에 수열 원소들의 합을 구하는 명령이 들어온다. 이걸 각각 구한다면 O(n)이라는 상당히 비싼 비용이 들어가게 된다.

누적합은 이런 합을 미리 계산해둠으로서 O(1)시간만에 구간내의 합을 계산할 수 있도록 하는 일종의 캐쉬라고 볼 수 있다.

수열이 고정된 상황

업데이트가 일어나지 않는다면 O(1)만에 특정 구간 내의 합을 구할 수 있다.

1차원

가장 기본적인 형태의 1차원에서의 누적합이다.

sum of i to j = prefix[j] - prefix[i] 이때 i > 0이며 별도로 prefix[-1] 대신 0을 넣어주면 된다.

시간복잡도 :
누적합 초기화 : O(n)
누적합 조회 : O(1)

2차원

2차원으로 확장된 영역에서의 누적합이다. 누적합의 경우 2중 for문을 활용하여 아래와 같은 식으로 구한다.
prefix[i][j] = prefix[i][j - 1] + prefix[i- 1][j] 이때 prefix[i][j] = (0, 0)부터 (i, j)영역 내의 모든 원소의 합을 의미하게 된다. 이를 잘 잘라서 원하는 직사각형 영역내의 원소의 합을 구할 수 있다.

sum of (i1, j1) to (i2, j2) = prefix[i2][j2] - (prefix[i1 - 1][j2] + prefix[i2][j1 - 1] - prefix[i1 - 1][j1 - 1])

외우기보다는 직관적인 추론으로 쉽게 유도 가능하다.

시간복잡도:
누적합 초기화 : O(n^2)
누적합 조회 : O(1)

수열이 변경되는 상황

업데이트(값 변경 or 삽입)가 일어나는 수열에서는 위 방법은 동작하지 않는다. 가장 큰 문제는 업데이트도 쿼리 문제로 주어질 가능성이 높은데 누적합을 새로 구해야하기에 O(n)이 걸린다. 이런 경우 차선책들로 누적합을 구해볼 수 있다.

제곱근 분할법

그룹단위로 차원을 늘려 분할하고 그룹별로 구간합을 관리하는 방법이다.

sum of 3 to 8 = 두번째 그룹의 합 + 나머지 원소들의 합

만약 삽입연산이 있다면 linked list를 사용하는 것이 유리하다.

시간복잡도
G: 그룹의 개수, E: 그룹의 원소개수
제곱근 분할은 G = E = root(n)으로 나온다.
누적합 구성 : O(G * E) = O(n)
값 변경 : O(1)
삽입 연산 : 링크드 리스트 O(G + E) = O(root(n)), 순차 리스트 O(G * E) = O(n)
누적합 조회 : O(G + E) = O(root(n))