Prefix sum

$N$개의 숫자가 늘어서 있다.
L번째 숫자부터 R번째 숫자까지의 합을 구하라는 질문이 여러 개 들어올 때, 각각을 모두 빠르게 구할 수 있을까?

2018/07/27 - [알고리즘 문제풀기/# 자료구조] - 구간의 합 구하기

prefix sum 기법을 사용하면 이 "구간의 합 구하기" 문제를 빠르게 풀 수 있다.
또한, 어떤 문제에서는 prefix sum을 구해보면 생각하지 못했던 성질이 나타나서, 그게 문제를 푸는 열쇠가 되기도 한다.
아예 prefix sum 값에 관한 문제가 나오기도 한다.
prefix sum은 간단하지만 중요한 개념이다.

그래서 도대체 그 prefix sum이란게 무엇인가 하면, 다음과 같다.
$a_1$부터 $a_n$까지의 $n$개의 숫자가 늘어서 있을 때,
prefix sum 배열 $p_i$의 값은 다음과 같다.

$$p_i = \sum_{k<i} a_k$$

말로 풀어서 쓰면, $p_i$의 값은 $a_1,\: a_2,\: \dots a_i$의 값의 합이다.

$p_i$ 배열의 값에 대해 이야기하기 전에, 먼저 $p_i$를 구하는 C/C++ 코드를 짜 보자.
$p_1$부터 $p_n$ 각각에 대해, $a_1$부터 $a_i$까지의 값을 모두 $p_i$에 더하는 코드를,
이렇게 짜려고 할 수도 있다.

for(int i = 1; i <= n; ++i){
    for(int j = 1; j <= i; ++j){
        p[i] += a[j];
    }
}

이렇게 하면, $p_i$에 값을 더하는 연산이 총 $1+\cdots+(n-1)=\frac{n(n+1)}{2}$번 발생하므로,
시간복잡도는 $O(n^2)$이다.

그런데 이보다 빠르게 할 수 있다. 왜냐하면 $p_n=p_{n-1}+a_n$이기 때문이다. 즉 이렇게 짤 수 있다.

p[1] = a[1];
for(int i = 2; i <= n; ++i){
    p[i] = p[i-1] + a[i];
}

이렇게 하면 $\textrm{O(N)}$에 prefix sum 배열을 채울 수 있다.

prefix sum에는 몇 가지 특징이 있다.

무엇보다, 구간의 합을 prefix sum의 차로 계산 가능하다.
즉 $a_L + a_{L+1} + \dots + a_{R-1} + a_{R} = p_{R} - p_{L-1}$ 이다.
구간의 크기가 아무리 크더라도, prefix sum을 한 번 계산해 놓았다면
단순히 두 값의 차를 구하는 것으로 $O(1)$에 구간의 합을 계산할 수 있다.
때문에 넓은 구간의 합을 여러 번 물어보는 경우에도 쉽게 답할 수 있다.

또, 0 이상인 수열의 prefix sum 배열은 증가하는 형태이고,
증가하는 수열의 prefix sum은, 아래로 볼록한 함수의 모양을 가진다.