Prefix sum
누적 합
앞에서부터 더해 두고 구간 합을 꺼내요
1~3번 원소의 합을 구해요
구할 구간1~3번
지금까지의 합0
현재 위치비교 대상확인한 값
예제 코드
C++
<vector>std::vector<int> prefix_sums(const std::vector<int>& a) { std::vector<int> prefix(a.size() + 1, 0); for (int i = 0; i < static_cast<int>(a.size()); ++i) prefix[i + 1] = prefix[i] + a[i]; return prefix;}int range_sum(const std::vector<int>& prefix, int left, int right) { return prefix[right + 1] - prefix[left];}Python
def prefix_sums(a): prefix = [0] for value in a: prefix.append(prefix[-1] + value) return prefixdef range_sum(prefix, left, right): return prefix[right + 1] - prefix[left]시작하기
합을 저장할 칸을 만들어요
prefix[0]은 0이에요. 앞의 원소를 0개 더했기 때문이에요.
사용 조건
같은 배열의 여러 구간 합을 반복해서 구할 때 사용해요. 구간마다 원소를 처음부터 더하지 않아도 돼요.
먼저 알아두면 좋아요
배열과 반복문, 덧셈·뺄셈을 알고 시작해요. prefix[i]는 앞의 i개 원소를 더한 값이에요.
동작 원리
prefix[0] = 0으로 시작해요. prefix[i + 1] = prefix[i] + a[i]로 이전 합에 지금 값을 더해 저장해요.
left~right번의 합은 prefix[right + 1] − prefix[left]예요. right번까지 모두 더한 값에서 left번 앞의 부분을 빼면 필요한 구간만 남아요.
- 시간
- 준비 O(n), 구간 질문 하나 O(1)
- 추가 공간
- O(n) · 앞부분의 합을 저장해요
주의할 점
- 누적 합 배열은 원래 배열보다 한 칸 길어요. 0개 원소의 합도 저장하기 때문이에요.
- 원래 값이 바뀌면 누적 합도 영향을 받아요. 값 변경이 잦은 문제는 다른 방법을 검토해요.