구간 합 알고리즘을 이용해 특정 구간의 합을 빠르게 구해야 하는 문제입니다.

가장 쉽고 직관적인 방법으로 풀면 다음과 같이 코드를 작성할 수 있습니다.

#include <iostream>
#include <vector>

int main()
{
	int N, testCase;

	std::cin >> N >> testCase;

	std::vector<int> nums;
	nums.push_back(0);
	for (int i = 0; i < N; i++)
	{
		int num;
		std::cin >> num;
		nums.push_back(num);
	}

	for (int i = 0; i < testCase; i++)
	{
		int start, end;
		std::cin >> start >> end;

		int sum = 0;
		for (int j = start; j <= end; j++)
		{
			sum += nums[j];
		}
		std::cout << sum << "\n";
	}

	return 0;
}

이는 time complexity가 $O(N^2)$입니다. 이를 누적 합 알고리즘을 이용해 $O(N)$으로 단축시킬 수 있습니다.

구간 합 빠르게 구하기

특정 수열이 있을 때, 누적되는 값을 같이 계산합니다. 예를 들어 수열 [1,2,3,4,5]가 있다고 가정해봅시다.

0	1	2	3	4
1	2	3	4	5
1	3	6	10	15

이렇게 합 배열은 위 테이블처럼 구성됩니다. 즉, 이전 누적 합에 현재 index 값을 더해 계산합니다.

sums[i]=sums[i-1] + num;

여기에서 만약 1번째 index 부터 3번째 index까지의 합을 구하고 싶다면 3번째 index의 누적 합에 1번째 index 이전인 0번째 index의 값을 빼면 구할 수 있습니다.

합 배열을 구하는 time complexity는 $O(N)$이지만 구간 합을 구하는 계산의 time complexity를 $O(1)$로 단축시킬 수 있습니다.

---

0번째 index의 누적 합을 구한다고 하면 -1번째에 접근해 문제가 될 수도 있는데, 해당 문제에선 시작 index값이 1이기에 0번째 index에 0을 넣어서 해결했습니다.

#include <iostream>
#include <vector>

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);

	int N, testCase;

	std::cin >> N >> testCase;

	std::vector<int> nums(N + 1, 0);
	std::vector<int> sums(N + 1, 0);
	for (int i = 1; i <= N; i++) // O(N)
	{
		int num;
		std::cin >> num;
		nums[i] = num;
		sums[i] = sums[i - 1] + num;
	}

	for (int i = 0; i < testCase; i++) // O(N)
	{
		int start, end;
		std::cin >> start >> end;

		std::cout << sums[end] - sums[start - 1] << "\n";
	}

	return 0;
}