누적합(Prefix Sum)

요소들의 누적된 합. 어떠한 배열을 기반으로 앞에서부터 요소들의 누적된 합을 저장해 새로이 배열을 만들어서(PSum) 이를 활용하는 것을 의미 (↔ Suffix Sum 뒤에서부터 더함)

- PSum[n] 에는 배열의 n번째 인덱스의 값까지 합한 값이 들어감

- 누적합 배열을 만들 때는 0번 index를 비우고 1번부터 값을 받는 게 편하다.

 

활용 방법

구간쿼리 중 배열의 요소가 변하지 않는 정적배열에서 구간의 합을 구하는 데 사용함

n개의 숫자가 있고 합을 구해야할 구간이 m개 주어질 때, 매번 더하는 게 아니라 누적합 배열을 구해놓고 마이너스 연산으로 값을 구함

ex: [3,5] 구간의 합 → PSum[5] - PSum[2]

- 시간복잡도: O(n*n) → O(n)  *반복문으로 매번 구하면 O(n*n) 시간복잡도를 가진다.

- 구간쿼리 중 동적배열 문제는 펜윅트리(Fenwick Tree)를 활용해 구해야한다.

 

예제

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
num_list = list(map(int, input().split()))

# 누적합 구하기
prefix_sum_list = [0] * (n+1)
for index, num in enumerate(num_list):
    prefix_sum_list[index + 1] = prefix_sum_list[index] + num_list[index]

for _ in range(m):
    i, j = map(int, input().split())
    print(prefix_sum_list[j]-prefix_sum_list[i-1])

---

참고

https://www.youtube.com/watch?v=906Kko5nZhE