[알고리즘/ 자료구조] 구간 합

 

배열 A의 'A[0]부터 A[i] 까지의 합'을 '합 배열 S'에 미리 저장해둔다.

S[i] = S[i-1] + A[i]

 

나중에 구간 합을 구할 때는 

구간합 = S[j] - S[i-1]

 

합 배열을 사용해 구간 합을 구하면 O(N) 에서 O(1)로 시간 복잡도를 크게 줄일 수 있다.!

 

 

ex) 백준 11659

#include <iostream>
#include <vector>

int main()
{
	int N, M;

	std::cin >> N >> M;

	std::vector<int> Sum = std::vector<int>(N+1,0);
	for (int i = 1; i <= N; ++i)
	{
		std::cin >> Sum[i];
		Sum[i] += Sum[i - 1];
	}
	
	int i, j;
	while (M--)
	{
		std::cin >> i >> j;
		std::cout << Sum[j] - Sum[i - 1] << "\n";
	}
	
}