2차원 누적합, 부분합 구하기

누적합의 필요성

알고리즘 문제를 풀다보면 배열의 부분합을 빠르게 구해야 하는 경우가 있다. 

필요할 때 마다 구하게 되면 구할 때 마다 //(O(N)//)의 시간 복잡도를 갖는다.

종만북 1번 문제 페스티벌을 한번 보자.

https://algospot.com/judge/problem/read/FESTIVAL

가장 Naive한 알고리즘의 경우, 연속된 구간합을 구해서 그때그때마다 최소인지 모두 확인해 보는 방법인데, 구간합을 구하면 //(O(N^2)//)의 시간 복잡도를 갖기 때문에 상당히 느리다.

하지만 누적합을 이용하면 연속된 구간합을 //(O(N)//)만에 구할 수 있다.

누적합의 개념

대충 아래와 같은 수열이 있다고 해 보자. 총 5개의 원소를 가지고 있다.

인덱스 번호	//(1//)	//(2//)	//(3//)	//(4//)	//(5//)
//(a\scriptstyle i//)	//(3//)	//(5//)	//(7//)	//(1//)	//(4//)
//(S\scriptstyle i//)	//(3//)	//(8//)	//(15//)	//(16//)	//(20//)

위 수열에서 연속된 구간의 합, 예를들어 //(a\scriptstyle 2//)부터 //(a\scriptstyle 4//)까지의 합을 구하려고 한다면, 3개의 원소 값을 참조해야 한다.

이러한 점을 보완하기 위해서 누적합 수열 //(S\scriptstyle i//)를 도입해보자. 

//(S\scriptstyle i//)는 //(a\scriptstyle 1//)부터 //(a\scriptstyle i//)까지의 모든 원소의 합을 자신의 값으로 갖는다. 또한 //(S\scriptstyle 0\textstyle=0//)이다.

//(i//)번째 원소부터 //(j//)번째 원소의 구간합은 //(S\scriptstyle j\textstyle - S\scriptstyle i-1//)으로 구할 수 있다.

누적합 수열의 성질

1. //(S\scriptstyle 0\textstyle=0//)

2. //(S\scriptstyle 1\textstyle= a\scriptstyle1//)

3. //(S\scriptstyle i\textstyle=S\scriptstyle i-1\textstyle + a\scriptstyle i//)

4. //(S\scriptstyle n\textstyle=a\scriptstyle 1\textstyle +a\scriptstyle 2\textstyle + ... + a\scriptstyle n-1\textstyle + a\scriptstyle n//)

5. //(a\scriptstyle i\textstyle +a\scriptstyle i+1\textstyle + ... + a\scriptstyle j-1\textstyle + a\scriptstyle j\textstyle= S\scriptstyle j\textstyle - S\scriptstyle i-1//)

누적합을 활용한 빠른 구간합 계산

위의 누적합 수열의 성질 중 5번째 성질을 이용해서 연속된 임의의 구간의 합을 //(O(1)//)의 시간복잡도에 구할 수 있다. 다만 유의해야 할 사항은, 코드로 옮길 때, 누적합의 값이 산술 오버플로(Arithmetic Overflow)가 나타날 수 있으므로 변수 크기를 잘 조절해야 한다.

누적합을 이용해서 페스티벌 문제를 풀어본 코드이다.

페스티벌 문제 풀이 코드

 

#include <stdio.h>
#include <stdlib.h>

