Algorithms/Prefix Sums

2.14.1 Prefix Sum

개념

배열 앞에서부터 더한 값을 미리 저장해 여러 구간의 합을 빠르게 구하는 방법입니다.

구간 합 계산

PiP_i를 처음 ii개 원소의 합으로 정의하면 P0=0P_0=0, Pi=Pi−1+AiP_i=P_{i-1}+A_i입니다. ll번째부터 rr번째까지의 합은 Pr−Pl−1P_r-P_{l-1}입니다.

[2,4,1,5][2,4,1,5]의 누적 합은 [0,2,6,7,12][0,2,6,7,12]입니다. 두 번째부터 네 번째 원소의 합은 12−2=1012-2=10입니다.

구간 앞쪽에 포함된 공통 부분을 빼는 방식입니다. 값이 바뀌면 뒤쪽의 누적 합도 바뀌므로 주로 배열이 고정된 상태에서 많은 질의를 처리할 때 사용합니다.

식에서 빼는 부분을 펼치면 Pr=A1+⋯+Al−1+Al+⋯+ArP_r=A_1+\cdots+A_{l-1}+A_l+\cdots+A_r이고, Pl−1=A1+⋯+Al−1P_{l-1}=A_1+\cdots+A_{l-1}입니다. 두 식을 빼면 구간 앞쪽의 합이 상쇄되고 Al+⋯+ArA_l+\cdots+A_r만 남습니다. l=1l=1일 때도 앞쪽에 원소가 없는 합을 P0=0P_0=0으로 두면 같은 식을 사용할 수 있습니다.

길이 NN인 배열에서 구간 합을 QQ번 묻는다면 매번 더하는 방법은 최대 NQNQ개의 원소를 확인합니다. 누적 합은 처음에 배열을 한 번 더한 뒤 각 질문에서 두 누적 합만 확인합니다. 구간의 길이와 위치가 서로 달라도 같은 표를 재사용할 수 있습니다.

복잡도

원소 수를 NN, 질의 수를 QQ라고 합니다.

연산시간복잡도공간복잡도
누적합 전처리O(N)O(N)누적합 O(N)O(N)
구간 합 질의O(1)O(1)추가 O(1)O(1)
전처리와 전체 질의O(N+Q)O(N+Q)누적합 O(N)O(N)

예제

문제

주어진 배열에서 여러 구간의 합을 구하여라.

입력

첫째 줄에 원소 수 NN과 질의 수 QQ가 공백을 사이에 두고 주어진다. 1≤N,Q≤1 0001\le N,Q\le1\,000이다.

둘째 줄에 수열의 원소 a1,a2,…,aNa_1,a_2,\ldots,a_N이 공백을 사이에 두고 주어진다. 1≤ai<10 0001\le a_i<10\,000이다.

다음 QQ개 줄에 구간의 양 끝 번호 l,rl,r이 공백을 사이에 두고 주어진다. 1≤l≤r≤N1\le l\le r\le N이다. 두 끝의 원소를 모두 포함한다.

출력

각 구간의 합을 한 줄에 출력한다.

예제 입력

4 3
2 4 1 5
2 4
1 4
3 3

예제 출력

10
12
1

예제 코드

C++20

#include <iostream>

using namespace std;

int p[1001];

int main() {
    int n, q, i, x, l, r;

    cin >> n >> q;
    for (i = 1; i <= n; ++i) {
        cin >> x;
        p[i] = p[i - 1] + x;
    }
    for (i = 0; i < q; ++i) {
        cin >> l >> r;
        cout << p[r] - p[l - 1] << '\n';
    }
}