누적합

누적합이란 요소들의 누적된 합의 의미로 어떠한 배열을 기반으로 앞에서 부터 요소들의 누적된 합을 저장해 새로이 배열을 만들어서 이를 활용하는 것을 말합니다.

 

이는 앞에서부터 더하는 prefix sum과 뒤에서부터 더하는 suffix sum이 있지만 코딩테스트는 prefix sum만 나오지 prefix sum 만 공부해도 좋습니다. 

 

누적합의 경우 0번 배열에 넣지 않고 1번 배열부터 담는 것이 구현하는 것이 쉽습니다. 

누적합이란 누적해서 더해진 값들의 배열을 의미합니다. 1,2,3,4 라는 배열의 누적합은 1,3,6,10이란 배열이 됩니다. 

이렇게 만들어놓으면 구간 쿼리에 대응하기가 쉽습니다. 예를 들어 0 번째 요소에서 3 번째 요소까지 다 더하라고 했을 때 누적합 배열 3 번째 요소를 이용하면 되기 때문입니다.

 

문제를 풀 때 '구간'에 대한 많은 '쿼리'가 나올 때 생각해야 될 것은 트리 또는 누적합입니다. 여기서 트리는 세그먼트, 펜윅트리를 뜻합니다. 이 때 그 구간 안에 있는 요소들이 변하지 않는 정적 요소라면 누적합을 쓰면 됩니다. 

 

예시 문제 

승철이는 뇌를 잃어버렸다. 학교에 갔더니 선생님이 자연수로 이루어진 N개의 카드를 주며 M개의 질문을 던진다. 그 질문은 나열한 카드 중 A 번째부터 B 번째까지의 합을 구하는 것이다. 뇌를 잃어버렸기 때문에 승철이는 이 문제를 풀 수 없다. 문제를 풀 수 있는 프로그램을 작성해보자.

 

입력

수의 개수 N, 합을 구해야 하는 횟수 M, 그 이후 N개의 수가 주어진다. 수는 100 이하의 자연수, 그 이후 M 개의 줄에는 합을 구해야 하는 구간 A, B가 주어진다.

출력

M개의 줄에 A부터 B까지의 합을 구하라.

범위

1 <= N <= 100,000

1 <= M <= 100,000

1 <= A <= B <= N

 

예제 입력

8 3
1 2 3 4 5 6 7 8
1 4
1 5 
3 5 

 

예제 출력

10
15
12

 

이 문제를 단순하게 생각하고 구현하면 어떻게 구현할까요.

int a[100004], b, c, psum[100004], n, m;

int main()
{
	cin >> n >> m;
    for(int i = 1; i <= n: i++)
    {
    	cin >> a[i];
	}
    for(int i = 0; i < m; i++)
    {
    	cin >> b >> c;
        int sum = 0;
        for(int j = b; j <= c; j++)
        {
        	sum += a[j];
        }
        cout << sum << '\n';
    }
    
    return 0;
}

위 코드의 경우는 10만 * 10만, 즉 100억이라는 시간복잡도를 갖습니다. 

이 때 누적합이라는 방식을 사용해야 합니다.

구간쿼리란 구간을 정해서 구간에 대한 합이나 곱과 같은 연산을 하는 것을 의미합니다.

즉 이 문제는 구간합 쿼리 문제입니다. 

 

누적합을 이용하면 미리 누적해놓은 값을 활용해 단순하게 마이너스 연산만으로 특정 구간에 대한 연산값을 얻을 수 있습니다.

예) 2- 5 구간의 합을 구해라 = psum[5] - psum[1]

 

동적 배열의 경우 펜윅트리를 사용해야 하지만, 정적 배열의 구간 쿼리에 대해서는 누적합을 사용하는 것이 좋습니다.

 

아래 코드는 누적합을 사용한 코드입니다.

int a[100004], b, c, psum[100004], n, m;
int main()
{
	cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
    	cin >> a[i];
        // 누적합이 1부터 시작해야하는 이유
        psum[i] = psum[i-1] + a[i];
    }
    for(int i =0; i < m; i++)
    {
    	cin >> b >>  c;
        cout << psum[c] - psum[b-1] << "\n";
    }
    
    return 0;
}

이전의 psum을 이용해 원하는 요소의 값 하나만 더해 원하는 값을 얻을 수 있습니다.

 

누적합 정리

구간 쿼리를 구하며 정적 배열의 경우 누적합을 사용하고, psum[i] = psum[i-1] + a[i] 를 이용해 만들 수 있습니다.