[기본] 합배열과 구간 합 구하기

 

 

합배열과 구간합

합배열은 특정 배열의 누적 합을 저장하는 배열로, 구간합을 빠르게 계산하기 위해 사용됩니다. 배열의 i번째까지의 누적 합을 저장하여, 특정 구간의 합을 O(1) 시간 복잡도로 구할 수 있습니다.

합배열 계산

배열 A가 주어졌을 때, 합배열 S는 다음과 같이 정의됩니다.

S[i]=A[1]+A[2]+...+A[i]

즉,

• S[0]=0 (기본값)
• S[i]=S[i−1]+A[i]

를 만족합니다.

예제

배열 A=[2,4,5,7,9,12] 가 주어졌을 때, 합배열 S 는 다음과 같습니다.

i	A[i]	S[i]
0	0	0
1	2	2
2	4	6
3	5	11
4	7	18
5	9	27
6	12	39

 

구간합 계산

구간합을 구하는 공식은 매우 쉽습니다. 구간 i에서 j까지의 구간합을 구하는 공식은 다음과 같습니다.

• S[j] - S[i -1]

• 예:
  구간 [2, 5]의 합은 S[5] - S[1] = 25
  구간 [3, 4]의 합은 S[4] - S[2] = 12
  구간 [5, 5]의 합은 S[5] - S[4] = 9

 

시간복잡도 비교

• 기본 방식: 구간합을 직접 더하면 O(N)
• 합배열 이용: 한 번의 뺄셈으로 O(1)

즉, 합배열을 사전에 O(N) 에 계산해두면, 구간합을 매우 빠르게 구할 수 있습니다.

 

 

실전 문제

백준 11659: 구간 합 구하기 4(링크)

 

문제

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

출력

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

제한

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000
• 1 ≤ i ≤ j ≤ N

예제 입력 1

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

예제 출력 1

12
9
1

 

시간제한	메모리	정답 비율
1 초	256 MB	38.466%

 

코드

// C++ 17
#include <iostream>
#include <vector>

using namespace std;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    
	int dataCount, queryCount = 0;
	cin >> dataCount >> queryCount;

	vector<int> rangeSum;
	rangeSum.reserve(dataCount + 1);
	rangeSum.push_back(0);
	
	for (int i = 0; i < dataCount; i++)
	{
		int data;
		cin >> data;
		rangeSum.push_back(rangeSum[i] + data);
	}

	for (int i = 0; i < queryCount; i++)
	{
		int start, end;
		cin >> start >> end;
		cout << rangeSum[end] - rangeSum[start - 1] << '\n';
	}
}

 

배열 입력을 받자마자 합배열을 만들고, 구간이 주어지는 즉시 구간합 공식을 통해 출력하는 코드입니다.