말 그대로 구간의 누적의 합을 구하는 알고리즘이다. 배열에 값을 저장하고 하나씩 더해가는 방식은 O(n^2)의 시간 복잡도를 갖는다. 하지만 누적합 알고리즘을 사용한다면 O(n)으로 시간복잡도를 줄일 수 있다. 보통 누적합은 부분 합을 구하기 위해서 사용하는데 만약 a부터 b까지의 합을 구한다고 하면 먼저 누적합을 만들고, b번째 요소에서 a-1번째 요소를 빼주면 구할 수 있다.
import itertools
a = [3,2,1,6,8,4]
result = list(itertools.accumulate(a))
print(result)
🖨️ [3, 5, 6, 12, 20, 24]
import itertools
a = [3,2,1,6,8,4]
start = 3
end = 5
acc = list(itertools.accumulate(a))
result = acc[end] - acc[start-1]
🖨️ 18
누적합을 우선 구한 후 마지막 부분의 누적합 값에서 시작부분 전의 누적합을 빼서 부분 합을 구할 수 있다,