누적 합 (Prefix Sum)

크기가 $N$인 정수 배열 $A$가 있고, 여기서 다음과 같은 연산을 최대 $M$번 수행해야 하는 문제가 있습니다.

• 구간 $l$, $r$ ($l ≤ r$)이 주어졌을 때, $A[l] + A[l+1] + \dots + A[r-1] + A[r]$을 구해서 출력하기

$A[l] + A[l+1] + \dots + A[r-1] + A[r]$을 구하기 위해 소스 1과 같이 모두 더하는 방법이 있습니다.

int ans = 0;
for (int i=l; i<=r; i++) {
    ans += a[i];
}

int ans = 0;
for (int i=l; i<=r; i++) {
    ans += a[i];
}

ans = 0
for i in range(l, r+1):
    ans += a[i]

소스 1의 시간 복잡도는 $O(N)$입니다. 문제에서는 연산을 최대 $M$번 수행해야 한다고 했으니, 총 시간 복잡도는 $O(NM)$이 됩니다.

누적 합 아이디어는 배열 $A$에 들어있는 값이 바뀌지 않는다는 점을 이용합니다. 배열이 변하지 않으니 구간의 합도 변하지 않습니다. 따라서, 앞에서부터 차례대로 누적된 합을 구해놓고 이를 이용해서 구간의 합을 구할 수 있습니다.

$S[i] = A[1] + \dots + A[i]$, $S[0] = 0$ 으로 정의합시다.

$l$번째 수부터 $r$번째 수까지 합은 $S[r] - S[l-1]$과 같습니다.

그 이유를 알아보면

$S[r] = A[1] + ... + A[r]$

$S[l-1] = A[1] + ... + A[l-1]$

입니다. 따라서, $S[r] - S[l-1] = A[l] + \dots + A[r]$이 됩니다.

구간의 합을 구하기 위해서 뺄셈 연산 한 번만 하면되니 시간 복잡도는 $O(1)$입니다. 연산을 총 $M$번 수행해야 하니 총 시간 복잡도는 $O(M)$이 됩니다.

위의 예시는 $l = $, $r = $인 경우입니다.

누적 합을 저장할 배열 $S$는 $O(N)$에 구할 수 있습니다.

$S[i] = A[1] + \dots + A[i-1] + A[i]$이고, 여기서 $A[1] + \dots + A[i-1]$는 $S[i-1]$로 표현할 수 있습니다. 이 점을 이용해 소스 2와 같이 구현할 수 있습니다.

구간 $l$, $r$의 합은 $S[r] - S[l-1]$으로 구할 수 있습니다.

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

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

for i in range(1, n+1):
    s[i] = s[i-1] + a[i]

위의 설명에서 배열 $A$의 시작 인덱스는 $1$로 사용했습니다. 그 이유는 $S[l-1]$ 때문입니다. 시작 인덱스가 $1$이면 $l$의 최솟값은 $1$이고, 여기서 $l-1$은 $0$입니다. 만약, 시작 인덱스가 $0$이었다면, $l$의 최솟값은 $0$이고, 이때 $l-1$은 $-1$입니다.

배열의 인덱스로 음수를 사용할 수 없기 때문에, $1$부터 시작하는 것으로 정했습니다. 물론 $0$부터 시작해도 누적 합을 사용할 수 있습니다. 하지만, 뒤에 배열 한 칸이 더 필요합니다.

누적 합을 사용하기 위해 이 글의 가장 처음에 설명한 문제와 같은 문제입니다. 소스 3으로 해결할 수 있습니다.

#include <iostream>
#include <vector>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> a(n+1);
    vector<int> s(n+1);
    for (int i=1; i<=n; i++) {
        cin >> a[i];
        s[i] = s[i-1] + a[i];
    }
    while (m--) {
        int x, y;
        cin >> x >> y;
        cout << s[y] - s[x-1] << '\n';
    }
    return 0;
}

import java.util.*;
public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] a = new int[n+1];
        int[] s = new int[n+1];
        for (int i=1; i<=n; i++) {
            a[i] = sc.nextInt();
            s[i] = s[i-1] + a[i];
        }
        while (m-- > 0) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            System.out.println(s[y]-s[x-1]);
        }
    }
}

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
a = [0] + list(map(int,input().split()))
s = [0]*(n+1)
for i in range(1, n+1):
    s[i] = s[i-1] + a[i]
for _ in range(m):
    x,y = map(int,input().split())
    print(s[y]-s[x-1])

• 2559 - 수열
• 17425 - 약수의 합
• 10986 - 나머지 합