void dump_arr(int* arr, int len) {
	for (int i=0; i < len; i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");
}

int main() {
	int case_num, total_num, least_len, i, j, k, start, len, sum;
	int* arr, *summation;
	double min, current;
	
	scanf("%d", &case_num);
	
	for (i=0; i< case_num; i++) {
		scanf("%d %d", &total_num, &least_len);
		arr = (int*) calloc(sizeof(int), total_num);
		summation = (int*) calloc(sizeof(int), total_num + 1);
		summation[0] = 0;
		for (j=0; j< total_num; j++) {
			scanf("%d", &arr[j]);
			summation[j+1] = summation[j] + arr[j];
		}
		
		min = 9999999999;
		int start, end;
		for (start = 0; start <= total_num - least_len; start++) {
			for (end = start + least_len ; end <= total_num; end++) {
				current = (double)(summation[end] - summation[start]) / (end-start);
				if (min > current) {
					min = current;
				}
			}
		}
		
		printf("%.10f\n", min);
		
		free(arr);
		free(summation);
	}
}

2차원 누적합

위에서 언급한 누적합의 개념을 2차원으로 확장시킬 수 있다. 2차원 누적합으로 해결할 수 있는 문제의 예시로는 다음 Star sky 문제가 있다.

http://codeforces.com/contest/835/problem/C

누적합이 2차원으로 확장되면서 일차원 배열은 2차원 배열로 확장되고, 누적합 수열도 2차원 배열형태로 확장된다.

직사각형 형태의 배열에 포함되는 직사각형 구간의 모든 원소의 합을 빠르게 구할 수 있게 된다.

다음과 같이 2차원 배열 //(a(i, j)//)과 2차원 누적합 배열 //(S(i, j)//)가 있다고 가정해보자.

가장 왼쪽 위를 //(a(1, 1)//)라고 할 때 //(S(i,j)//)는 //(a(1,1)//)와 //(a(i,j)//)를 양 대각 끝 꼭지점으로 하는 직사각형 범위 면적 안의 모든 //(a//) 원소의 합으로 정의된다.

//(a(2,2) ~ a(3,3)//)의 부분합을 구하기 위해서는 //(S(3,3)//)에서 시작한다. 

//(S(3,3)//)값에서 //(S(1,3)//)값을 빼고, //(S(3,1)//) 값을 빼면 초록색 부분의 합에서 주황색 부분의 합이 빠진 값이 된다

. 왜냐하면 //(S(1,3)//)값에 주황색 부분이 포함되어 있고, //(S(3,1)//)부분에도 주황색 부분의 값이 포함되어 있으니, 두번 빼진 셈 이다. 

따라서 다시 주황색 부분에 해당하는 //(S(1,1)//)를 더해주면 초록색 부분의 구간합이 된다.

//((sx,sy)//)부터 //((dx,dy)//) 까지의 합을 //(Range(a,b,c,d)//)라고 할 때 이를 //(S(i,j)//)로 나타내면 다음과 같다.

//(Range(a,b,c,d)= S(dx,dy)- S(sx-1,dy)- S(dx,sy-1)+ S(sx-1,sy-1)//)

위 수식을 이용해서 직사각형 형태의 영역의 구간합을 //(O(1)//)의 시간복잡도에 구할 수 있다.

다만 구현 시 유의해야 할 점은, 정수 오버플로에 유의해야 한다. 

1차원 구간합 수열의 경우 //(S\scriptstyle 0\textstyle=0//)인데, 

2차원 구간합 수열의 경우 //(S(0,x)//)와 //(S(x,0)//)와 같은 형태로 나타나는 수열의 값은 모두 //(0//)이다.

따라서 해당 값에 0으로 값이 잘 들어가도록 하여 실수를 방지해야 한다.

2차원 구간합 수열을 구하는 방법은 Row 방향으로 한번 1차원 구간합을 모두 다 구한 뒤, Column 방향으로 구해진 구간합을 다시 구간합 하면 된다.

//(a(i,j)//)에서 Row(가로)방향으로 누적합을 구하여서 //(s(i,j)//) 수열이 되고, 해당 수열을 Column(세로)방향으로 누적합을 구해서 최종적인 //(S(i,j)//) 수열이 된다.

Star sky 문제 풀이 코드

 
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;

int map[101][101][11]; //x좌표 / y좌표 / 시작밝기 -> 누적합 버전
int main() {
	int n, q, c; //별의 개수, 별 바라보는 회수, 별의 최대밝기
	
	cin >> n >> q >> c;
	for (int i=0; i < n; i++) {
		int a,b,c;
		cin >> a >> b >> c;
		map[a][b][c]++;
	}
	
	for (int s=0; s < 11; s++) {
		for (int x=0; x < 101; x++) {
			for (int y=0; y < 100; y++) {
				map[x][y+1][s] += map[x][y][s];
			}
		}
	}
	for (int s=0; s < 11; s++) {
		for (int x=0; x < 101; x++) {
			for (int y=0; y < 100; y++) {
				map[y+1][x][s] += map[y][x][s];
			}
		}
	}
	
	while(q--) {
		int t, x1, y1, x2, y2;
		cin >> t >> x1 >> y1 >> x2 >> y2;
		int sum=0;
		
		for (int src_bright = 0; src_bright < 11; src_bright++) {
			int add = (src_bright + t) % (c+1);
			int num = map[x2][y2][src_bright] - map[x1-1][y2][src_bright] - map[x2][y1-1][src_bright] + map[x1-1][y1-1][src_bright];
			sum += add*num;
		}
		cout << sum << endl;
	}
}

복잡도 분석

누적합을 사용하는데에는 2단계의 Step이 있다.

1. 전처리(Preprocessing) : 누적합 수열 //(S(i)//) 혹은 //(S(i,j)//)를 구한다.

2. 계산 : 원하는 구간의 구간합을 계산한다.

전처리 단계의 경우 1차원 누적합일 경우 //(O(N)//)의 시간복잡도와 공간 복잡도를 갖는다.

2차원 누적합은 전처리 단계에서 //(O(N^2)//)의 시간복잡도와 공간 복잡도를 갖는다.

계산 단계의 경우 차원과 관계없이 //(O(1)//)의 상수 시간복잡도를 갖는다.

누적합의 한계

누적합의 경우에는 합을 구하는 도중에 원본 수열값이 변하는 경우 누적합 수열을 다시 계산해야하는 단점이 있다. 따라서 원본 수열값이 변할 수 있는 경우에 구간 합을 빠르게 구해야 할 경우에는 세그먼트 트리를 사용해야 한다.