누적합과 구간합 알고리즘

배열에서 특정 구간의 합을 구할 때 시간 복잡도를 O(1)로 만들 수 있는 방법

 

누적합

배열에서 순차적으로 누적해서 합을 저장한다.

1차원 배열

1	2	3	4	5
1	3	6	10	15

for(int i = 1; i <= n; i++) {
	cin >> S[i];
	S[i] = S[i-1] + S[i];
}

2차원 배열

for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= m; j++) {
      cin >> S[i][j];
			S[i][j] += S[i][j - 1] + S[i - 1][j] - S[i - 1][j - 1]; // 중복되는 부분을 한번 제거
	}
}

예를들어 14의 경우 6(왼쪽) + 3(위쪽) + 6(자신) - 1(대각선)으로 계산해서 나온 결과이다.

구간합

위에서 구한 누적합 배열을 바탕으로 구간합을 구할 수 있다.

1차원 배열

i에서 j까지 구간합

S[j] - S[i-1]

2차원 배열

(x1, y1), (x2, y2) 영역의 구간합

// 나머지 영영역을 제거하고 중복되는 부분을 한번 더해줌 
S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] + S[x1 - 1][y1 - 1]

하늘색영역을 구하기 위해 노란색 영역들을 빼주고, 중복으로 뺀 초록색 영역을 한번 더해준다