1. 구간 합

: 합 배열을 이용해 시간 복잡도를 더 줄이기 위한 알고리즘

(1) 구현 과정

구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 한다. 배열 A가 있을 때 합 배열 S는 다음과 같이 정의한다.

# 합 배열 S 정의

S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] // A[0] ~ A[i] 까지의 합

1. 먼저 합 배열을 구한다 -> 미리 구해둘 경우, 일정 범위의 합을 구하는 시간 복잡도가 감소 [O(1)]
2. 합배열 공식 : sum[i] = sum[i-1] + arr[i]
3. 구간합 공식 : sum[j]-sum[i-1] // i에서 j까지의 구간 합

• arr[2] ~ arr[5] 구간 합을 합 배열로 구하는 과정

sum[5] = arr[0] + arr[1] + arr[2]+ arr[3]+ arr[4]+ arr[5]
sum[1] = arr[0] + arr[1]
sum[5] - sum[1] = arr[2] + arr[3] + arr[4] + arr[5]

//sum[5]-sum[1]은 arr[2] ~ arr[5]까지의 구간 합

• 합 배열만 미리 구해 두면 구간 합은 한 번의 계산으로 구할 수 있다.
• 합배열은 A 배열이 바뀌지 않는 이상 합 배열을 다시 구하지 않아도 된다.
• 그런데, 배열 값이 자주 바뀌면?
• 이건 나중에 뒤에서 다뤄보겠음 !

---

문제 3. 구간 합 구하기 4 백준11659

수 N개가 주어졌을 때 i번째 수에서 j번째 수까지의 합을 구하는 프로그램을 작성하시오.

입력

1번째 줄에 수의 개수 N(1 <= N <= 100,000), 합을 구해야 하는 횟수 M(1 <= M <= 100,000), 2번째 줄에 N개의 수가 주어진다. 각 수는 1,000보다 작거나 같은 자연수다. 3번째 줄부터는 M개의 줄에 합을 구해야하는 구간 i와 j가주어진다.

• 코딩테스트는 항상 최악의 케이스를 생각하면서 풀어야 한다.
• 가장 큰 데이터가 들어온다고 가정하고 문제를 보자.
• 예제를 보고 확인한다.

출력

총 M개의 줄에 입력으로 주어진 i 번째 수에서 j 번째 수까지의 합을 출력한다.

예제 입력

5 3 // 데이터의 개수, 질의 개수
5 4 3 2 1 // 구간 합을 구할 대상 배열
1 3
2 4
5 5

예제 출력

12
9
1

---

1단계. 문제 분석하기

• 수 개수와 합을 구해야 하는 횟수가 최대 100,000 -> 구간마다 합을 계산할 경우 시간 초과
• 구간합을 구해야 하는 이 배열의 길이가 10만이 들어왔다고 가정, 질의 횟수도 10만개라고 가정하자. 1~10만개를 쭉 더한다.(10만번의 연산 횟수) = 질의 1번에 최악의 케이스이면 10만번의 연산이 일어난다. 근데 이 질의가 10만번 있다? ⇒ 시간복잡도는 1억이 넘는다.
• 따라서 해당 문제는 일반적으로 구간 합을 구하는 방식으로는 풀 수 없다.
• 구간합을 사용
  • 처음에 주어진 배열이 변하지 않는다. fix되어있음.
  • 심지어 질의의 갯수가 엄청 많다.
  • ⇒ 합 배열을 이용한 구간합 !

2단계. 손으로 풀어보기

1. N개의 수를 입력받아 합 배열 생성

   합 배열 공식: sum[i] = sum[i-1] + arr[i]

   • 합 배열 S는 데이터를 받으면서 바로바로 구할 수 있다. (매우 간단)

2. 구간 i~j가 주어지면 구간 합을 구해 출력

   구간 합 공식: sum[j] - sum[i-1]

   • 질의 10만개라고 가정하고, 합 배열을 이용한 구간 합 공식을 이용해 문제를 푼다.
     • 질의1(1, 3) : S[3] - S[0] = 12 - 0 = 12
     • 질의2(2, 4) : S[4] - S[1] = 14 - 5 = 9
     • 질의3(5, 5) : S[5] - S[4] = 15 - 14 = 1

3단계. 슈도코드 작성하기

• S[0] = A[0]

suNo(숫자 개수), quizNo(질의 개수) 저장하기
for(숫자 개수만큼 반복하기) {
	합 배열 생성하기(S[i] = S[i - 1] + A[i])
}
for(질의 개수만큼 반복하기) {
    질의 범위 받기다 〜 j)
    구간 합 출력하기(S[j] - S[i - 1])
}

//  구간 합 구하기 4_11659

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int suNo = Integer.parseInt(st.nextToken());
        int quizNo = Integer.parseInt(st.nextToken());
        
        long[] S = new long[suNo + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= suNo; i++) {
            S[i] = S[i - 1] + Integer.parseInt(st.nextToken());
        }
        for (int q = 0; q < quizNo; q++) {
            st = new StringTokenizer(br.readLine());
            int i = Integer.parseInt(st.nextToken());
            int j = Integer.parseInt(st.nextToken());
            System.out.println(S[j] - S[i - 1]);
        }
    }
}