🤔 의미

누적 합 알고리즘은 말 그대로 누적합을 구하여 리스트 혹은 배열에 저장해놓는 것이다. 예를들어 3번째 인덱스의 값은 0,1 그리고 2번째의 누적합이 들어가는 것이다. 결국 처음부터 하나씩 누적으로 합한다는 것이다. 당연히 0번째 인덱스는 자기자신의 값이 들어갈 것이고(누적합 리스트에서), 1번째 누적합 리스트의 인덱스에는 0번째 값과 1번 째 값을 더한 값이 들어갈 것이다. 아래는 그 예시이다.

---

💻 활용

index	0	1	2	3	4
arr(원래 배열)	5	1	2	3	4
pre_sum(누적합 배열)	5	6	8	11	15

현재 누적합 배열값+ 다음 배열값 = 다음 누적합 배열