배열 문제 유형 - 누적합

https://youtu.be/906Kko5nZhE
https://m.blog.naver.com/PostView.naver?blogId=jhc9639&logNo=222283814653&referrerCode=0&searchKeyword=%EB%88%84%EC%A0%81%ED%95%A9

'큰돌의 터전' 블로그, 유튜브를 보고 자려다 벌떡 일어나서 정리

1. 누적합
   배열에서 앞에서부터 연속된 구역의 숫자들을 합한 값들을 활용하는 유형

그냥 반복으로 하면 시간복잡도가 커지지만 누적합에 대한 별도의 arr를 만들어 활용하면 시간복잡도를 크게 줄일 수 있음

실사용 예시

위의 블로그와 유튜브에서 설명해주신대로 중간 부분을 구하려면 pSum arr를 새로 만들어서 arr의 값을 빼주는 것으로 O(1)의 시간복잡도로 계산할 수 있다.

3. 코테
   핵심키워드 : '구간', '쿼리'
   참고사항 : 세그먼트, 펜윅트리 또는 누적합 활용.
   특히 그 구간 안에 있는 요소들이 변하지 않는 정적 요소라면 누적합이 적절.