구간 합이란 시간복잡도를 줄이기 위해 합 배열을 미리 생성하는 알고리즘이다.기존 배결의 특정 범위의 합을 구하는 시간 복잡도는 O(N)이지만, 합 배열을 미리 구해 놓으면 시간 복잡도가 O(1)이 된다.합 배열의 기본 공식은 S[i] = S[i - 1] + A[i]이다.i에서 j까지의 구간 합 또한 S[j] - S[i - 1]로 나타낼 수 있다. 백준 11659. 구간 합 구하기 4(시간 제한 0.5초) 수 N개가 주어졌을 때, i번째 수에서 j번째 수의 합을 구하는 프로그램 첫째 줄에 수의 개수 N(1 ≤ N ≤ 100,000)과 합을 구해야 하는 횟수 M(1 ≤ M ≤ 100,000)이 주어진다.둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다.셋째 줄부터 M개의 줄에는 ..
