구간 합

배열의 특정 구간의 합을 구하는 자료구조
배열 내 특정 위치의 값이 변하지 않는 경우를 전체로 사용가능한 자료구조다

---

분류

	값을 변경하지 않는 경우	값을 변경하는 경우
1 차원	Prefix Sum	Binary Index Tree (Fenwick Tree) (segment tree) (sqrt-decomposition)
2 차원	sumed-area table (integral image)	Binary Index Tree (Fenwick Tree) (segment tree) (sqrt-decomposition)

표 출처 : https://www.youtube.com/watch?v=_2DOKWvGets

---

구조

• 배열의 0번째 인덱스는 0으로 한다
• 누적 합의 결과는 1번 인덱스부터 저장을 시작한다

1. 0번부터 N번째 위치까지의 합

• Array[N]

2. M번째부터 N번째 위치까지의 합

• Array[N]-[M-1]

---

코드

let arr = [1, 2, 3, 4, 5]
// 배열 크기를 하나 더 크게 만들어 0번 인덱스에 0을 할당
var prefixSum = [Int](repeating: 0, count: arr.count + 1)

for i in 1...arr.count {
    prefixSum[i] = prefixSum[i-1] + arr[i-1]
}

print(prefixSum)