1차원 배열 누적합을 이용하면 구간합을 상수 시간에 구할수 있다!?
index = i
0
1
2
3
4
5
arr[i]
1
2
3
4
5
6
prefixSum[i]
1
3
6
10
15
21
prefixSum만드는 시간 복잡도 O(n)
길이가 n인 배열의 a~b구간의 합 구하기
0≤a<b≤n
⇒ prefixSum[b]-prefixSum[a]