[C++] 구간 합

구간 합의 핵심 이론

• 합 배열 S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] ( 배열 A의 0~i까지의 합 배열 S)
• 합 배열을 미리 구해놓으면, 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N) -> O(1)로 감소한다.
• 합 배열 S를 만드는 공식
  • S[i] = S[i-1] + A[i]
• 구간 합을 구하는 공식
  • S[j] - S[i-1] ( i~j까지의 구간 합)

 

관련 문제들

• 백준 11659 (실버3)

#include <iostream>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int N, M;
	int k;
	cin >> N >> M;

	int sum[100001] = {};

	for (int i = 1; i <= N; i++)	// sum[0]=0, sum[1], sum[2] ...
	{
		cin >> k;
		sum[i] = sum[i - 1] + k;
	}

	int i, j;
	for (int a = 0; a < M; a++)
	{
		cin >> i >> j;
		cout << sum[j] - sum[i - 1] << '\n';
	}
}

• 백준 11660 (실버1)

#include <iostream>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int N, M;	// 표의크기 NxN, 합을 구해야하는 횟수 M
	cin >> N >> M;

	int** sum = new int* [N + 1] {};
	for (int i = 0; i <= N; i++)
	{
		sum[i] = new int[N + 1] {};
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			int temp;
			cin >> temp;
			sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + temp;
		}
	}

	for (int i = 0; i < M; i++)
	{
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		cout << sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1] << '\n';
	}

	for (int i = 0; i <= N; i++)
	{
		delete[] sum[i];
	}
}

• 백준 10986 (골드3)

#include <iostream>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int N, M;
	cin >> N >> M;

	long* sum = new long[N + 1] {};
	long* index = new long[M + 1] {};

	for (int i = 1; i <= N; i++)
	{
		int temp;
		cin >> temp;
		sum[i] = sum[i - 1] + temp;
	}

	long answer = 0;
	for (int i = 1; i <= N; i++)
	{
		sum[i] %= M;
		if (sum[i] == 0)
		{
			answer++;	// 0~i구간이 0인 부분
		}
		index[sum[i]]++;
	}

	for (int i = 0; i < M; i++)
	{
		if (index[i] > 1)
		{
			answer += index[i] * (index[i] - 1) / 2;
		}
	}
	cout << answer;

	delete[] sum;
	delete[] index;

	return 0;
}