누적합

누적합 누적합은 리스트의 각 원소에 대해 그 이전 원소들의 합을 미리 구해 구간의 합을 구하는 방법이다. 이를테면 매출을 매일 기록해둔 카페 주인이 주말 매출과 주중 매출을 알고 싶어한다. 월요일을 일주일의 시작이라고 가정하고 예시를 살펴보자. 카페 수익 월 화 수 목 금 토 일 1 2 3 4 5 6 7 화요일부터 금요일까지의 수익은 2,3,4,5의 합인 14이다. 또 수요일부터 일요일까지의 매출의 합은 3,4,5,6,7의 합인 25가 된다. 데이터가 적으면 빠르게 구할 수 있지만, 데이터가 많아질수록 합을 구하는 시간이 오래 걸린다. 이때 누적합을 이용하면 빠르게 구할 수 있다. 화요일부터 금요일까지의 매출은 2,3,4,5를 다 더해주는 것이 아니라, 금요일까지의 누적합에서 월요일까지의 누적합을 빼주면..