prefix-sum.md

구간 합

배열 arr 에 원소element 1 부터 10 까지 담겨 있다. 원소는 index 1 부터 담는다.

index :  1  2  3  4  5  6  7  8  9  10
value :  1  2  3  4  5  6  7  8  9  10

index 4 부터 index 7 까지의 value 를 더하면 arr[4] + arr[5] + arr[6] + arr[7] = 4 + 5 + 6 + 7 = 22 이다.


구간은 시작 index a 와 끝 index b 의 쌍 (a, b) 로 나타내고, arr[a] 부터 arr[b] 까지 더한 값을 구간 합이라 한다. 하나의 배열에서 여러 구간의 합을 구할 수 있다. 아래는 arr 의 세 구간과 각 구간 합이다.

(4, 7)   →  4 + 5 + 6 + 7       = 22
(1, 10)  →  1 + 2 + ... + 10    = 55
(3, 3)   →  3                   = 3

arr[0] 은 쓰지 않으며, 어떤 값이 들어 있어도 결과에 영향을 주지 않는다. 원소를 index 1 부터 담는 이유는 아래 누적 합에서 설명한다.


반복문으로 구하기

구간마다 arr[a] 부터 arr[b] 까지 차례로 더한다.

#include <iostream>
#include <utility>
#include <vector>

using namespace std;

int main()
{
    vector<int> arr = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    vector<pair<int, int>> ranges = {{4, 7}, {1, 10}, {3, 3}};

    for (auto [a, b] : ranges)
    {
        int sum = 0;
        for (int j = a; j <= b; j++)
        {
            sum += arr[j];
        }
        cout << sum << '\n';
    }
    return 0;
}
22
55
3

구간 (4, 7) 은 덧셈을 4 번, (1, 10) 은 10 번 한다. 원소가 n 개이면 구간 하나에 최대 n 번 더하고, 구간 합을 m 번 구하면 최대 n × m 번 더한다. 시간 복잡도는 O(nm)O(nm) 이다. 원소가 100,000 개이고 구간 합을 100,000 번 구하면 덧셈을 최대 10,000,000,000 번 한다. 구간이 길고 구간 합을 구하는 횟수가 많을수록 이 방식은 느려진다.


같은 원소를 구간마다 다시 더하는 것이 원인이다. 위 예시에서 (4, 7) 과 (1, 10) 은 arr[4] 부터 arr[7] 까지를 두 번 더한다.


누적 합

누적 합 배열 psum 의 index i 에는 arr[1] 부터 arr[i] 까지의 합을 담는다.

psum[i]=arr[1]+arr[2]+⋯+arr[i]psum[i] = arr[1] + arr[2] + \cdots + arr[i]

arr 를 index 1 부터 담았기 때문에 psum[i] 는 정확히 arr[i] 까지의 합이 되어, 두 배열의 index 가 일치한다.


psum[i - 1] 에는 이미 arr[1] 부터 arr[i - 1] 까지의 합이 담겨 있으므로, 여기에 arr[i] 하나만 더하면 psum[i] 가 된다.

psum[i]=psum[i−1]+arr[i]psum[i] = psum[i - 1] + arr[i]
image

위 그림은 arr 에 1 부터 10 까지 담았을 때의 psum 이다. 위의 작은 숫자가 index, 칸 안의 숫자가 value 이다. psum[4] 의 10 은 arr[1] 부터 arr[4] 까지인 1 + 2 + 3 + 4 이다. psum[0] 은 아무것도 더하지 않은 합이라 0 이다.


psum 은 index 1 부터 차례로 채운다. index 하나마다 덧셈을 한 번 하므로 O(n)O(n) 이다.

for (int i = 1; i <= n; i++)
{
    psum[i] = psum[i - 1] + arr[i];
}

누적 합으로 구간 합 구하기

psum[b] 는 arr[1] 부터 arr[b] 까지의 합이다. 이 합을 a 앞에서 둘로 나누면, 앞쪽은 arr[1] 부터 arr[a - 1] 까지인 psum[a - 1] 이고 뒤쪽은 구하려는 구간 합이다.

psum[b]=psum[a−1]+(arr[a]+⋯+arr[b])psum[b] = psum[a - 1] + (arr[a] + \cdots + arr[b])

따라서 구간 합은 psum[b] 에서 psum[a - 1] 을 뺀 값이다.

arr[a]+⋯+arr[b]=psum[b]−psum[a−1]arr[a] + \cdots + arr[b] = psum[b] - psum[a - 1]
image

위 그림은 a = 4, b = 7 일 때이다. 첫째 줄과 둘째 줄의 파란 칸은 각 psum 에 더한 원소이고, 셋째 줄의 파란 칸은 psum[7] - psum[3] 으로 남은 원소이다. psum[7] 은 arr[1] 부터 arr[7] 까지 더한 28, psum[3] 은 arr[1] 부터 arr[3] 까지 더한 6 이다. 28 에서 6 을 빼면 arr[1] 부터 arr[3] 까지가 지워지고 arr[4] 부터 arr[7] 까지의 합 22 만 남는다.


a = 1 이면 psum[0] 을 뺀다. 배열을 index 1 부터 채우고 psum[0] 을 0 으로 두었기 때문에, 이때도 같은 식으로 psum[b] 가 그대로 나온다. index 0 부터 채웠다면 psum[-1] 을 읽게 되어 a = 0 인 경우를 따로 처리해야 한다.


구간 하나에 뺄셈을 한 번 하므로 O(1)O(1) 이다. psum 을 채우는 O(n)O(n) 과 합치면 전체 시간 복잡도는 O(n+m)O(n + m) 이다.


전체 코드

psum 은 vector<int> psum(n + 1, 0) 으로 만들어 psum[0] 을 0 으로 둔다. vector 대신 함수 안에서 int psum[11]; 처럼 일반 배열로 선언하면 값이 정해지지 않아 psum[0] 에 쓰레기 값이 들어갈 수 있다.

#include <iostream>
#include <utility>
#include <vector>

using namespace std;

int main()
{
    vector<int> arr = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    vector<pair<int, int>> ranges = {{4, 7}, {1, 10}, {3, 3}};

    int n = arr.size() - 1;
    vector<int> psum(n + 1, 0);
    for (int i = 1; i <= n; i++)
    {
        psum[i] = psum[i - 1] + arr[i];
    }

    for (auto [a, b] : ranges)
    {
        cout << psum[b] - psum[a - 1] << '\n';
    }
    return 0;
}
22
55
3