11659번: 구간 합 구하기 4 www.acmicpc.net 이 문제는 수 N개가 주어졌을 때 i번째 수부터 j번째 수까지 합을 구하는 문제이다. 만약 주어지는 (i, j) 쌍의 수가 적다면 단순히 i번째 수부터 j번째 수까지 더하면 끝나지만, 문제는 주어지는 (i, j) 쌍의 수가 최대 10^6개까지 가능하다는 점이다. 그러므로 매번 (i, j) 쌍이 주어질 때마다 합을 직접 구하려고 하면 O(NM)의 시간이 소요돼 비효율적인 알고리즘이 된다. 그러므로 좀더 효율적인 알고리즘을 고안할 필요가 있다. 이를 해결하는 효율적인 알고리즘 중 하나는 수열의 합에서 아이디어를 착안할 수 있다. 어떤 수열의 일반항 a_n이 주어진 경우 이를 이용해 수열의 합의 일반항 S_n을 구할 수 있다. 여기서 S_n은 a_..
