누적합

누적합 (Prefix Sum) 알고리즘

---

누적합 알고리즘은 배열의 구간합을 구하는데 사용하는 알고리즘입니다.

누적합 알고리즘을 사용하면 구간합을 계산할 때 O(1)의 시간 복잡도로 계산을 할 수 있습니다.

누적합 알고리즘을 사용할 때는 배열의 처음부터 끝까지의 합을 저장한 배열을 만듭니다.

일반적으로 누적합에 사용할 배열은 기존 배열의 크기에 1을 추가하여 생성합니다.

---

누적합 알고리즘 과정

---

누적합 알고리즘 과정을 보시기 전에 주의할 사항은 다음과 같습니다.

1. index의 값은 0부터 시작합니다.

2. 배열 array의 i번째 값은 array[i - 1]입니다.

3. 누적합 배열 preSum은 기본 배열 arr보다 크기가 1 큰 배열입니다.

---

만약 위와 같은 기본 배열 arr이 있다면 누적합 배열은 다음과 같은 과정을 통해 만들어집니다.

1. 기본 배열 사이즈 + 1의 누적합 배열 preSum을 생성합니다.

2. arr 배열을 순서대로 실행하면서, preSum[i + 1]를 preSum[i] + arr[i]로 변경합니다.

3. arr의 a번째 요소부터 b번째 요소의 구간합은 preSum[b] - preSum[a - 1]의 값이 됩니다.

예를 들어, arr의 4번째 요소부터 6번째 요소까지의 합은 preSum[6] - presum[3]인 15가 됩니다.

---

누적합 알고리즘 코드 예시

---

누적합 알고리즘을 코틀린 코드로 구현한 예시입니다.

fun main() {
    // 기본 배열
    val arr = intArrayOf(1, 2, 3, 4, 5, 6)

    // 1번 과정 : "기본 배열 + 1" 크기의 누적합 배열 생성
    // preSum = [0, 0, 0, 0, 0, 0, 0]
    val preSum = IntArray(arr.size + 1)

    // 2번 과정 : 누적합 구하기
    // preSum = [0, 1, 3, 6, 10, 15, 21]
    for (i in arr.indices) {
        preSum[i + 1] = preSum[i] + arr[i]
    }

    // 3번 과정 : 기본 배열의 4번째 요소부터 6번째 요소(4, 5, 6)의 구간합
    // result = 15
    val result = preSum[6] - preSum[3]
}