1. 누적합 (prefix sum)

📌 누적합?

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램

✅ 수 N개 (배열)이 바뀌지 않는 다는 점을 이용한다.

✅ 배열이 변하지 않으니 구간의 합도 변하지 않는다.

🛠️ 앞에서부터 차례대로 누적된 합을 구해놓고 이를 이용해서 구간의 합을 구한다.

i번째 수부터 j번째 수까지 합은 sum[j] - sum[i-1]