[알고리즘] 구간 합(prefix sum)

구간 합 알고리즘은 1차원배열에서 i ~ k번째 사이의 값들의 합을 구하는데 사용합니다. 단순히 for문을 사용하여 i~k사이의 값을 더해가면서 할 수도 있지만 이 경우 시간복잡도는 O(N)입니다. 하지만 구간 합 알고리즘의 경우 O(1)성능을 가집니다.

 

그리고 sum[]이라는 배열을 사용하는데, 이 배열은 현재 인덱스까지의 총 합을 저장하게 됩니다. j번째 바로 앞까지의 총합에 arr[j]번째 값을 더하면 j번째까지의 총합을 의미하기 때문에 이 값은 sum[j]에 저장하며 이는 sum[j] = sum[j-1] + arr[j]가 됩니다.

 

이후 5,8의 구간합을 구하기 위해서는 sum[8] - sum[5-1]로 한번에 구할 수 있습니다.

#include <iostream>

using namespace std;

int main()
{
    int arr[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    int sum[10] = {
        0,
    };

    sum[0] = arr[0];
    for (int i = 1; i < 10; i++)
    {
        sum[i] = sum[i - 1] + arr[i];
    }

    for (int n : sum)
    {
        cout << n << " "; // 0 1 3 6 10 15 21 28 36 45
    }
    cout << "\n";

    int i = 5;
    int j = 8;
    cout << sum[j] - sum[i - 1] << endl; // 26

    return 0;
}